Portal:Geometry/Selected article/6

2009-09-02T01:06:30Z

67.232.56.99: Pentagram-phi.svg was corrected, hence I'm now reverting it back to this image.

[[File:Branch-decomposition.svg|thumb|400px|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 decomposition|tree-width]] and many graph optimization problems may be solved efficiently for graphs of small branchwidth. Branch-decompositions and branchwidth may also be generalized from graphs to [[matroid]]s.

==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 ''T''1 and ''T''2. This partition of ''T'' into subtrees induces a partition of the edges associated with the leaves of ''T'' into two subgraphs ''G''1 and ''G''2 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 ''E''1 and to an edge of ''E''2; that is, it is the number of vertices that are shared by the two subgraphs ''G''1 and ''G''2. 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 decomposition]]s, and branch-width is closely related to [[tree decomposition|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 (mathematician)|Neil Robertson]] and [[Paul Seymour (mathematician)|Paul Seymour]]<ref>{{harvnb|Robertson|Seymour|1991}}, Theorem 5.1, p. 168.</ref> showed that for a graph ''G''
with tree-width ''k'' and branchwidth {{nowrap|''b'' > 1,}}
:<math>b -1 \le k \le \left\lfloor\frac{3}{2}b\right\rfloor -1.</math>

==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 graph is exactly twice the branch width of the original graph.<ref name="st94">{{harvtxt|Seymour|Thomas|1994}}.</ref>

==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.<ref name="st94"/> However, the graphs with branchwidth at most ''k'' form a [[Minor (graph theory)|minor-closed family of graphs]],<ref>{{harvtxt|Robertson|Seymour|1991}}, Theorem 4.1, p. 164.</ref> from which it follows that computing the branchwidth is [[Parameterized complexity|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.<ref>{{harvtxt|Bodlaender|Thilikos|1997}}. {{harvtxt|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.</ref>

For [[planar graph]]s, the branchwidth can be computed exactly in polynomial time.,<ref name="st94"/> this in contrast to treewidth for which the complexity on planar graphs is a well known open problem.

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.<ref>{{harvtxt|Hicks|2000}}; {{harvtxt|Hliněný|2003}}.</ref> For instance, {{harvtxt|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. {{harvtxt|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 [[matroid]]s that generalizes branch-decompositions of graphs.<ref>{{harvnb|Robertson|Seymour|1991}}. Section 12, "Tangles and Matroids", pp. 188–190.</ref> 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 [[Matroid rank|rank function]] of the matroid, then the width of an e-separation is defined as {{nowrap|ρ(''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 (graph theory)|star]] have different branchwidths, 2 and 1 respectively, but they both induce the same graphic matroid with branchwidth 1.<ref name="mt07"/> However, for graphs that are not trees, the branchwidth of the graph is equal to the branchwidth of its associated graphic matroid.<ref>{{harvtxt|Mazoit|Thomassé|2007}}; {{harvtxt|Hicks|McMurray|2007}}.</ref> 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.<ref name="mt07">{{harvtxt|Mazoit|Thomassé|2007}}.</ref>

Branchwidth is an important component of attempts to extend the theory of [[graph minor]]s to [[matroid minor]]s: although [[treewidth]] can also be generalized to matroids,<ref>{{harvtxt|Hliněný|Whittle|2006}}.</ref> and plays a bigger role than branchwidth in the theory of graph minors, branchwidth has more convenient properties in the matroid setting.<ref>{{harvtxt|Geelen|Gerards|Whittle|2006}}.</ref> Robertson and Seymour conjectured that the matroids representable over any particular [[finite field]] are [[well-quasi-ordering|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.<ref>{{harvtxt|Geelen|Gerards|Whittle|2002}}; {{harvtxt|Geelen|Gerards|Whittle|2006}}.</ref> 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.<ref>{{harvtxt|Geelen|Gerards|Whittle|2006}}; {{harvtxt|Geelen|Gerards|Whittle|2007}}.</ref>

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 [[matroid oracle|independence oracle]].<ref>{{harvtxt|Oum|Seymour|2007}}.</ref>

==Forbidden minors==
[[File:Branchwidth 3-forbidden minors.svg|thumb|The four [[forbidden minor]]s for graphs of branchwidth three.]]
By the [[Robertson–Seymour theorem]], the graphs of branchwidth ''k'' can be characterized by a finite set of [[forbidden minor]]s. The graphs of branchwidth 0 are the [[matching (graph theory)|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).<ref name="rs91-4.2"/> The graphs of branchwidth 1 are the graphs in which each [[connected component (graph theory)|connected component]] is a [[star (graph theory)|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.<ref name="rs91-4.2"/> 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]] ''K''4 on four vertices.<ref name="rs91-4.2">{{harvtxt|Robertson|Seymour|1991}}, Theorem 4.2, p. 165.</ref> A graph has branchwidth three if and only if it has treewidth three and does not have the [[hypercube graph|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 ''K''5, and the [[Wagner graph]]) together with the cube graph.<ref>{{harvtxt|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.</ref>

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 ''K''4 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.<ref>{{harvtxt|Hall|Oxley|Semple|Whittle|2002}}; {{harvtxt|Geelen|Gerards|Robertson|Whittle|2003}}.</ref>

==Notes==
{{Commonscat|Tree decomposition}}
{{reflist|2}}

==References==
{{refbegin|2}}
*{{citation
| last1 = Bodlaender | first1 = Hans L. | author1-link = Hans L. Bodlaender
| last2 = Thilikos | first2 = Dimitrios M.
| contribution = Constructive linear time algorithms for branchwidth
| doi = 10.1007/3-540-63165-8_217
| pages = 627–637
| publisher = Springer-Verlag
| series = Lecture Notes in Computer Science
| title = Proc. 24th International Colloquium on Automata, Languages and Programming (ICALP '97)
| volume = 1256
| year = 1997}}.
*{{citation
| last1 = Bodlaender | first1 = Hans L. | author1-link = Hans L. Bodlaender
| last2 = Thilikos | first2 = Dimitrios M.
| doi = 10.1006/jagm.1999.1011
| issue = 2
| journal = Journal of Algorithms
| pages = 167–194
| title = Graphs with branchwidth at most three
| volume = 32
| year = 1999}}.
*{{citation
| doi = 10.1287/ijoc.15.3.233.16078
| last1 = Cook | first1 = William
| last2 = Seymour | first2 = Paul D. | author2-link = Paul Seymour (mathematician)
| issue = 3
| journal = INFORMS Journal on Computing
| pages = 233–248
| title = Tour merging via branch-decomposition
| url = http://www.cs.utk.edu/~langston/projects/papers/tmerge.pdf
| volume = 15
| year = 2003}}.
*{{citation
| last1 = Fomin | first1 = Fedor V.
| last2 = Thilikos | first2 = Dimitrios M.
| doi = 10.1137/S0097539702419649
| journal = SIAM Journal on Computing
| page = 281
| title = Dominating sets in planar graphs: branch-width and exponential speed-up
| volume = 36
| year = 2006
| issue = 2}}.
*{{citation
| last1 = Fomin | first1 = Fedor V.
| last2 = Mazoit | first2 = Frédéric
| last3 = Todinca | first3 = Ioan
| doi = 10.1016/j.dam.2008.08.009
| issue = 12
| journal = Discrete Applied Mathematics
| pages = 2726–2736
| title = Computing branchwidth via efficient triangulations and blocks
| url = http://hal.archives-ouvertes.fr/hal-00390623/
| volume = 157
| year = 2009}}.
*{{citation
| last1 = Geelen | first1 = Jim | author1-link = Jim Geelen
| last2 = Gerards | first2 = Bert
| last3 = Robertson | first3 = Neil | author3-link = Neil Robertson (mathematician)
| last4 = Whittle | first4 = Geoff
| doi = 10.1016/S0095-8956(02)00046-1
| issue = 2
| journal = Journal of Combinatorial Theory, Series B
| pages = 261–265
| title = On the excluded minors for the matroids of branch-width ''k''
| volume = 88
| year = 2003}}.
*{{citation
| last1 = Geelen | first1 = Jim | author1-link = Jim Geelen
| last2 = Gerards | first2 = Bert
| last3 = Whittle | first3 = Geoff
| doi = 10.1006/jctb.2001.2082
| issue = 2
| journal = Journal of Combinatorial Theory, Series B
| pages = 270–290
| title = Branch-width and well-quasi-ordering in matroids and graphs
| volume = 84
| year = 2002}}.
*{{citation
| last1 = Geelen | first1 = Jim | author1-link = Jim Geelen
| last2 = Gerards | first2 = Bert
| last3 = Whittle | first3 = Geoff
| contribution = Towards a structure theory for matrices and matroids
| pages = 827–842
| title = Proc. [[International Congress of Mathematicians]]
| url = http://www.icm2006.org/proceedings/Vol_III/contents/ICM_Vol_3_41.pdf
| volume = III
| year = 2006}}.
*{{citation
| last1 = Geelen | first1 = Jim | author1-link = Jim Geelen
| last2 = Gerards | first2 = Bert
| last3 = Whittle | first3 = Geoff
| doi = 10.1016/j.jctb.2007.02.005
| issue = 6
| journal = Journal of Combinatorial Theory, Series B
| pages = 971–998
| title = Excluding a planar graph from GF(''q'')-representable matroids
| url = http://www.math.uwaterloo.ca/~jfgeelen/publications/grid.pdf
| volume = 97
| year = 2007}}.
*{{citation
| last1 = Hall | first1 = Rhiannon
| last2 = Oxley | first2 = James | author2-link = James Oxley
| last3 = Semple | first3 = Charles
| last4 = Whittle | first4 = Geoff
| doi = 10.1006/jctb.2002.2120
| issue = 1
| journal = Journal of Combinatorial Theory, Series B
| pages = 148–171
| title = On matroids of branch-width three
| volume = 86
| year = 2002}}.
*{{citation
| last = Hicks | first = Illya V.
| publisher = Rice University
| series = Ph.D. thesis
| title = Branch Decompositions and their Applications
| url = http://www.caam.rice.edu/caam/trs/2000/TR00-17.ps
| year = 2000}}.
*{{citation
| last1 = Hicks | first1 = Illya V.
| last2 = McMurray | first2 = Nolan B., Jr.
| doi = 10.1016/j.jctb.2006.12.007
| issue = 5
| journal = Journal of Combinatorial Theory, Series B
| pages = 681–692
| title = The branchwidth of graphs and their cycle matroids
| volume = 97
| year = 2007}}.
*{{citation
| last = Hliněný | first = Petr
| contribution = On matroid properties definable in the MSO logic
| doi = 10.1007/978-3-540-45138-9\_41
| pages = 470–479
| publisher = Springer-Verlag
| series = Lecture Notes in Computer Science
| title = Proc. 28th International Symposium on Mathematical Foundations of Computer Science (MFCS '03)
| volume = 2747
| year = 2003}}
*{{citation
| last1 = Hliněný | first1 = Petr
| last2 = Whittle | first2 = Geoff
| doi = 10.1016/j.ejc.2006.06.005
| issue = 7
| journal = European Journal of Combinatorics
| pages = 1117–1128
| title = Matroid tree-width
| url = http://www.fi.muni.cz/~hlineny/Research/papers/matr-tw-final.pdf
| volume = 27
| year = 2006}}.
**Addendum and corrigendum: {{citation
| last1 = Hliněný | first1 = Petr
| last2 = Whittle | first2 = Geoff
| title = Addendum to matroid tree-width
| journal = European Journal of Combinatorics
| volume=30
| issue=4
| pages=1036–1044
| year = 2009
| doi=10.1016/j.ejc.2008.09.028}}.
*{{citation
| last1 = Mazoit | first1 = Frédéric
| last2 = Thomassé | first2 = Stéphan
| contribution = Branchwidth of graphic matroids
| editor1-last = Hilton | editor1-first = Anthony
| editor2-last = Talbot | editor2-first = John
| page = 275
| publisher = Cambridge University Press
| series = London Mathematical Society Lecture Note Series
| title = Surveys in Combinatorics 2007
| url = http://hal.archives-ouvertes.fr/docs/00/04/09/28/PDF/Branchwidth.pdf
| volume = 346
| year = 2007}}.
*{{citation
| last1 = Oum | first1 = Sang-il
| last2 = Seymour | first2 = Paul | author2-link = Paul Seymour (mathematician)
| doi = 10.1016/j.jctb.2006.06.006
| issue = 3
| journal = [[Journal of Combinatorial Theory]]
| mr = 2305892
| pages = 385–393
| series = Series B
| title = Testing branch-width
| volume = 97
| year = 2007}}.
*{{citation
| last1 = Robertson | first1 = Neil | author1-link = Neil Robertson (mathematician)
| last2 = Seymour | first2 = Paul D. | author2-link = Paul Seymour (mathematician)
| doi = 10.1016/0095-8956(91)90061-N
| issue = 2
| journal = Journal of Combinatorial Theory
| pages = 153–190
| title = Graph minors. X. Obstructions to tree-decomposition
| volume = 52
| year = 1991}}.
*{{citation
| last1 = Seymour | first1 = Paul D. | author1-link = Paul Seymour (mathematician)
| last2 = Thomas | first2 = Robin
| doi = 10.1007/BF01215352
| issue = 2
| journal = Combinatorica
| pages = 217–241
| title = Call routing and the ratcatcher
| volume = 14
| year = 1994}}.
{{refend}}

[[Category:Trees (graph theory)]]
[[Category:Graph minor theory]]
[[Category:Graph invariants]]
[[Category:Matroid theory]]

formulasearchengine - User contributions [en]

Portal:Geometry/Selected article/6