Branch-decomposition

From Wikipedia, the free encyclopedia
Branch decomposition of a grid graph, showing an e-separation. The separation, the decomposition, and the graph all have width three.

In graph theory, a branch-decomposition of an undirected graph G is a hierarchical clustering of the edges of G, represented by an unrooted binary tree T with the edges of G as its leaves. Removing any edge from T partitions the edges of G into two subgraphs, and the width of the decomposition is the maximum number of shared vertices of any pair of subgraphs formed in this way. The branchwidth of G is the minimum width of any branch-decomposition of G.

Branchwidth is closely related to tree-width: for all graphs, both of these numbers are within a constant factor of each other, and both quantities may be characterized by forbidden minors. And as with treewidth, many graph optimization problems may be solved efficiently for graphs of small branchwidth. However, unlike treewidth, the branchwidth of planar graphs may be computed exactly, in polynomial time. Branch-decompositions and branchwidth may also be generalized from graphs to matroids.

Definitions[]

An unrooted binary tree is a connected undirected graph with no cycles in which each non-leaf node has exactly three neighbors. A branch-decomposition may be represented by an unrooted binary tree T, together with a bijection between the leaves of T and the edges of the given graph G = (V,E). If e is any edge of the tree T, then removing e from T partitions it into two subtrees T1 and T2. This partition of T into subtrees induces a partition of the edges associated with the leaves of T into two subgraphs G1 and G2 of G. This partition of G into two subgraphs is called an e-separation.

The width of an e-separation is the number of vertices of G that are incident both to an edge of E1 and to an edge of E2; that is, it is the number of vertices that are shared by the two subgraphs G1 and G2. The width of the branch-decomposition is the maximum width of any of its e-separations. The branchwidth of G is the minimum width of a branch-decomposition of G.

Relation to treewidth[]

Branch-decompositions of graphs are closely related to tree decompositions, and branch-width is closely related to tree-width: the two quantities are always within a constant factor of each other. In particular, in the paper in which they introduced branch-width, Neil Robertson and Paul Seymour[1] showed that for a graph G with tree-width k and branchwidth b > 1,

Carving width[]

Carving width is a concept defined similarly to branch width, except with edges replaced by vertices and vice versa. A carving decomposition is an unrooted binary tree with each leaf representing a vertex in the original graph, and the width of a cut is the number (or total weight in a weighted graph) of edges that are incident to a vertex in both subtrees.

Branch width algorithms typically work by reducing to an equivalent carving width problem. In particular, the carving width of the medial graph of a planar graph is exactly twice the branch width of the original graph.[2]

Algorithms and complexity[]

It is NP-complete to determine whether a graph G has a branch-decomposition of width at most k, when G and k are both considered as inputs to the problem.[2] However, the graphs with branchwidth at most k form a minor-closed family of graphs,[3] from which it follows that computing the branchwidth is fixed-parameter tractable: there is an algorithm for computing optimal branch-decompositions whose running time, on graphs of branchwidth k for any fixed constant k, is linear in the size of the input graph.[4]

For planar graphs, the branchwidth can be computed exactly in polynomial time. This in contrast to treewidth for which the complexity on planar graphs is a well known open problem.[5] The original algorithm for planar branchwidth, by Paul Seymour and Robin Thomas, took time O(n2) on graphs with n vertices, and their algorithm for constructing a branch decomposition of this width took time O(n4).[2] This was later sped up to O(n3).[6]

As with treewidth, branchwidth can be used as the basis of dynamic programming algorithms for many NP-hard optimization problems, using an amount of time that is exponential in the width of the input graph or matroid.[7] For instance, Cook & Seymour (2003) apply branchwidth-based dynamic programming to a problem of merging multiple partial solutions to the travelling salesman problem into a single global solution, by forming a sparse graph from the union of the partial solutions, using a spectral clustering heuristic to find a good branch-decomposition of this graph, and applying dynamic programming to the decomposition. Fomin & Thilikos (2006) argue that branchwidth works better than treewidth in the development of fixed-parameter-tractable algorithms on planar graphs, for multiple reasons: branchwidth may be more tightly bounded by a function of the parameter of interest than the bounds on treewidth, it can be computed exactly in polynomial time rather than merely approximated, and the algorithm for computing it has no large hidden constants.

Generalization to matroids[]

It is also possible to define a notion of branch-decomposition for matroids that generalizes branch-decompositions of graphs.[8] A branch-decomposition of a matroid is a hierarchical clustering of the matroid elements, represented as an unrooted binary tree with the elements of the matroid at its leaves. An e-separation may be defined in the same way as for graphs, and results in a partition of the set M of matroid elements into two subsets A and B. If ρ denotes the rank function of the matroid, then the width of an e-separation is defined as ρ(A) + ρ(B) − ρ(M) + 1, and the width of the decomposition and the branchwidth of the matroid are defined analogously. The branchwidth of a graph and the branchwidth of the corresponding graphic matroid may differ: for instance, the three-edge path graph and the three-edge star have different branchwidths, 2 and 1 respectively, but they both induce the same graphic matroid with branchwidth 1.[9] However, for graphs that are not trees, the branchwidth of the graph is equal to the branchwidth of its associated graphic matroid.[10] The branchwidth of a matroid is equal to the branchwidth of its dual matroid, and in particular this implies that the branchwidth of any planar graph that is not a tree is equal to that of its dual.[9]

Branchwidth is an important component of attempts to extend the theory of graph minors to matroid minors: although treewidth can also be generalized to matroids,[11] and plays a bigger role than branchwidth in the theory of graph minors, branchwidth has more convenient properties in the matroid setting.[12] Robertson and Seymour conjectured that the matroids representable over any particular finite field are well-quasi-ordered, analogously to the Robertson–Seymour theorem for graphs, but so far this has been proven only for the matroids of bounded branchwidth.[13] Additionally, if a minor-closed family of matroids representable over a finite field does not include the graphic matroids of all planar graphs, then there is a constant bound on the branchwidth of the matroids in the family, generalizing similar results for minor-closed graph families.[14]

For any fixed constant k, the matroids with branchwidth at most k can be recognized in polynomial time by an algorithm that has access to the matroid via an independence oracle.[15]

Forbidden minors[]

The four forbidden minors for graphs of branchwidth three.

By the Robertson–Seymour theorem, the graphs of branchwidth k can be characterized by a finite set of forbidden minors. The graphs of branchwidth 0 are the matchings; the minimal forbidden minors are a two-edge path graph and a triangle graph (or the two-edge cycle, if multigraphs rather than simple graphs are considered).[16] The graphs of branchwidth 1 are the graphs in which each connected component is a star; the minimal forbidden minors for branchwidth 1 are the triangle graph (or the two-edge cycle, if multigraphs rather than simple graphs are considered) and the three-edge path graph.[16] The graphs of branchwidth 2 are the graphs in which each biconnected component is a series–parallel graph; the only minimal forbidden minor is the complete graph K4 on four vertices.[16] A graph has branchwidth three if and only if it has treewidth three and does not have the cube graph as a minor; therefore, the four minimal forbidden minors are three of the four forbidden minors for treewidth three (the graph of the octahedron, the complete graph K5, and the Wagner graph) together with the cube graph.[17]

Forbidden minors have also been studied for matroid branchwidth, despite the lack of a full analogue to the Robertson–Seymour theorem in this case. A matroid has branchwidth one if and only if every element is either a loop or a coloop, so the unique minimal forbidden minor is the uniform matroid U(2,3), the graphic matroid of the triangle graph. A matroid has branchwidth two if and only if it is the graphic matroid of a graph of branchwidth two, so its minimal forbidden minors are the graphic matroid of K4 and the non-graphic matroid U(2,4). The matroids of branchwidth three are not well-quasi-ordered without the additional assumption of representability over a finite field, but nevertheless the matroids with any finite bound on their branchwidth have finitely many minimal forbidden minors, all of which have a number of elements that is at most exponential in the branchwidth.[18]

Notes[]

  1. ^ Robertson & Seymour 1991, Theorem 5.1, p. 168.
  2. ^ a b c Seymour & Thomas (1994).
  3. ^ Robertson & Seymour (1991), Theorem 4.1, p. 164.
  4. ^ Bodlaender & Thilikos (1997). Fomin, Mazoit & Todinca (2009) describe an algorithm with improved dependence on k, (2√3)k, at the expense of an increase in the dependence on the number of vertices from linear to quadratic.
  5. ^ Kao, Ming-Yang, ed. (2008), "Treewidth of graphs", Encyclopedia of Algorithms, Springer, p. 969, ISBN 9780387307701, Another long-standing open problem is whether there is a polynomial-time algorithm to compute the treewidth of planar graphs.
  6. ^ Gu & Tamaki (2008).
  7. ^ Hicks (2000); Hliněný (2003).
  8. ^ Robertson & Seymour 1991. Section 12, "Tangles and Matroids", pp. 188–190.
  9. ^ a b Mazoit & Thomassé (2007).
  10. ^ Mazoit & Thomassé (2007); Hicks & McMurray (2007).
  11. ^ Hliněný & Whittle (2006).
  12. ^ Geelen, Gerards & Whittle (2006).
  13. ^ Geelen, Gerards & Whittle (2002); Geelen, Gerards & Whittle (2006).
  14. ^ Geelen, Gerards & Whittle (2006); Geelen, Gerards & Whittle (2007).
  15. ^ Oum & Seymour (2007).
  16. ^ a b c Robertson & Seymour (1991), Theorem 4.2, p. 165.
  17. ^ Bodlaender & Thilikos (1999). The fourth forbidden minor for treewidth three, the pentagonal prism, has the cube graph as a minor, so it is not minimal for branchwidth three.
  18. ^ Hall et al. (2002); Geelen et al. (2003).

References[]

Retrieved from ""