59

If you really want to know what led Neil Robertson and me to tree-width, it wasn't algorithms at all. We were trying to solve Wagner's conjecture that in any infinite set of graphs, one of them is a minor of another, and we were right at the beginning. We knew it was true if we restricted to graphs with no k-vertex path; let me explain why. We knew all such ...


25

It appears the problem is in L by [EJT10] and thus L-complete under $\text{NC}^1$ reducibility by [CM87]. See page 2 of [EJT10]: Applying Theorem I.3 to the formula $\phi(X)$ expressing that $X$ is a simple path from $s$ to $t$ shows that the problem $\{(G,s,t) \text{ } | \text{ tw$(G) \leq k$, there is a path from $s$ to $t$ in $G$}\}$ lies in L ...


19

As far as I know, the state of the art is what is reported in Hans L. Bodlaender, Fedor V. Fomin, Arie M. C. A. Koster, Dieter Kratsch, and Dimitrios M. Thilikos (2012), "On exact algorithms for treewidth", ACM Transactions on Algorithms 9 (1): A12, doi:10.1145/2390176.2390188. The methods described there include an implemented $O^*(2^n)$ algorithm with ...


18

Being 4-colorable? Certainly MSO, and trivial on planar graphs. It's NP-complete for a large enough forbidden clique minor, by reduction to planar 3-colorability.


16

Most algorithms for graphs of bounded treewidth are based on some form of dynamic programming. For these algorithms to be efficient, we need to bound the number of states in the dynamic programming table: if you want a polynomial-time algorithm, then you need a polynomial number of states (e.g., n^tw), if you want to show that the problem is FPT, you usually ...


16

Treewidth is NP-hard to compute on co-bipartite graphs, indeed the original NP-hardness proof of treewidth of Arnborg et al. shows this. Additionally, Bodlaender and Thilikos showed that it is NP-hard to compute the treewidth of graphs of maximum degree $9$. Finally, for any graph of treewidth at least $2$, subdividing an edge (i.e, replacing the edge by a ...


15

An (optimal) $r$-domination for $G$ is an (optimal) domination for the $r$th power $G^r$ and vice versa ($G^r$ is obtained from $G$ by adding new edges between distinct vertices of distance at most $r$). The following facts are well known: (1) All powers of a strongly chordal graph are strongly chordal (A. Lubiw, Master thesis; see also Dahlhaus & ...


15

It is indeed true that every graph $G$ with no $K_{1,k}$ minor has treewidth at most $k-1$. We prove this below, first a few definitions: Let $tw(G)$ be the treewidth of $G$ and $\omega(G)$ be the maximum size of a clique in $G$. A graph $H$ is a triangulation of $G$ if $G$ is a subgraph of $H$ and $H$ is chordal (i.e has no induced cycles on at least $4$ ...


15

You can recursively decompose each triangle into a smaller triangle and a trapezoid, and each trapezoid into two smaller triangles. The corresponding tree decomposition (whose bags contain the corners of a triangle at one level of the decomposition and a triangle or trapezoid at the next or previous level) has five vertices per bag and therefore has width ...


14

I believe that the universal graphs for trees constructed by Chung and Graham 1983 have treewidth $\Theta(\log n)$. Or for a slightly simpler but similar example consider the transitive closures of balanced binary trees. However, there's a negative result here, too. All the examples you give of interesting graph families are minor-closed, or very closely ...


13

You don't need to calculate the variance to prove the concentration of tw(G(n,p)) around its expectation. If two graphs G' and G differ by one vertex then their treewidth differs by at most one. You can use the standard method, the Hoeffding-Azuma inequality applied to the vertex exposure martingale to show, for example, $\mathbb{P}( | tw(G(n,p)) - \mathbb{...


13

In Sparse obstructions and exact treewidth determination, Lucena states that in the PhD thesis of Sanders, "75 or so minimal forbidden minors for treewidth $\leq 4$ are given, and it is believed though not proven that this may constitute the entire obstruction set."


13

As far as I know the NP-completeness of computing the treewidth of a planar graph is still open. The most recent reference I know is a survey by Bodlaender from 2012 called `Fixed-Parameter Tractability of Treewidth and Pathwidth' that appeared in the festschrift for Mike Fellows' 65th birthday. The problem is listed in the conclusion of the survey.


12

TSP is the optimization version of HAMILTONIAN CYCLE, which can be expressed by an MSO-formula (Monadic Second-Order Logic) with edge-set quantifications ($MSO_2$, also known as MSO in the incidence-graph model) as follows: Let $hamilton(F)$ express that $F$ is a set of edges of the input graph $G = (V, E)$ such that every vertex is incident to exactly two ...


12

See the paper by Julia Chuzhoy and myself on Treewidth sparsifiers. We show that one can obtain a subgraph of degree at most 3 with treewidth $\Omega(k/polylog(k))$ where $k$ is the treewidth of $G$. https://arxiv.org/abs/1410.1016 The proof is shorter than the one for grid minors but it is still not that that easy and builds on several previous tools. ...


11

The concept of exploiting properties that a graph possesses locally can be taken even further. Dawar, Grohe and Kreutzer in Locally Excluding a Minor considered classes of graphs that locally exclude a minor and Dvorak, Kral and Thomas in Deciding first-order properties for sparse graphs considered classes of graphs that have (locally) bounded expansion. ...


11

My suggestion would be to look carefully at Courcelle's theorem, that problems expressible in (certain extensions of) monadic second order logic have FPT algorithms when parameterized by treewidth. My suspicion is that this covers many or most of the known examples of FPT problems for these graphs. In this view, your local/global distinction seems to be ...


10

The problem is still NP-complete. Here's a reduction from the Treewidth problem on general graphs. Recall that for a graph G of treewidth at least two, the treewidth is not affected when subdividing an edge by a degree-2 vertex (i.e. replacing an edge $\{u,v\}$ by a new vertex $x$ and edges $\{u,x\}$, $\{x,v\}$ ). Given an input graph $G$ on $n$ vertices, ...


10

As far as I know, dynamic programming does the trick Klein's paper on TSP for planar graphs has the details for planar graphs with bounded tree-width. If the graph is not planar, the dynamic program is slower (dependency on the tree-width is worse). Philip N. Klein: A Linear-Time Approximation Scheme for TSP in Undirected Planar Graphs with Edge-Weights. ...


10

Not really an answer but the closest references I am aware of. There are results available for branch-width. Also, there is at least one empirical study of treewidth of industrial instances. Discovering treewidth, H. Bodlaender, 2005. Gives algorithms to compute bounds on treewidth. Treewidth in Industrial SAT Benchmarks, R. Mateescu, 2011. Uses variations ...


10

I wrote a paper called A Fast Parallel Branch and Bound Algorithm for Treewidth, in ICTAI 2011. It can compute treewidth in multi-core. I used lots of heuristics and spent lots of time refining the program. I was a random undergraduate student in China and didn't make it to a good conference. But based on my experiment results, I think my program is very ...


10

On this page a theorem is mentioned that provides such classes: Theorem (Scheffler [1]) If $G$ is the intersection graph of connected subgraphs of another graph $H$, then $tw(G)\leq tw(H)\omega(G)-1$. This generalizes the bound for chordal graphs (for which $H$ is a tree) and also applies to circular-arc graphs (then $H$ is a cycle). I do not know if other ...


10

See "Decomposition by clique separators", Robert E. Tarjan, Discrete Mathematics 55 (2): 221–232, 1985. If I understand correctly, your notion of width is essentially the size of the largest piece in Tarjan's decomposition.


10

Indeed, using the resultss in Elberfeld-Jakoby-Tantau-2010 one can show that SAT can be decided in logspace on formulas whose incidence graph has bounded treewidth. Here is a sketch of how the main steps of the proof of this claim go. The notions of tree-decomposition and treewidth can be generalized to arbitrary relational structures. See for instance ...


10

The intersection graph of interior disjoint balls in $\mathbb{R}^d$, should have treewidth $O(n^{1-1/d})$, if there is justice in the universe (let me think about it - yep - there is). The treewidth should be $\Theta(n^{1-1/d})$. This family of graphs is contained in the family of graphs of low density graphs in $\mathbb{R}^d$. I have a paper (with Kent ...


9

This is not exactly what you are asking for, but it is very closely related and thus might be nevertheless interesting to you: The concept of local treewidth introduced in M. Frick, M.Grohe, Deciding first-order properties of locally tree-decomposable structures is more general than the definition of locally bounded treewidth in the wikipedia article to ...


9

If G is formed from a smaller graph H that is not a clique by adding two vertices x and y, such that x and y are not adjacent to each other but adjacent to all other vertices of G, then $tw(G)=tw(H)+2$. For, in any tree decomposition of $G$, either $x$ and $y$ have disjoint subtrees or they have overlapping subtrees. If they have disjoint subtrees, all the ...


9

It is quite easy to do dynamic programming on graphs of treewidth $k$ for this problem. One can keep for each vertex in a bag the shortest distance to some vertex in the partial solution and the distance to future solution needed to dominate the undominated vertices. This in total gives a table size of $O(r^k)$ so for fixed $r$ this problem is FPT ...


9

Dawar and Kreutzer have shown that the problem is fixed-parameter tractable on nowhere dense classes of graphs, which includes the planar graphs, the graphs of bounded (local) tree-width and all classes with (locally) excluded minors. Dvorak has shown that there is a polynomial time constant factor approximation for classes of bounded expansion, which ...


9

We now understand that for any fixed bound $k \in \mathbb{N}$ on the treewidth, we can convert any Boolean circuit of treewidth less than $k$ to a so-called d-SDNNF circuit, in linear time and with the dependency on $k$ being singly exponential. The so-called d-SDNNFs are circuits satisfying conditions on the use of negation (only at the leaves), ...


Only top voted, non community-wiki answers of a minimum length are eligible