Line graphs of bounded clique-width

We show that a set of graphs has bounded tree-width or bounded path-width if and only if the corresponding set of line graphs has bounded clique-width or bounded linear clique-width, respectively. This relationship implies some interesting algorithmic properties and re-proves already known results in a very simple way. It also shows that the minimization problem for NLC-width is NP-complete.     

Recent developments on graphs of bounded clique-width

Whether the clique-width of graphs in a certain class of graphs is bounded or not, is an important question from an algorithmic point of view, as many problems that are NP-hard in general admit polynomial-time solutions when restricted to graphs of bounded clique-width. Over the last few years, many classes of graphs have been shown to have bounded clique-width. For many others, this parameter has been proved to be unbounded. This paper provides a survey of recent results addressing this problem.     

Well-Quasi-Ordering versus Clique-Width: New Results on Bigenic Classes

Daligault, Rao and Thomassé asked whether a hereditary class of graphs well-quasi-ordered by the induced subgraph relation has bounded clique-width. Lozin, Razgon and Zamaraev recently showed that this is not true for classes defined by infinitely many forbidden induced subgraphs. However, in the case of finitely many forbidden induced subgraphs the question remains open and we conjecture that in this case the answer is positive. The conjecture is known to hold for classes of graphs defined by a single forbidden induced subgraph H, as such graphs are well-quasi-ordered and are of bounded clique-width if and only if H is an induced subgraph of P ₄. For bigenic classes of graphs, i.e. ones defined by two forbidden induced subgraphs, there are several open cases in both classifications. In the present paper we obtain a number of new results on well-quasi-orderability of bigenic classes, each of which supports the conjecture.     

Characterizations for co-graphs defined by restricted NLC-width or clique-width operations

In this paper we characterize subclasses of co-graphs defined by restricted NLC-width operations and subclasses of co-graphs defined by restricted clique-width operations.We show that a graph has NLCT-width 1 if and only if it is (C₄,P₄)-free. Since (C₄,P₄)-free graphs are exactly trivially perfect graphs, the set of graphs of NLCT-width 1 is equal to the set of trivially perfect graphs, and a recursive definition for trivially perfect graphs follows. Further we show that a graph has linear NLC-width 1 if and only if is (C₄,P₄,2K₂)-free. This implies that the set of graphs of linear NLC-width 1 is equal to the set of threshold graphs.We also give forbidden induced subgraph characterizations for co-graphs defined by restricted clique-width operations using P₄, 2K₂, and co-2P₃.     

A local characterization of bounded clique-width for line graphs

It is shown that a line graph G has clique-width at most 8k+4 and NLC-width at most 4k+3, if G contains a vertex whose non-neighbours induce a subgraph of clique-width k or NLC-width k in G, respectively. This relation implies that co-gem-free line graphs have clique-width at most 14 and NLC-width at most 7.It is also shown that in a line graph the neighbours of a vertex induce a subgraph of clique-width at most 4 and NLC-width at most 2.     

Counting truth assignments of formulas of bounded tree-width or clique-width

We study algorithms for ?SAT and its generalized version ?GENSAT, the problem of computing the number of satisfying assignments of a set of propositional clauses Σ. For this purpose we consider the clauses given by their incidence graph, a signed bipartite graph SI(Σ), and its derived graphs I(Σ) and P(Σ).It is well known, that, given a graph of tree-width k, a k-tree decomposition can be found in polynomial time. Very recently Oum and Seymour have shown that, given a graph of clique-width k, a (2^3k+2-1)-parse tree witnessing clique-width can be found in polynomial time.In this paper we present an algorithm for ?GENSAT for formulas of bounded tree-width k which runs in time 4^k(n+n²·log₂(n)), where n is the size of the input. The main ingredient of the algorithm is a splitting formula for the number of satisfying assignments for a set of clauses Σ where the incidence graph I(Σ) is a union of two graphs G₁ and G₂ with a shared induced subgraph H of size at most k. We also present analogue improvements for algorithms for formulas of bounded clique-width which are given together with their derivation.This considerably improves results for ?SAT, and hence also for SAT, previously obtained by Courcelle et al. [On the fixed parameter complexity of graph enumeration problems definable in monadic second order logic, Discrete Appl. Math. 108 (1-2) (2001) 23-52].     

On the OBDD size for graphs of bounded tree- and clique-width

We study the size of OBDDs (ordered binary decision diagrams) for representing the adjacency function f_G of a graph G on n vertices. Our results are as follows:

-

for graphs of bounded tree-width there is an OBDD of size O(logn) for f_G that uses encodings of size O(logn) for the vertices;

-

for graphs of bounded clique-width there is an OBDD of size O(n) for f_G that uses encodings of size O(n) for the vertices;

-

for graphs of bounded clique-width such that there is a clique-width expression for G whose associated binary tree is of depth O(logn) there is an OBDD of size O(n) for f_G that uses encodings of size O(logn) for the vertices;

-

for cographs, i.e. graphs of clique-width at most 2, there is an OBDD of size O(n) for f_G that uses encodings of size O(logn) for the vertices. This last result complements a recent result by Nunkesser and Woelfel [R. Nunkesser, P. Woelfel, Representation of graphs by OBDDs, in: X. Deng, D. Du (Eds.), Proceedings of ISAAC 2005, in: Lecture Notes in Computer Science, vol. 3827, Springer, 2005, pp. 1132-1142] as it reduces the size of the OBDD by an O(logn) factor using encodings whose size is increased by an O(1) factor.

     

On the expressive power of CNF formulas of bounded tree- and clique-width

We study representations of polynomials over a field K from the point of view of their expressive power. Three important examples for the paper are polynomials arising as permanents of bounded tree-width matrices, polynomials given via arithmetic formulas, and families of so called CNF polynomials. The latter arise in a canonical way from families of Boolean formulas in conjunctive normal form. To each such CNF formula there is a canonically attached incidence graph. Of particular interest to us are CNF polynomials arising from formulas with an incidence graph of bounded tree- or clique-width.We show that the class of polynomials arising from families of polynomial size CNF formulas of bounded tree-width is the same as those represented by polynomial size arithmetic formulas, or permanents of bounded tree-width matrices of polynomial size. Then, applying arguments from communication complexity we show that general permanent polynomials cannot be expressed by CNF polynomials of bounded tree-width. We give a similar result in the case where the clique-width of the incidence graph is bounded, but for this we need to rely on the widely believed complexity theoretic assumption #P?FP/poly.     

Improved bottleneck domination algorithms

W.C.K. Yen introduced BOTTLENECK DOMINATION and BOTTLENECK INDEPENDENT DOMINATION. He presented an -time algorithm to compute a minimum bottleneck dominating set. He also obtained that the BOTTLENECK INDEPENDENT DOMINATING SET problem is NP-complete, even when restricted to planar graphs.We present simple linear time algorithms for the BOTTLENECK DOMINATING SET and the BOTTLENECK TOTAL DOMINATING SET problem. Furthermore, we give polynomial time algorithms (most of them with linear time-complexities) for the BOTTLENECK INDEPENDENT DOMINATING SET problem on the following graph classes: AT-free graphs, chordal graphs, split graphs, permutation graphs, graphs of bounded treewidth, and graphs of clique-width at most k with a given k-expression.     

On powers of graphs of bounded NLC-width (clique-width)

Given a graph G, the graph G^l has the same vertex set and two vertices are adjacent in G^l if and only if they are at distance at most l in G. The l-coloring problem consists in finding an optimal vertex coloring of the graph G^l, where G is the input graph. We show that, for any fixed value of l, the l-coloring problem is polynomial when restricted to graphs of bounded NLC-width (or clique-width), if an expression of the graph is also part of the input. We also prove that the NLC-width of G^l is at most 2(l+1)^nlcw(G).     

Minimal Classes of Graphs of Unbounded Clique-Width

In the present paper, we identify the first two minimal with respect to set-inclusion hereditary classes of graphs of unbounded clique-width: Bipartite permutation graphs and unit interval graphs.     

Clique-width of graphs defined by one-vertex extensions

Let G be a graph and u be a vertex of G. We consider the following operation: add a new vertex v such that v does not distinguish any two vertices which are not distinguished by u. We call this operation a one-vertex extension. Adding a true twin, a false twin or a pendant vertex are cases of one-vertex extensions. Here we are interested in graph classes defined by a subset of allowed one-vertex extension. Examples are trees, cographs and distance-hereditary graphs. We give a complete classification of theses classes with respect to their clique-width. We also introduce a new graph parameter called the modular-width, and we give a relation with the clique-width.     

Solving some NP-complete problems using split decomposition

We show how to use the split decomposition to solve some NP-hard optimization problems on graphs. We give algorithms for clique problem and domination-type problems. Our main result is an algorithm to compute a coloration of a graph using its split decomposition. Finally we show that the clique-width of a graph is bounded if and only if the clique-width of each representative graph in its split decomposition is bounded.     

Split Permutation Graphs

The class of split permutation graphs is the intersection of two important classes, the split graphs and permutation graphs. It also contains an important subclass, the threshold graphs. The class of threshold graphs enjoys many nice properties. In particular, these graphs have bounded clique-width and they are well-quasi-ordered by the induced subgraph relation. It is known that neither of these two properties is extendable to split graphs or to permutation graphs. In the present paper, we study the question of extendability of these two properties to split permutation graphs. We answer this question negatively with respect to both properties. Moreover, we conjecture that with respect to both of them the split permutation graphs constitute a critical class.     

Relationships between the class of unit grid intersection graphs and other classes of bipartite graphs

We show that the class of unit grid intersection graphs properly includes both of the classes of interval bigraphs and of P₆-free chordal bipartite graphs. We also demonstrate that the classes of unit grid intersection graphs and of chordal bipartite graphs are incomparable.     

On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic

We discuss the parametrized complexity of counting and evaluation problems on graphs where the range of counting is definable in monadic second-order logic (MSOL). We show that for bounded tree-width these problems are solvable in polynomial time. The same holds for bounded clique width in the cases, where the decomposition, which establishes the bound on the clique-width, can be computed in polynomial time and for problems expressible by monadic second-order formulas without edge set quantification. Such quantifications are allowed in the case of graphs with bounded tree-width. As applications we discuss in detail how this affects the parametrized complexity of the permanent and the hamiltonian of a matrix, and more generally, various generating functions of MSOL definable graph properties. Finally, our results are also applicable to SAT and ♯SAT.     

Linear Clique‐Width for Hereditary Classes of Cographs

The class of cographs is known to have unbounded linear clique‐width. We prove that a hereditary class of cographs has bounded linear clique‐width if and only if it does not contain all quasi‐threshold graphs or their complements. The proof borrows ideas from the enumeration of permutation classes.     

A forbidden subgraph characterization of line-polar bipartite graphs

A graph is polar if the vertex set can be partitioned into A and B in such a way that the subgraph induced by A is a complete multipartite graph and the subgraph induced by B is a disjoint union of cliques. Polar graphs are a common generalization of bipartite, cobipartite, and split graphs. However, recognizing polar graphs is an NP-complete problem in general. This led to the study of the polarity of special classes of graphs such as cographs and chordal graphs, cf. Ekim et al. (2008) [7] and [5]. In this paper, we study the polarity of line graphs and call a graph line-polar if its line graph is polar. We characterize line-polar bipartite graphs in terms of forbidden subgraphs. This answers a question raised in the fist reference mentioned above. Our characterization has already been used to develop a linear time algorithm for recognizing line-polar bipartite graphs, cf. Ekim (submitted for publication) [6].     

Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree

Given an undirected graph with edge weights, we are asked to find an orientation, that is, an assignment of a direction to each edge, so as to minimize the weighted maximum outdegree in the resulted directed graph. The problem is called MMO, and is a restricted variant of the well-known minimum makespan problem. As in previous studies, it is shown that MMO is in P for trees, weak NP-hard for planar bipartite graphs, and strong NP-hard for general graphs. There are still gaps between those graph classes. The objective of this paper is to show tighter thresholds of complexity: We show that MMO is (i) in P for cactus graphs, (ii) weakly NP-hard for outerplanar graphs, and also (iii) strongly NP-hard for graphs which are both planar and bipartite. This implies the NP-hardness for P₄-bipartite, diamond-free or house-free graphs, each of which is a superclass of cactus. We also show (iv) the NP-hardness for series-parallel graphs and multi-outerplanar graphs, and (v) present a pseudo-polynomial time algorithm for graphs with bounded treewidth.     

The parameterized complexity of the induced matching problem

Given a graph G and an integer k≥0, the NP-complete Induced Matching problem asks whether there exists an edge subset M of size at least k such that M is a matching and no two edges of M are joined by an edge of G. The complexity of this problem on general graphs, as well as on many restricted graph classes has been studied intensively. However, other than the fact that the problem is W[1]-hard on general graphs, little is known about the parameterized complexity of the problem in restricted graph classes. In this work, we provide first-time fixed-parameter tractability results for planar graphs, bounded-degree graphs, graphs with girth at least six, bipartite graphs, line graphs, and graphs of bounded treewidth. In particular, we give a linear-size problem kernel for planar graphs.