Graphs of linear clique-width at most 3

A graph has linear clique-width at most k if it has a clique-width expression using at most k labels such that every disjoint union operation has an operand which is a single vertex graph. We give the first characterisation of graphs of linear clique-width at most 3, and we give the first polynomial-time recognition algorithm for graphs of linear clique-width at most 3. In addition, we present new characterisations of graphs of linear clique-width at most 2. We also give a layout characterisation of graphs of bounded linear clique-width; a similar characterisation was independently shown by Gurski and by Lozin and Rautenbach.     

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.     

Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization

We show that the NP-complete Feedback Vertex Set problem, which asks for the smallest set of vertices to remove from a graph to destroy all cycles, is deterministically solvable in O(ck⋅m) time. Here, m denotes the number of graph edges, k denotes the size of the feedback vertex set searched for, and c is a constant. We extend this to an algorithm enumerating all solutions in O(dk⋅m) time for a (larger) constant d. As a further result, we present a fixed-parameter algorithm with runtime O(k²⋅m²) for the NP-complete Edge Bipartization problem, which asks for at most k edges to remove from a graph to make it bipartite.     

Multilayer grid embeddings for VLSI

In this paper we propose two new multilayer grid models for VLSI layout, both of which take into account the number of contact cuts used. For the first model in which nodes “exist” only on one layer, we prove a tight area × (number of contact cuts) = Θ(n ²) tradeoff for embeddingn-node planar graphs of bounded degree in two layers. For the second model in which nodes “exist” simultaneously on all layers, we give a number of upper bounds on the area needed to embed groups using no contact cuts. We show that anyn-node graph of thickness 2 can be embedded on two layers inO(n ²) area. This bound is tight even if more layers and any number of contact cuts are allowed. We also show that planar graphs of bounded degree can be embedded on two layers inO(n ^3/2(logn)²) area. Some of our embedding algorithms have the additional property that they can respect prespecified grid placements of the nodes of the graph to be embedded. We give an algorithm for embeddingn-node graphs of thicknessk ink layers usingO(n ³) area, using no contact cuts, and respecting prespecified node placements. This area is asymptotically optimal for placement-respecting algorithms, even if more layers are allowed, as long as a fixed fraction of the edges do not use contact cuts. Our results use a new result on embedding graphs in a single-layer grid, namely an embedding ofn-node planar graphs such that each edge makes at most four turns, and all nodes are embedded on the same line.     

Computing the subset partial order for dense families of sets

We give an algorithm to compute the subset partial order (called the subset graph) for a family F of sets containing k sets with N elements in total and domain size n. Our algorithm requires O(nk²/logk) time and space on a Pointer Machine. When F is dense, i.e. N=Θ(nk), the algorithm requires O(N²/log²N) time and space. We give a construction for a dense family whose subset graph is of size Θ(N²/log²N), indicating the optimality of our algorithm for dense families. The subset graph can be dynamically maintained when F undergoes set insertions and deletions in O(nk/logk) time per update (that is sub-linear in N for the case of dense families). If we assume words of b?k bits, allow bits to be packed in words, and use bitwise operations, the above running time and space requirements can be reduced by a factor of blog(k/b+1)/logk and b²log(k/b+1)/logk respectively.     

Computing rank-width exactly

We prove that the rank-width of an n-vertex graph can be computed exactly in time O(n²n³log²nloglogn). To improve over a trivial O(n³logn)-time algorithm, we develop a general framework for decompositions on which an optimal decomposition can be computed efficiently. This framework may be used for other width parameters, including the branch-width of matroids and the carving-width of graphs.     

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.     

Collective Tree Spanners in Graphs with Bounded Parameters

In this paper we study collective additive tree spanners for special families of graphs including planar graphs, graphs with bounded genus, graphs with bounded tree-width, graphs with bounded clique-width, and graphs with bounded chordality. We say that a graph G=(V,E) admits a system of μ collective additive tree r -spanners if there is a system $\mathcal{T}(G)In this paper we study collective additive tree spanners for special families of graphs including planar graphs, graphs with bounded genus, graphs with bounded tree-width, graphs with bounded clique-width, and graphs with bounded chordality. We say that a graph G=(V,E) admits a system of μ collective additive tree r -spanners if there is a system T(G)\mathcal{T}(G) of at most μ spanning trees of G such that for any two vertices x,y of G a spanning tree T ? T(G)T\in\mathcal{T}(G) exists such that d _T (x,y)≤d _G (x,y)+r. We describe a general method for constructing a “small” system of collective additive tree r-spanners with small values of r for “well” decomposable graphs, and as a byproduct show (among other results) that any weighted planar graph admits a system of O(?n)O(\sqrt{n}) collective additive tree 0-spanners, any weighted graph with tree-width at most k−1 admits a system of klog ₂ n collective additive tree 0-spanners, any weighted graph with clique-width at most k admits a system of klog _3/2 n collective additive tree (2w)(2\mathsf{w}) -spanners, and any weighted graph with size of largest induced cycle at most c admits a system of log ₂ n collective additive tree (2?c/2?w)(2\lfloor c/2\rfloor\mathsf{w}) -spanners and a system of 4log ₂ n collective additive tree (2(?c/3?+1)w)(2(\lfloor c/3\rfloor +1)\mathsf {w}) -spanners (here, w\mathsf{w} is the maximum edge weight in G). The latter result is refined for weighted weakly chordal graphs: any such graph admits a system of 4log ₂ n collective additive tree (2w)(2\mathsf{w}) -spanners. Furthermore, based on this collection of trees, we derive a compact and efficient routing scheme for those families of graphs.     

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.     

On the existence of subexponential parameterized algorithms

The existence of subexponential-time parameterized algorithms is examined for various parameterized problems solvable in time O(2^O(k)p(n)). It is shown that for each t?1, there are parameterized problems in FPT for which the existence of O(2^o(k)p(n))-time parameterized algorithms implies the collapse of W[t] to FPT. Evidence is demonstrated that Max-SNP-hard optimization problems do not admit subexponential-time parameterized algorithms. In particular, it is shown that each Max-SNP-complete problem is solvable in time O(2^o(k)p(n)) if and only if 3-SAT∈DTIME(2^o(n)). These results are also applied to show evidence for the non-existence of -time parameterized algorithms for a number of other important problems such as Dominating Set, Vertex Cover, and Independent Set on planar graph instances.     

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.     

Serial and Parallel Algorithms for (k,2)-Partite Graphs

We introduce a class of layered graphs which we call (k,2)-partite and which we argue are an interesting class because of several important applications. We show that testing for (k,2)-partiteness can be done efficiently both on sequential and parallel machines, by showing that membership is in NSPACE(log n) and in NC². We show that (k,2)-partite graphs have bounded path width. We then show that a particular NP-complete problem, namely Maximum Independent Set, is solvable in linear time on bounded pathwidth graphs if the path decomposition is included in the input. Finally, we show that the Maximum Independent Set problem is in NC² for (k,2)-partite graphs. We note that linear time solutions for certain NP-complete problems have been shown for a wider class of graphs, namely partial k-trees. Our linear time algorithm is somewhat simpler in structure. We conjecture that our techniques can be used on many NP-complete problems to yield efficient algorithms for (k,2)-partite graphs.     

Efficient Exact Algorithms through Enumerating Maximal Independent Sets and Other Techniques

We give substantially improved exact exponential-time algorithms for a number of NP-hard problems. These algorithms are obtained using a variety of techniques. These techniques include: obtaining exact algorithms by enumerating maximal independent sets in a graph, obtaining exact algorithms from parameterized algorithms and a variant of the usual branch-and-bound technique which we call the "colored" branch-and-bound technique. These techniques are simple in that they avoid detailed case analyses and yield algorithms that can be easily implemented. We show the power of these techniques by applying them to several NP-hard problems and obtaining new improved upper bounds on the running time. The specific problems that we tackle are: (1) the Odd Cycle Transversal problem in general undirected graphs, (2) the Feedback Vertex Set problem in directed graphs of maximum degree 4, (3) Feedback Arc Set problem in tournaments, (4) the 4-Hitting Set problem and (5) the Minimum Maximal Matching and the Edge Dominating Set problems. The algorithms that we present for these problems are the best known and are a substantial improvement over previous best results. For example, for the Minimum Maximal Matching we give an O^*(1.4425ⁿ) algorithm improving the previous best result of O^*(1.4422^m) [35]. For the Odd Cycle Transversal problem, we give an O^*(1.62ⁿ) algorithm which improves the previous time bound of O^*(1.7724ⁿ) [3].     

A refined search tree technique for Dominating Set on planar graphs

We establish a refined search tree technique for the parameterized DOMINATING SET problem on planar graphs. Here, we are given an undirected graph and we ask for a set of at most k vertices such that every other vertex has at least one neighbor in this set. We describe algorithms with running times O(8^kn) and O(8^kk+n³), where n is the number of vertices in the graph, based on bounded search trees. We describe a set of polynomial time data-reduction rules for a more general “annotated” problem on black/white graphs that asks for a set of k vertices (black or white) that dominate all the black vertices. An intricate argument based on the Euler formula then establishes an efficient branching strategy for reduced inputs to this problem. In addition, we give a family examples showing that the bound of the branching theorem is optimal with respect to our reduction rules. Our final search tree algorithm is easy to implement; its analysis, however, is involved.     

Quadrilateral and tetrahedral mesh stripification using 2-factor partitioning of the dual graph

In order to find a 2-factor of a graph, there exists a O(n ^1.5) deterministic algorithm [7] and a O(n ³) randomized algorithm [14]. In this paper, we propose novel O(nlog³ nloglogn) algorithms to find a 2-factor, if one exists, of a graph in which all n vertices have degree 4 or less. Such graphs are actually dual graphs of quadrilateral and tetrahedral meshes. A 2-factor of such graphs implicitly defines a linear ordering of the mesh primitives in the form of strips. Further, by introducing a few additional primitives, we reduce the number of tetrahedral strips to represent the entire tetrahedral mesh and represent the entire quad surface using a single quad strip.     

On graphs with the third largest number of maximal independent sets

Let G be a simple and undirected graph. By mi(G) we denote the number of maximal independent sets in G. Erd?s and Moser posed the problem to determine the maximum cardinality of mi(G) among all graphs of order n and to characterize the corresponding extremal graphs attaining this maximum cardinality. The above problem has been solved by Moon and Moser in [J.W. Moon, L. Moser, On cliques in graphs, Israel J. Math. 3 (1965) 23-28]. More recently, Jin and Li [Z. Jin, X. Li, Graphs with the second largest number of maximal independent sets, Discrete Mathematics 308 (2008) 5864-5870] investigated the second largest cardinality of mi(G) among all graphs of order n and characterized the extremal graph attaining this value of mi(G). In this paper, we shall determine the third largest cardinality of mi(G) among all graphs G of order n. Additionally, graphs achieving this value are also determined.     

Algorithms for transitive closure

Let σ′(n) denote the number of all strongly connected graphs on the n-element set. We prove that σ′(n)?2ⁿ²·(1−n(n−1)/2ⁿ⁻¹). Hence the algorithm computing a transitive closure by a reduction to acyclic graphs has the expected time O(n²), under the assumption of uniform distribution of input graphs. Furthermore, we present a new algorithm constructing the transitive closure of an acyclic graph.     

Exact Algorithms for Exact Satisfiability and Number of Perfect Matchings

We present exact algorithms with exponential running times for variants of n-element set cover problems, based on divide-and-conquer and on inclusion–exclusion characterizations. We show that the Exact Satisfiability problem of size l with m clauses can be solved in time 2 ^m l ^O(1) and polynomial space. The same bounds hold for counting the number of solutions. As a special case, we can count the number of perfect matchings in an n-vertex graph in time 2 ⁿ n ^O(1) and polynomial space. We also show how to count the number of perfect matchings in time O(1.732 ⁿ ) and exponential space. We give a number of examples where the running time can be further improved if the hypergraph corresponding to the set cover instance has low pathwidth. This yields exponential-time algorithms for counting k-dimensional matchings, Exact Uniform Set Cover, Clique Partition, and Minimum Dominating Set in graphs of degree at most three. We extend the analysis to a number of related problems such as TSP and Chromatic Number.     

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.     

Many Distances in Planar Graphs

We show how to compute in O(n ^4/3log?^1/3 n+n ^2/3 k ^2/3log?n) time the distance between k given pairs of vertices of a planar graph G with n vertices. This improves previous results whenever (n/log?n)^5/6≤k≤n ²/log?⁶ n. As an application, we speed up previous algorithms for computing the dilation of geometric planar graphs.