Parameter: branchwidth

Definition:

A branch decomposition of a graph $G$ is a pair $(T,\chi),ドル where $T$ is a binary tree and $\chi$ is a bijection, mapping leaves of $T$ to edges of $G$. Any edge $\{u, v\}$ of the tree divides the tree into two components and divides the set of edges of $G$ into two parts $X, E \backslash X,ドル consisting of edges mapped to the leaves of each component. The width of the edge $\{u,v\}$ is the number of vertices of $G$ that is incident both with an edge in $X$ and with an edge in $E \backslash X$. The width of the decomposition $(T,\chi)$ is the maximum width of its edges. The branchwidth of the graph $G$ is the minimum width over all branch-decompositions of $G$.

References

[922]

N. Robertson, P.D. Seymour
Graph minors. X. Obstructions to tree--decomposition
J. Comb. Theory (B) 52 1991 153--190

[1699]

R. Sasák
Comparing 17 graph parameters
Master's thesis, University of Bergen 2010

Equivalent parameters

Only references for direct inclusions are given. Where no reference is given for an equivalent parameter, check other equivalent parameters.

treewidth
[922]
N. Robertson, P.D. Seymour
Graph minors. X. Obstructions to tree--decomposition
J. Comb. Theory (B) 52 1991 153--190

Relations

Minimal/maximal is with respect to the contents of ISGCI. Only references for direct bounds are given. Where no reference is given, check equivalent parameters.

Minimal upper bounds for this parameter

carvingwidth (possibly equal)
distance to outerplanar (possibly equal)
pathwidth (possibly equal)

This parameter is a minimal upper bound for

book thickness (possibly equal)
booleanwidth (possibly equal)
cliquewidth (possibly equal)
rankwidth (possibly equal)

Problems

Problems in italics have no summary page and are only listed when ISGCI contains a result for the current parameter.

3-Colourability

[?]

Input: A graph G in this class.

Output: True iff each vertex of G can be assigned one colour out of 3 such that whenever two vertices are adjacent, they have different colours.

FPT

FPT from FPT-Linear on cliquewidth
FPT from FPT-Linear on treewidth

Clique

[?]

Input: A graph G in this class and an integer k.

Output: True iff G contains a set S of pairwise adjacent vertices, with |S| >= k.

FPT

FPT on cliquewidth
XP on maximum clique [by definition]

Clique cover

[?]

Input: A graph G in this class and an integer k.

Output: True iff the vertices of G can be partitioned into k sets S_i, such that whenever two vertices are in the same set S_i, they are adjacent.

XP on cliquewidth

[1714]

W. Espelage, F. Gurski, E. Wanke
How to solve NP-hard graph problems on clique-width bounded graphs in polynomial time
Proceedings of the 27th International Workshop on Graph-Theoretic Concepts in Computer Science WG'01, LNCS 2204, 117-128 (2001)

Colourability

[?]

Input: A graph G in this class and an integer k.

Output: True iff each vertex of G can be assigned one colour out of k such that whenever two vertices are adjacent, they have different colours.

FPT

FPT on cliquewidth

Domination

[?]

Input: A graph G in this class and an integer k.

Output: True iff G contains a set S of vertices, with |S| <= k, such that every vertex in G is either in S or adjacent to a vertex in S.

FPT

FPT from FPT-Linear on cliquewidth
FPT from FPT-Linear on treewidth
FPT on booleanwidth

[1701]

M. Vatshelle
New Width Parameters of Graphs
PhD Thesis, Dept. of Informatics, University of Bergen 2012

FPT

[1701]

M. Vatshelle
New Width Parameters of Graphs
PhD Thesis, Dept. of Informatics, University of Bergen 2012

Feedback vertex set

[?]

Input: A graph G in this class and an integer k.

Output: True iff G contains a set S of vertices, with |S| <= k, such that every cycle in G contains a vertex from S.

FPT

FPT on cliquewidth
FPT on treewidth

[1582]

B. Courcelle, S. Oum
Vertex-minors, monadic second-order logic and a conjecture by Seese
J. Comb. Theory (B) 97 91-126 (2007)

Graph isomorphism

[?]

Input: Graphs G and H in this class

Output: True iff G and H are isomorphic.

FPT

FPT on treewidth

[1737]

D. Lokshktanov, M. Pilipczuk, M. Pilipczuk, S. Saurabh
Fixed-Parameter-Tractable canonization and isomorphism test for graphs of bounded treewidth
55th IEEE Annual Symposium on Foundations of Computer Science FOCS-2014 186-195 (2014)

XP on rankwidth

[1763]

M. Grohe, P. Schweitzer
Isomorphism Testing for Graphs of Bounded Rank Width
Proc. of 55th Annual IEEE Symposium on Foundations of Computer Science FOCS (2015)

XP on treewidth

[1701]

M. Vatshelle
New Width Parameters of Graphs
PhD Thesis, Dept. of Informatics, University of Bergen 2012

Hamiltonian cycle

[?]

Input: A graph G in this class.

Output: True iff G has a simple cycle that goes through every vertex of the graph.

FPT

FPT from FPT-Linear on treewidth
XP on cliquewidth

[1714]

[1715]

R. Ganian, P. Hlineny, J. Obdrzalek
Clique-width: When hard does not mean impossible
Symposium on Theoretical Aspects of Computer Science STACS 2011, Leibniz International Proceedings in Informatics LIPIcs Vol 9, Dagstuhl 404-415 (2011)

Hamiltonian path

[?]

Input: A graph G in this class.

Output: True iff G has a simple path that goes through every vertex of the graph.

FPT

FPT on treewidth

[1701]

M. Vatshelle
New Width Parameters of Graphs
PhD Thesis, Dept. of Informatics, University of Bergen 2012

XP on cliquewidth

[1714]

[1715]

XP on rankwidth

[1701]

M. Vatshelle
New Width Parameters of Graphs
PhD Thesis, Dept. of Informatics, University of Bergen 2012

Independent set

[?]

Input: A graph G in this class and an integer k.

Output: True iff G contains a set S of pairwise non-adjacent vertices, such that |S| >= k.

FPT

FPT on cliquewidth

[1716]

F. Gurski
A comparison of two approaches for polynomial time algorithms computing basic graph parameters
Manuscript 2008

Maximum cut

[?]

(decision variant)

Input: A graph G in this class and an integer k.

Output: True iff the vertices of G can be partitioned into two sets A,B such that there are at least k edges in G with one endpoint in A and the other endpoint in B.

FPT

FPT from FPT-Linear on treewidth
XP on cliquewidth

[1735]

E. Wanke
k-NLC graphs and polynomial algorithsm
Discrete Appl. Math. 54 No.2 251-266 (1994)

Monopolarity

[?]

Input: A graph G in this class.

Output: True iff G is monopolar.

Unknown to ISGCI

Polarity

[?]

Input: A graph G in this class.

Output: True iff G is polar.

XP on cliquewidth

[1764]

V.B. Le, R. Nevries
Complexity and algorithms for recognizing polar and monopolar graphs
Theoretical Computer Science 528 1-11 (2014)

XP on treewidth

[1764]

V.B. Le, R. Nevries
Complexity and algorithms for recognizing polar and monopolar graphs
Theoretical Computer Science 528 1-11 (2014)

Weighted clique

[?]

Input: A graph G in this class with weight function on the vertices and a real k.

Output: True iff G contains a set S of pairwise adjacent vertices, such that the sum of the weights of the vertices in S is at least k.

FPT

FPT from FPT-Linear on treewidth
FPT on cliquewidth
FPT on degeneracy

[1849]

(no preview available)

XP on maximum clique [by definition]

Weighted feedback vertex set

[?]

Input: A graph G in this class with weight function on the vertices and a real k.

Output: True iff G contains a set S of vertices, such that the sum of the weights of the vertices in S is at most k and every cycle in G contains a vertex from S.

FPT

FPT from FPT-Linear on cliquewidth
FPT on rankwidth

[1701]

M. Vatshelle
New Width Parameters of Graphs
PhD Thesis, Dept. of Informatics, University of Bergen 2012

FPT on treewidth

[1701]

M. Vatshelle
New Width Parameters of Graphs
PhD Thesis, Dept. of Informatics, University of Bergen 2012

Weighted independent dominating set

[?]

Input: A graph G in this class with weight function on the vertices and a real k.

Output: True iff G contains a set S of pairwise non-adjacent vertices, with the sum of the weights of the vertices in S at most k, such that every vertex in G is either in S or adjacent to a vertex in S.

FPT

FPT from FPT-Linear on cliquewidth

Weighted independent set

[?]

Input: A graph G in this class with weight function on the vertices and a real k.

Output: True iff G contains a set S of pairwise non-adjacent vertices, such that the sum of the weights of the vertices in S is at least k.

FPT

FPT from FPT-Linear on cliquewidth
FPT from FPT-Linear on treewidth
FPT on booleanwidth

[1701]

M. Vatshelle
New Width Parameters of Graphs
PhD Thesis, Dept. of Informatics, University of Bergen 2012

FPT

[1701]

M. Vatshelle
New Width Parameters of Graphs
PhD Thesis, Dept. of Informatics, University of Bergen 2012

Parameter: branchwidth

References

Equivalent parameters

Relations

Minimal upper bounds for this parameter

This parameter is a minimal upper bound for

Problems

Graph classes

Bounded

Unbounded

Open

Unknown to ISGCI