Papers

Journal Papers

2009

Excluding a Bipartite Circle Graph from Line Graphs. J. Graph Theory, 60(2009)(3), pp. 183-203.
Circle Graph Obstructions under Pivoting (with Jim Geelen). J. Graph Theory 61(2009)(1), pp. 1-11.
Computing rank-width exactly, Information Proc. Letters 109(2009)(13), pp. 745-748

2008

Width Parameters Beyond Tree-width and Their Applications (with Petr Hliněný, Detlef Seese, and Georg Gottlob), The Computer Journal 51 (2008) (3), pp. 326-362. [show abstract]
Abstract:
Besides the very successful concept of tree-width (see [Bodlaender, H. and Koster, A. (2007) Combinatorial optimisation on graphs of bounded treewidth. These are special issues on Parameterized Complexity]), many concepts and parameters measuring the similarity or dissimilarity of structures compared to trees have been born and studied over the past years. These concepts and parameters have proved to be useful tools in many applications, especially in the design of efficient algorithms. Our presented novel look at the contemporary developments of these ?width? parameters in combinatorial structures delivers?besides traditional tree-width and derived dynamic programming schemes?also a number of other useful parameters like branch-width, rank-width (clique-width) or hypertree-width. In this contribution, we demonstrate how ?width? parameters of graphs and generalized structures (such as matroids or hypergraphs), can be used to improve the design of parameterized algorithms and the structural analysis in other applications on an abstract level.
Rank-width is less than or equal to branch-width. J. Graph Theory 57(2008)(3), pp. 239-244.
Rank-width and Well-quasi-ordering. SIAM J. Discrete Math., 22(2008)(2), pp. 666-682. [show abstract]
Abstract:
Robertson and Seymour (1990) proved that graphs of bounded tree-width are well-quasi-ordered by the graph minor relation. By extending their arguments, Geelen, Gerards, and Whittle (2002) proved that binary matroids of bounded branch-width are well-quasi-ordered by the matroid minor relation. We prove another theorem of this kind in terms of rank-width and vertex-minors. For a graph G=(V,E) and a vertex v of G, a local complementation at v is an operation that replaces the subgraph induced by the neighbors of v with its complement graph. A graph H is called a vertex-minor of G if H can be obtained from G by applying a sequence of vertex-deletions and local complementations. Rank-width was defined by Oum and Seymour (2006) to investigate clique-width; they showed that graphs have bounded rank-width if and only if they have bounded clique-width. We prove that graphs of bounded rank-width are well-quasi-ordered by the vertex-minor relation; in other words, for every infinite sequence G₁,G₂,... of graphs of rank-width (or clique-width) at most k, there exist i<j such that G_i is isomorphic to a vertex-minor of G_j. This implies that there is a finite list of graphs such that a graph has rank-width at most k if and only if it contains no one in the list as a vertex-minor. The proof uses the notion of isotropic systems defined by Bouchet.
Finding Branch-decompositions and Rank-decompositions (with Petr Hliněný). SIAM J. Comput. 38 (2008) (3), pp. 1012-1032.
Approximating Rank-width and Clique-width Quickly. ACM Trans. Algorithms, 5 (2008) (1), pp. 1-20.

2007

Vertex-Minors, Monadic Second-Order Logic, and a Conjecture by Seese (with Bruno Courcelle). J. Combin. Theory, Ser. B 97 (2007) (1), pp. 91-126. [show abstract]
Abstract:
We prove that one can express the vertex-minor relation on finite undirected graphs by formulas of monadic second-order logic (with no edge set quantification) extended with a predicate expressing that a set has even cardinality. We obtain a slight weakening of a conjecture by D. Seese stating that sets of graphs having a decidable satisfiability problem for monadic second-order logic have bounded clique-width. We also obtain a polynomial-time algorithm to decide rank-width at most k for any fixed k. The proofs use isotropic systems.
Testing Branch-width (with Paul Seymour). J. Combin. Theory, Ser. B 97(2007)(3), pp. 385-393. [show abstract]
Corrigendum to our paper "Testing branch-width", 2009.
Abstract:
An integer-valued function f on the set 2^V of all subsets of a finite set V is a connecitivity function if it satisfies
- f(X)+f(Y)≥ f(X cap Y)+f(X cup Y),
- f(X)=f(V-X),
- f(emptyset)=0.
Branch-width is defined for graphs, matroids, and more generally, connecitivity functions. We show that for each constant k, there is a polynomial-time (in |V|) algorithm to decide whether the branch-width of a connectivity function f is at most k, if f is given by an oracle. This algorithm can be applied to branch-width, carving-width, and rank-width of graphs. In particular, we can recognize matroids M of branch-width at most k in polynomial (in |E(M)|) time if the matroid is given by an independence oracle.

2006

Approximating Clique-width and Branch-width (with Paul Seymour). J. Combin. Theory, Ser. B 96 (2006) (4), pp. 514-528. [show abstract] (the 9th in the most downloaded papers between Jan-Mar 2006 from JCT B)
Abstract:
We construct a polynomial-time algorithm to approximate the branch-width of certain symmetric submodular functions, and give two applications.

The first is to graph "clique-width". Clique-width is a measure of the difficulty of decomposing a graph in a kind of tree-structure, and if a graph has clique-width at most k then the corresponding decomposition of the graph is called a "k-expression". We find (for fixed k) an O(n⁹ log n)-time algorithm that, with input an n-vertex graph, outputs either a (2^3k+2-1)-expression for the graph, or a true statement that the graph has clique-width at least k+1. (The best earlier algorithm algorithm, by Johansson (2001), constructed a 2k log n-expression for graphs of clique-width at most k.) It was already known that several graph problems, NP-hard on general graphs, are solvable in polynomial time if the input graph comes equipped with a k-expression (for fixed k). As a consequence of our algorithm, the same conclusion follows under the weaker hypothesis that the input graph has clique-width at most k (thus, we no longer need to be provided with an explicit k-expression).

Another application is to the area of matroid branch-width. For fixed k, we find an O(n⁴)-time algorithm that, with input an n-element matroid in terms of its rank oracle, either outputs a branch-decomposition of width at most 3k-1 or a true statement that the matroid has branch-width at least k+1. The previous algorithm by Hliněný (2002) was only for representable matroids.

2005

Rank-width and Vertex-minors. J. Combin. Theory, Ser. B 95 (2005) (1), pp. 79-100. [show abstract]
Corrigendum to: "Rank-width and vertex-minors", 2009.
(the 9th in the most downloaded papers between Jul-Sep 2005 from JCT B)
Abstract:
The rank-width is a graph parameter related in terms of fixed functions to clique-width but more tractable. Clique-width has nice algorithmic properties, but no good "minor" relation is known analogous to graph minor embedding for tree-width. In this paper, we discuss the vertex-minor relation of graphs and its connection with rank-width. We prove a relationship between vertex-minors of bipartite graphs and minors of binary matroids, and as an application, we prove that bipartite graphs of sufficiently large rank-width contain certain bipartite graphs as vertex-minors. The main theorem of this paper is that for fixed k, there is a finite list of graphs such that a graph G has rank-width at most k if and only if no graph in the list is isomorphic to a vertex-minor of G. Furthermore, we prove that a graph has rank-width at most 1 if and only if it is distance-hereditary.

Ph.D. Thesis Paper

Graphs of Bounded Rank-width, Princeton University, 2005. [show abstract]

Refereed Conference Papers

Approximating Rank-width and Clique-width Quickly. 31st International Workshop on Graph-Theoretic Concepts in Computer Science, Lecture Notes in Comput. Sci., vol 3787, pp. 49-58, 2005. [show abstract]
Abstract:
Rank-width is defined by Seymour and the author to investigate clique-width; they show that graphs have bounded rankwidth if and only if they have bounded clique-width. It is known that many hard graph problems have polynomial-time algorithms for graphs of bounded clique-width, however, requiring a given decomposition corresponding to clique-width (k-expression); they remove this requirement by constructing an algorithm that either outputs a rank-decomposition of width at most f(k) for some function f or confirms rank-width is larger than k in O(|V|⁹ log |V|) time for an input graph G=(V,E) and a fixed k. This can be reformulated in terms of clique-width as an algorithm that either outputs a (2^1+f(k)-1)-expression or confirms clique-width is larger than k in O(|V|⁹ log |V|) time for fixed k.
In this paper, we develop two separate algorithms of this kind with faster running time. We construct a O(|V|⁴)-time algorithm with f(k)=3k+1 by constructing a subroutine for the previous algorithm; we may now avoid using general submodular function minimization algorithms used by Seymour and the author. Another one is a O(|V|³)-time algorithm with f(k)=24k by giving a reduction from graphs to binary matroids; then we use an approximation algorithm for matroid branch-width by Hliněný.
Certifying Large Branch-width (with Paul Seymour). In the Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms (Miami, FL, 2006). SODA '06. ACM, New York, pp. 810-813, 2006. [show abstract]
Abstract:
Branch-width is defined for graphs, matroids, and, more generally, arbitrary symmetric submodular functions. For a finite set V, a function f on the set of subsets 2^V of V is submodular if f(X)+f(Y)≥ f(X cap Y)+f(X cup Y), and symmetric if f(X) = f(V-X). We discuss the computational complexity of recognizing that symmetric submodular functions have branch-width at most k for fixed k. An integer-valued symmetric submodular function f on 2^V is a connectivity function if f(emptyset)=0 and f({v})≤ 1 for all v in V. We show that for each constant k, if a connectivity function f on 2^V is presented by an oracle and the branch-width of f is larger than k, then there is a certificate of polynomial size (in |V|) such that a polynomial-time algorithm can verify the claim that branch-width of f is larger than k. In particular it is in coNP to recognize matroids represented over a fixed field with branch-width at most k for fixed k.
Finding Branch-decompositions and Rank-decompositions (with Petr Hliněný). 15th Annual European Symposium, Eilat, Israel, October 8-10, 2007, Lecture Notes in Comput. Sci., vol 4698, pp. 163-174, 2007.