treewidth

abbr: tw

tags: tree decomposition

equivalent to: branch width, mm-width

providers: ISGCI, PACE, PACE

Relations

Results

• 2015 Parameterized Algorithms by Cygan, Fomin, Kowalik, Lokshtanov, Marx, Pilipczuk, Pilipczuk, Saurabh
  • 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.
• 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
  • page 17 : graph class complete has unbounded treewidth – Theorem 2.2
  • page 17 : graph class grid has unbounded treewidth – Theorem 2.4
  • page 49 : carving-width upper bounds treewidth by a linear function – Theorem 5.5 (tw $\prec$ carw) Tree-width is bounded by carving-width.
• 2008 Simulating Quantum Computation by Contracting Tensor Networks by Markov, Shi
  • page 11 : contraction complexity upper bounds treewidth by a linear function – Proposition 4.2. … $cc(G)=tw(G^)$ … Lemma 4.4. $(tw(G) - 1)/2 \le tw(G^) \le \Delta(G)(tw(G) + 1) - 1.$
• 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 computable 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 : outerplanar upper bounds treewidth by a constant – 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
  • page 6 : treewidth upper bounds NLC-width by an exponential function – Theorem 2.5. For each partial $k$-tree $G$ there is a $(2^{k+1}-1)$-NLC tree $J$ with $G=unlab(J)$.
• 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)$.
• 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”).
• 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$.
• 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 linear function
  • treewidth upper bounds tree-independence number by a computable function
• assumed
  • degree treewidth upper bounds treewidth by a linear function – by definition
  • treewidth is equivalent to treewidth – assumed