Finding a dominating set on bipartite graphs

Finding a dominating set of minimum cardinality is an NP-hard graph problem, even when the graph is bipartite. In this paper we are interested in solving the problem on graphs having a large independent set. Given a graph G with an independent set of size z, we show that the problem can be solved in time O^∗(²n−z), where n is the number of vertices of G. As a consequence, our algorithm is able to solve the dominating set problem on bipartite graphs in time O^∗(²n/2). Another implication is an algorithm for general graphs whose running time is O(n^1.7088).     

Applying Modular Decomposition to Parameterized Cluster Editing Problems

A graph G is said to be a bicluster graph if G is a disjoint union of bicliques (complete bipartite subgraphs), and a cluster graph if G is a disjoint union of cliques (complete subgraphs). In this work, we study the parameterized versions of the NP-hard Bicluster Graph Editing and Cluster Graph Editing problems. The former consists of obtaining a bicluster graph by making the minimum number of modifications in the edge set of an input bipartite graph. When at most k modifications are allowed (Bicluster(k) Graph Editing problem), this problem is FPT, and can be solved in O(4 ^k nm) time by a standard search tree algorithm. We develop an algorithm of time complexity O(4 ^k +n+m), which uses a strategy based on modular decomposition techniques; we slightly generalize the original problem as the input graph is not necessarily bipartite. The algorithm first builds a problem kernel with O(k ²) vertices in O(n+m) time, and then applies a bounded search tree. We also show how this strategy based on modular decomposition leads to a new way of obtaining a problem kernel with O(k ²) vertices for the Cluster(k) Graph Editing problem, in O(n+m) time. This problem consists of obtaining a cluster graph by modifying at most k edges in an input graph. A previous FPT algorithm of time O(1.92 ^k +n ³) for this problem was presented by Gramm et al. (Theory Comput. Syst. 38(4), 373–392, 2005, Algorithmica 39(4), 321–347, 2004). In their solution, a problem kernel with O(k ²) vertices is built in O(n ³) time.     

Boolean-width of graphs

We introduce the graph parameter boolean-width, related to the number of different unions of neighborhoods-Boolean sums of neighborhoods-across a cut of a graph. For many graph problems, this number is the runtime bottleneck when using a divide-and-conquer approach. For an n-vertex graph given with a decomposition tree of boolean-width k, we solve Maximum Weight Independent Set in time O(n²k2^2k) and Minimum Weight Dominating Set in time O(n²+nk2^3k). With an additional n² factor in the runtime, we can also count all independent sets and dominating sets of each cardinality.Boolean-width is bounded on the same classes of graphs as clique-width. boolean-width is similar to rank-width, which is related to the number of GF(2)-sums of neighborhoods instead of the Boolean sums used for boolean-width. We show for any graph that its boolean-width is at most its clique-width and at most quadratic in its rank-width. We exhibit a class of graphs, the Hsu-grids, having the property that a Hsu-grid on Θ(n²) vertices has boolean-width Θ(logn) and rank-width, clique-width, tree-width, and branch-width Θ(n).     

On induced-universal graphs for the class of bounded-degree graphs

For a family F of graphs, a graph U is said to be F-induced-universal if every graph of F is an induced subgraph of U. We give a construction for an induced-universal graph for the family of graphs on n vertices with degree at most k. For k even, our induced-universal graph has O(nk/2) vertices and for k odd it has O(n⌈k/2⌉−1/klog2+2/kn) vertices. This construction improves a result of Butler by a multiplicative constant factor for the even case and by almost a multiplicative n1/k factor for the odd case. We also construct induced-universal graphs for the class of oriented graphs with bounded incoming and outgoing degree, slightly improving another result of Butler.     

Improved fixed parameter tractable algorithms for two “edge” problems: MAXCUT and MAXDAG

We give improved parameterized algorithms for two “edge” problems MAXCUT and MAXDAG, where the solution sought is a subset of edges. MAXCUT of a graph is a maximum set of edges forming a bipartite subgraph of the given graph. On the other hand, MAXDAG of a directed graph is a set of arcs of maximum size such that the graph induced on these arcs is acyclic. Our algorithms are obtained through new kernelization and efficient exact algorithms for the optimization versions of the problems. More precisely our results include:

(i)

a kernel with at most αk vertices and βk edges for MAXCUT. Here 0<α?1 and 1<β?2. Values of α and β depends on the number of vertices and the edges in the graph;

(ii)

a kernel with at most 4k/3 vertices and 2k edges for MAXDAG;

(iii)

an O^∗(k^1.2418) parameterized algorithm for MAXCUT in undirected graphs. This improves the O^∗(k^1.4143)¹ algorithm presented in [E. Prieto, The method of extremal structure on the k-maximum cut problem, in: The Proceedings of Computing: The Australasian Theory Symposium (CATS), 2005, pp. 119-126];

(iv)

an O^∗(n²) algorithm for optimization version of MAXDAG in directed graphs. This is the first such algorithm to the best of our knowledge;

(v)

an O^∗(k²) parameterized algorithm for MAXDAG in directed graphs. This improves the previous best of O^∗(k⁴) presented in [V. Raman, S. Saurabh, Parameterized algorithms for feedback set problems and their duals in tournaments, Theoretical Computer Science 351 (3) (2006) 446-458];

(vi)

an O^∗(k¹⁶) parameterized algorithm to determine whether an oriented graph having m arcs has an acyclic subgraph with at least m/2+k arcs. This improves the O^∗(k²) algorithm given in [V. Raman, S. Saurabh, Parameterized algorithms for feedback set problems and their duals in tournaments, Theoretical Computer Science 351 (3) (2006) 446-458].

In addition, we show that if a directed graph has minimum out degree at least f(n) (some function of n) then Directed Feedback Arc Set problem is fixed parameter tractable. The parameterized complexity of Directed Feedback Arc Set is a well-known open problem.     

Approximation and Tidying—A Problem Kernel for?s-Plex Cluster Vertex Deletion

We introduce the NP-hard graph-based data clustering problem s-Plex Cluster Vertex Deletion, where the task is to delete at most?k vertices from a graph so that the connected components of the resulting graph are s-plexes. In an s-plex, every vertex has an edge to all but at most s?1?other vertices; cliques are 1-plexes. We propose a new method based on “approximation and tidying” for kernelizing vertex deletion problems whose goal graphs can be characterized by forbidden induced subgraphs. The method exploits polynomial-time approximation results and thus provides a useful link between approximation and kernelization. Employing “approximation and tidying”, we develop data reduction rules that, in?O(ksn ²) time, transform an s-Plex Cluster Vertex Deletion instance with n vertices into an equivalent instance with O(k ² s ³)?vertices, yielding a problem kernel. To this end, we also show how to exploit structural properties of the specific problem in order to significantly improve the running time of the proposed kernelization method.     

Linear Time Algorithms for Finding a Dominating Set of Fixed Size in Degenerated Graphs

There is substantial literature dealing with fixed parameter algorithms for the dominating set problem on various families of graphs. In this paper, we give a k ^O(dk) n time algorithm for finding a dominating set of size at most k in a d-degenerated graph with n vertices. This proves that the dominating set problem is fixed-parameter tractable for degenerated graphs. For graphs that do not contain K _h as a topological minor, we give an improved algorithm for the problem with running time (O(h)) ^hk n. For graphs which are K _h -minor-free, the running time is further reduced to (O(log h)) ^hk/2 n. Fixed-parameter tractable algorithms that are linear in the number of vertices of the graph were previously known only for planar graphs. For the families of graphs discussed above, the problem of finding an induced cycle of a given length is also addressed. For every fixed H and k, we show that if an H-minor-free graph G with n vertices contains an induced cycle of size k, then such a cycle can be found in O(n) expected time as well as in O(nlog n) worst-case time. Some results are stated concerning the (im)possibility of establishing linear time algorithms for the more general family of degenerated graphs. A preliminary version of this paper appeared in the Proceedings of the 13th Annual International Computing and Combinatorics Conference (COCOON), Banff, Alberta, Canada (2007), pp. 394–405. N. Alon research supported in part by a grant from the Israel Science Foundation, and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University. This paper forms part of a Ph.D. thesis written by S. Gutner under the supervision of Prof. N. Alon and Prof. Y. Azar in Tel Aviv University.     

Maximum weight k-independent set problem on permutation graphs

Based on a Directed Acyclic Graph approach, an O(kn ²) time sequential algorithm is presented to solve the maximum weight k-independent set problem on weighted-permutation graphs. The weights considered here are all non-negative and associated with each of the n vertices of the graph. This problem has many applications in practical problems like k-machines job scheduling problem, k-colourable subgraph problem, VLSI design and routing problem.     

Compact Navigation and Distance Oracles for Graphs with Small Treewidth

Given an unlabeled, unweighted, and undirected graph with n vertices and small (but not necessarily constant) treewidth k, we consider the problem of preprocessing the graph to build space-efficient encodings (oracles) to perform various queries efficiently. We assume the word RAM model where the size of a word is Ω(logn) bits. The first oracle, we present, is the navigation oracle which facilitates primitive navigation operations of adjacency, neighborhood, and degree queries. By way of an enumeration argument, which is of interest in its own right, we show the space requirement of the oracle is optimal to within lower order terms for all graphs with n vertices and treewidth k. The oracle supports the mentioned queries all in constant worst-case time. The second oracle, we present, is an exact distance oracle which facilitates distance queries between any pair of vertices (i.e., an all-pairs shortest-path oracle). The space requirement of the oracle is also optimal to within lower order terms. Moreover, the distance queries perform in O(k ³log³ k) time. Particularly, for the class of graphs of popular interest, graphs of bounded treewidth (where k is constant), the distances are reported in constant worst-case time.     

Efficient Parallel Algorithms for Permutation Graphs

In this paper, we present optimal O(log n) time, O(n/log n) processor EREW PRAM parallel algorithms for finding the connected components, cut vertices, and bridges of a permutation graph. We also present an O(log n) time, O(n) processor, CREW PRAM model parallel algorithm for finding a Breadth First Search (BFS) spanning tree of a permutation graph rooted at vertex 1 and use the same to derive an efficient parallel algorithm for the All Pairs Shortest Path problem on permutation graphs.     

A Fully Dynamic Graph Algorithm for Recognizing Interval Graphs

We present the first dynamic graph algorithm for recognizing interval graphs. The algorithm runs in O(nlog?n) worst-case time per edge deletion or edge insertion, where n is the number of vertices in the graph. The algorithm uses a new representation of interval graphs called the train tree, which is based on the clique-separator graph representation of chordal graphs. The train tree has a number of useful properties and it can be constructed from the clique-separator graph in O(n) time.     

Path-matching problems

The notion of matching in graphs is generalized in this paper to a set of paths rather than to a set of edges. The generalized problem, which we call thepath-matching problem, is to pair the vertices of an undirected weighted graph such that the paths connecting each pair are subject to certain objectives and/or constraints. This paper concentrates on the case where the paths are required to be edge-disjoint and the objective is to minimize the maximal cost of a path in the matching (i.e., the bottleneck version). Other variations of the problem are also mentioned. Two algorithms are presented to find the best matching under the constraints listed above for trees. Their worst-case running times areO(n logd logw), whered is the maximal degree of a vertex,w is the maximal cost of an edge, andn is the size of the tree, andO(n ²), respectively. The problem is shown to be NP-complete for general graphs. Applications of these problems are also discussed.     

Bandwidth on AT-free graphs

We study the classical Bandwidth problem from the viewpoint of parametrised algorithms. Given a graph G=(V,E) and a positive integer k, the Bandwidth problem asks whether there exists a bijective function β:{1,…,∣V∣}→V such that for every edge uv∈E, ∣β⁻¹(u)−β⁻¹(v)∣≤k. It is known that under standard complexity assumptions, no algorithm for Bandwidth with running time of the form f(k)n^O(1) exists, even when the input is restricted to trees. We initiate the search for classes of graphs where such algorithms do exist. We present an algorithm with running time n⋅2^O(klogk) for Bandwidth on AT-free graphs, a well-studied graph class that contains interval, permutation, and cocomparability graphs. Our result is the first non-trivial algorithm that shows fixed-parameter tractability of Bandwidth on a graph class on which the problem remains NP-complete.     

An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs

A certifying algorithm for a problem is an algorithm that provides a certificate with each answer that it produces. The certificate is an evidence that can be used to authenticate the correctness of the answer. A Hamiltonian cycle in a graph is a simple cycle in which each vertex of the graph appears exactly once. The Hamiltonian cycle problem is to determine whether or not a graph contains a Hamiltonian cycle. The best result for the Hamiltonian cycle problem on circular-arc graphs is an O(n²logn)-time algorithm, where n is the number of vertices of the input graph. In fact, the O(n²logn)-time algorithm can be modified as a certifying algorithm although it was published before the term certifying algorithms appeared in the literature. However, whether there exists an algorithm whose time complexity is better than O(n²logn) for solving the Hamiltonian cycle problem on circular-arc graphs has been opened for two decades. In this paper, we present an O(Δn)-time certifying algorithm to solve this problem, where Δ represents the maximum degree of the input graph. The certificates provided by our algorithm can be authenticated in O(n) time.     

Algorithms for updating minimal spanning trees

The problem of finding the minimal spanning tree on an undirected weighted graph has been investigated by many people and O(n²) algorithms are well known. P. M. Spira and A. Pan (Siam J. Computing4 (1975), 375–380) present an O(n) algorithm for updating the minimal spanning tree if a new vertex is inserted into the graph. In this paper, we present another O(n) algorithm simpler than that presented by Spira and Pan for the insertion of a vertex. Spira and Pan further show that the deletion of a vertex requires O(n²) steps. If all the vertices are considered, O(n³) steps may be used. The algorithm which we present here takes only O(n²) steps and labels the vertices of the graph in such a way that any vertex may be deleted from the graph and the minimal spanning tree can be updated in constant time. Similar results are obtained for the insertion and the deletion of an edge.     

On Cutwidth Parameterized by Vertex Cover

We study the Cutwidth problem, where the input is a graph G, and the objective is find a linear layout of the vertices that minimizes the maximum number of edges intersected by any vertical line inserted between two consecutive vertices. We give an algorithm for Cutwidth with running time O(2 ^k n ^O(1)). Here k is the size of a minimum vertex cover of the input graph G, and n is the number of vertices in G. Our algorithm gives an O(2 ^n/2 n ^O(1)) time algorithm for Cutwidth on bipartite graphs as a corollary. This is the first non-trivial exact exponential time algorithm for Cutwidth on a graph class where the problem remains NP-complete. Additionally, we show that Cutwidth parameterized by the size of the minimum vertex cover of the input graph does not admit a polynomial kernel unless NP?coNP/poly. Our kernelization lower bound contrasts with the recent results of Bodlaender et al. (ICALP, Springer, Berlin, 2011; SWAT, Springer, Berlin, 2012) that both Treewidth and Pathwidth parameterized by vertex cover do admit polynomial kernels.     

Dominating set is fixed parameter tractable in claw-free graphs

We show that the Dominating Set problem parameterized by solution size is fixed-parameter tractable (FPT) in graphs that do not contain the claw (K_1,3, the complete bipartite graph on four vertices where the two parts have one and three vertices, respectively) as an induced subgraph. We present an algorithm that uses 2^O(k2)n^O(1) time and polynomial space to decide whether a claw-free graph on n vertices has a dominating set of size at most k. Note that this parameterization of Dominating Set is W[2]-hard on the set of all graphs, and thus is unlikely to have an FPT algorithm for graphs in general.The most general class of graphs for which an FPT algorithm was previously known for this parameterization of Dominating Set is the class of K_i,j-free graphs, which exclude, for some fixed i,j∈N, the complete bipartite graph K_i,j as a subgraph. For i,j≥2, the class of claw-free graphs and any class of K_i,j-free graphs are not comparable with respect to set inclusion. We thus extend the range of graphs over which this parameterization of Dominating Set is known to be fixed-parameter tractable.We also show that, in some sense, it is the presence of the claw that makes this parameterization of the Dominating Set problem hard. More precisely, we show that for any t≥4, the Dominating Set problem parameterized by the solution size is W[2]-hard in graphs that exclude the t-claw K_1,t as an induced subgraph. Our arguments also imply that the related Connected Dominating Set and Dominating Clique problems are W[2]-hard in these graph classes.Finally, we show that for any t∈N, the Clique problem parameterized by solution size, which is W[1]-hard on general graphs, is FPT in t-claw-free graphs. Our results add to the small and growing collection of FPT results for graph classes defined by excluded subgraphs, rather than by excluded minors.     

Computing Optimal Steiner Trees in Polynomial Space

Given an n-node edge-weighted graph and a subset of k terminal nodes, the NP-hard (weighted) Steiner tree problem is to compute a minimum-weight tree which spans the terminals. All the known algorithms for this problem which improve on trivial O(1.62 ⁿ )-time enumeration are based on dynamic programming, and require exponential space. Motivated by the fact that exponential-space algorithms are typically impractical, in this paper we address the problem of designing faster polynomial-space algorithms. Our first contribution is a simple O((27/4) ^k n ^O(logk))-time polynomial-space algorithm for the problem. This algorithm is based on a variant of the classical tree-separator theorem: every Steiner tree has a node whose removal partitions the tree in two forests, containing at most 2k/3 terminals each. Exploiting separators of logarithmic size which evenly partition the terminals, we are able to reduce the running time to $O(4^{k}n^{O(\log^{2} k)})$ . This improves on trivial enumeration for roughly k<n/3, which covers most of the cases of practical interest. Combining the latter algorithm (for small k) with trivial enumeration (for large k) we obtain a O(1.59 ⁿ )-time polynomial-space algorithm for the weighted Steiner tree problem. As a second contribution of this paper, we present a O(1.55 ⁿ )-time polynomial-space algorithm for the cardinality version of the problem, where all edge weights are one. This result is based on a improved branching strategy. The refined branching is based on a charging mechanism which shows that, for large values of k, convenient local configurations of terminals and non-terminals exist. The analysis of the algorithm relies on the Measure & Conquer approach: the non-standard measure used here is a linear combination of the number of nodes and number of non-terminals. Using a recent result in Nederlof (International colloquium on automata, languages and programming (ICALP), pp. 713–725, 2009), the running time can be reduced to O(1.36 ⁿ ). The previous best algorithm for the cardinality case runs in O(1.42 ⁿ ) time and exponential space.     

Parameterized algorithm for eternal vertex cover

In this paper we initiate the study of a “dynamic” variant of the classical Vertex Cover problem, the Eternal Vertex Cover problem introduced by Klostermeyer and Mynhardt, from the perspective of parameterized algorithms. This problem consists in placing a minimum number of guards on the vertices of a graph such that these guards can protect the graph from any sequence of attacks on its edges. In response to an attack, each guard is allowed either to stay in his vertex, or to move to a neighboring vertex. However, at least one guard has to fix the attacked edge by moving along it. The other guards may move to reconfigure and prepare for the next attack. Thus at every step the vertices occupied by guards form a vertex cover. We show that the problem admits a kernel of size k⁴(k+1)+2k, which shows that the problem is fixed parameter tractable when parameterized by the number of available guards k. Finally, we also provide an algorithm with running time O(²O(k²)+nm) for Eternal Vertex Cover, where n is the number of vertices and m the number of edges of the input graph. In passing we also observe that Eternal Vertex Cover is NP-hard, yet it has a polynomial time 2-approximation algorithm.     

On Independent Sets and Bicliques in Graphs

Bicliques of graphs have been studied extensively, partially motivated by the large number of applications. In this paper we improve Prisner’s upper bound on the number of maximal bicliques (Combinatorica, 20, 109–117, 2000) and show that the maximum number of maximal bicliques in a graph on n vertices is Θ(3 ^n/3). Our major contribution is an exact exponential-time algorithm. This branching algorithm computes the number of distinct maximal independent sets in a graph in time O(1.3642 ⁿ ), where n is the number of vertices of the input graph. We use this counting algorithm and previously known algorithms for various other problems related to independent sets to derive algorithms for problems related to bicliques via polynomial-time reductions.