Parameter: treewidth

Definition:

A tree decomposition of a graph $G$ is a pair $(T, X)$, where $T = (I, F)$ is a tree, and $X = \{X_i \mid i \in I\}$ is a family of subsets of $V(G)$ such that

The width of the tree decomposition is $\max |X_i| - 1$.
The treewidth of a graph is the minimum width over all possible tree decompositions of the graph.

References

[119]
H.L. Bodlaender
A tourist guide through treewidth
Acta Cybernetica 11 1993 1--23
[915]
N. Robertson, P.D. Seymour
Graph minors. II. Algorithmic aspects of tree width
J. Algorithms 7 1986 309--322
[1411]
H.L. Bodlaender
A partial k-arboretum of graphs with bounded treewidth
Theor. Comp. Sci. 209 1-45 (1998)

Equivalent parameters

[+]Details

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

[+]Details

This parameter is a minimal upper bound for

[+]Details

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-Linear [+]Details
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 [+]Details
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 Si, such that whenever two vertices are in the same set Si, they are adjacent.
XP [+]Details
Cochromatic colouring
[?]
(decision variant)
Input: A graph G in this class and an integer k.
Output: True iff the vertices of G can be partitioned into at most k sets, such that each partite set induces either an independent set or a clique in G.
Unknown to ISGCI [+]Details
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 [+]Details
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-Linear [+]Details
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 [+]Details
Graph canonisation
[?]
Input: A graph G in this class.
Output: A graph C(G) such that C(G) = C(H) iff G is isomorphic to H.
XP [+]Details
Graph isomorphism
[?]
Input: Graphs G and H in this class
Output: True iff G and H are isomorphic.
FPT [+]Details
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-Linear [+]Details
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 [+]Details
Independent dominating 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, with |S| <= k, such that every vertex in G is either in S or adjacent to a vertex in S.
Unknown to ISGCI [+]Details
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 [+]Details
Maximum bisection
[?]
(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 of equal size (or |A|=|B|-1 if G has an odd number of vertices) such that there are at least k edges in G with one endpoint in A and the other endpoint in B.
Unknown to ISGCI [+]Details
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-Linear [+]Details
Minimum bisection
[?]
(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 of equal size (or |A|=|B|-1 if G has an odd number of vertices) such that there are at most k edges in G with one endpoint in A and the other endpoint in B.
Unknown to ISGCI [+]Details
Monopolarity
[?]
Input: A graph G in this class.
Output: True iff G is monopolar.
Unknown to ISGCI [+]Details
Polarity
[?]
Input: A graph G in this class.
Output: True iff G is polar.
XP [+]Details
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-Linear [+]Details
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 [+]Details
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 [+]Details
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-Linear [+]Details
Weighted maximum cut
[?]
(decision variant)
Input: A graph G in this class with weight function on the edges and a real k.
Output: True iff the vertices of G can be partitioned into two sets A,B such that the sum of weights of the edges in G with one endpoint in A and the other endpoint in B is at least k.
Unknown to ISGCI [+]Details

Graph classes

Bounded

back to top

Unbounded

back to top

Open

back to top

Unknown to ISGCI

back to top