treewidth
abbr: tw
tags: tree decomposition
equivalent to: branch width, mm-width, treewidth
Relations
Other | Relation from | Relation to |
---|---|---|
acyclic chromatic number | exclusion | upper bound |
arboricity | exclusion | upper bound |
average degree | exclusion | upper bound |
average distance | exclusion | exclusion |
bandwidth | upper bound | exclusion |
bipartite | unbounded | exclusion |
bipartite number | exclusion | unknown to HOPS |
bisection bandwidth | exclusion | exclusion |
block | unbounded | exclusion |
book thickness | exclusion | upper bound |
boolean width | exclusion | upper bound |
bounded components | upper bound | exclusion |
boxicity | exclusion | upper bound |
branch width | upper bound | upper bound |
c-closure | exclusion | exclusion |
carving-width | upper bound | exclusion |
chordal | unbounded | exclusion |
chordality | exclusion | upper bound |
chromatic number | exclusion | upper bound |
clique cover number | exclusion | exclusion |
clique-tree-width | exclusion | upper bound |
clique-width | exclusion | upper bound |
cluster | unbounded | exclusion |
co-cluster | unbounded | exclusion |
cograph | unbounded | exclusion |
complete | unbounded | exclusion |
connected | unbounded | unknown to HOPS |
cutwidth | upper bound | exclusion |
cycle | constant | exclusion |
cycles | constant | exclusion |
d-path-free | upper bound | exclusion |
degeneracy | exclusion | upper bound |
degree treewidth | upper bound | exclusion |
diameter | exclusion | exclusion |
diameter+max degree | upper bound | exclusion |
disjoint cycles | constant | exclusion |
distance to bipartite | exclusion | exclusion |
distance to block | exclusion | exclusion |
distance to bounded components | upper bound | exclusion |
distance to chordal | exclusion | exclusion |
distance to cluster | exclusion | exclusion |
distance to co-cluster | exclusion | exclusion |
distance to cograph | exclusion | exclusion |
distance to complete | exclusion | exclusion |
distance to edgeless | upper bound | exclusion |
distance to forest | upper bound | exclusion |
distance to interval | exclusion | exclusion |
distance to linear forest | upper bound | exclusion |
distance to maximum degree | exclusion | exclusion |
distance to outerplanar | upper bound | exclusion |
distance to perfect | exclusion | exclusion |
distance to planar | exclusion | exclusion |
distance to stars | upper bound | exclusion |
domatic number | exclusion | upper bound |
domination number | exclusion | exclusion |
edge clique cover number | exclusion | exclusion |
edge connectivity | exclusion | upper bound |
edgeless | constant | exclusion |
feedback edge set | upper bound | exclusion |
feedback vertex set | upper bound | exclusion |
forest | constant | exclusion |
genus | exclusion | exclusion |
girth | exclusion | exclusion |
grid | unbounded | exclusion |
h-index | exclusion | exclusion |
inf-flip-width | exclusion | upper bound |
interval | unbounded | exclusion |
iterated type partitions | exclusion | exclusion |
linear clique-width | exclusion | unknown to HOPS |
linear forest | constant | exclusion |
linear NLC-width | exclusion | unknown to HOPS |
linear rank-width | exclusion | unknown to HOPS |
maximum clique | exclusion | upper bound |
maximum degree | exclusion | exclusion |
maximum independent set | exclusion | exclusion |
maximum induced matching | exclusion | exclusion |
maximum leaf number | upper bound | exclusion |
maximum matching | unknown to HOPS | exclusion |
maximum matching on bipartite graphs | upper bound | exclusion |
mim-width | exclusion | upper bound |
minimum degree | exclusion | upper bound |
mm-width | upper bound | upper bound |
modular-width | exclusion | exclusion |
module-width | exclusion | upper bound |
neighborhood diversity | exclusion | exclusion |
NLC-width | exclusion | upper bound |
NLCT-width | exclusion | upper bound |
odd cycle transversal | exclusion | exclusion |
outerplanar | constant | exclusion |
path | constant | exclusion |
pathwidth | upper bound | exclusion |
pathwidth+maxdegree | upper bound | exclusion |
perfect | unbounded | exclusion |
planar | unbounded | exclusion |
radius-r flip-width | exclusion | upper bound |
rank-width | exclusion | upper bound |
shrub-depth | exclusion | unknown to HOPS |
sim-width | exclusion | upper bound |
star | constant | exclusion |
stars | constant | exclusion |
topological bandwidth | upper bound | exclusion |
tree | constant | exclusion |
tree-independence number | unknown to HOPS | upper bound |
treedepth | upper bound | exclusion |
treelength | exclusion | unknown to HOPS |
twin-cover number | exclusion | exclusion |
twin-width | exclusion | upper bound |
vertex connectivity | unknown to HOPS | unknown to HOPS |
vertex cover | upper bound | exclusion |
vertex integrity | upper bound | exclusion |
Results
- 2012 Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics by Ganian
- page 263 : bounded twin-cover number does not imply bounded treewidth – There exists graphs with arbitrarily large twin-cover and bounded tree-width and vice-versa.
- page 263 : bounded treewidth does not imply bounded twin-cover number – There exists graphs with arbitrarily large twin-cover and bounded tree-width and vice-versa.
- 2010 Comparing 17 graph parameters by Sasák
- 2007 Graph Treewidth and Geometric Thickness Parameters by Dujmovic, Wood
- page 5 : treewidth upper bounds arboricity by a linear function – Proposition 2. The maximum arboricity of a graph in $\mathcal T_k$ (ed: $k$-tree) is $k$; …
- page 8 : treewidth upper bounds book thickness by a linear function – The maximum book thickness … of a graph $\mathcal T_k$ (ed: $k$-tree) satisfy … $=k$ for $k \le 2$, $=k+1$ for $k \ge 3$.
- 2005 On the relationship between NLC-width and linear NLC-width by Gurski, Wanke
- page 8 : treewidth upper bounds NLCT-width by a computable function – The results of [23] imply that each graph class of bounded path-width has bounded linear NLC-width and that each graph class of bounded tree-width has bounded NLCT-width.
- 2000 Upper bounds to the clique width of graphs by Courcelle, Olariu
- page 18 : treewidth upper bounds clique-width by an exponential function – We will prove that for every undirected graph $G$, $cwd(G) \le 2^{twd(G)+1}+1$ …
- 1998 A partial $k$-arboretum of graphs with bounded treewidth by Bodlaender
- page 4 : pathwidth upper bounds treewidth by a linear function – Lemma 3. (a) For all graphs $G$, $pathwidth(G) \ge treewidth(G)$. …
- page 34 : graph class outerplanar has constant treewidth – Lemma 78. Every outerplanar graph $G=(V,E)$ has treewidth at most 2.
- page 37 : graph class grid has unbounded treewidth – Lemma 88. The treewidth of an $n \times n$ grid graph … is at least $n$.
- page 38 : treewidth upper bounds minimum degree by a linear function – Lemma 90 (Scheffler [94]). Every graph of treewidth at most $k$ contains a vertex of degree at most $k$.
- 1994 k-NLC graphs and polynomial algorithms by Wanke
- 1993 The Pathwidth and Treewidth of Cographs by Bodlaender, Möhring
- page 4 : graph class complete has unbounded treewidth – Lemma 3.1 (“clique containment lemma”). Let $({X_i\mid u\in I},T=(I,F))$ be a tree-decomposition of $G=(V,E)$ and let $W \subseteq V$ be a clique in $G$. Then there exists $i \in I$ with $W \subseteq X_i$.
- page 4 : graph class bipartite has unbounded treewidth – Lemma 3.2 (“complete bipartite subgraph containment lemma”).
- 1993 On the chordality of a graph by McKee, Scheinerman
- page 5 : treewidth upper bounds chordality by a linear function – Theorem 7. For any graph $G$, $\mathrm{Chord}(G) \le \tau(G)$.
- 1991 Graph minors. X. Obstructions to tree-decomposition by Robertson, Seymour
- page 16 : treewidth upper bounds branch width by a linear function – (5.1) For any hypergraph $G$, $\max(\beta(G), \gamma(G)) \le \omega(G) + 1 \le \max(\lfloor(3/2)\beta(G)\rfloor, \gamma(G), 1)$.
- page 16 : branch width upper bounds treewidth by a linear function – (5.1) For any hypergraph $G$, $\max(\beta(G), \gamma(G)) \le \omega(G) + 1 \le \max(\lfloor(3/2)\beta(G)\rfloor, \gamma(G), 1)$.
- 1986 Graph minors. II. Algorithmic aspects of tree-width by Robertson, Seymour
- page 1 : treewidth – A \emph{tree-decomposition} of $G$ is a family $(X_i \colon i\in I)$ of subsets of $V(G)$, together with a tree $T$ with $V(T)=I$, with the following properties. (W1) $\bigcup(X_i \colon i \in I)=V(G)$. (W2) Every edge of $G$ has both its ends in some $X_i$ ($i \in I$). (W3) For $i,j,k \in I$, if $j$ lies on the path of $T$ from $i$ to $k$ then $X_i \cap X_k \subseteq X_j$. The \emph{width} of the tree-decomposition is $\max(|X_i|-1 \colon i \in I)$. The tree-width of $G$ is the minimum $w \ge 0$ such that $G$ has a tree-decomposition of width $\le w$.
- page 1 : treewidth – Equivalently, the tree-width of $G$ is the minimum $w \ge 0$ such that $G$ is a subgraph of a ``chordal’’ graph with all cliques of size at most $w + 1$.
- https://en.wikipedia.org/wiki/Treewidth
- treewidth – …, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree.
- assumed
- degree treewidth upper bounds treewidth by a linear function – by definition
- https://www.mimuw.edu.pl/~malcin/book/parameterized-algorithms.pdf
- treewidth – Very roughly, treewidth captures how similar a graph is to a tree. There are many ways to define ``tree-likeness’’ of a graph; … it appears that the approach most useful from algorithmic and graph theoretical perspectives, is to view tree-likeness of a graph $G$ as the existence of a structural decomposition of $G$ into pieces of bounded size that are connected in a tree-like fashion. This intuitive concept is formalized via the notions of a tree decomposition and the treewidth of a graph; the latter is a quantitative measure of how good a tree decomposition we can possibly obtain.
- unknown source
- distance to outerplanar upper bounds treewidth by a linear function – After removal of $k$ vertices the remaining class has a bounded width $w$. So by including the removed vertices in every bag, we can achieve decomposition of width $w+k$
- treewidth upper bounds book thickness by a computable function
- treewidth upper bounds mm-width by a computable function
- mm-width upper bounds treewidth by a computable function
- treewidth upper bounds boolean width by a computable function
- treewidth upper bounds tree-independence number by a computable function