Questions tagged [treewidth]

Treewidth is a graph parameter which measures how close the graph is to a tree (smaller is better). Many problems can be solved more efficiently on graphs with bounded treewidth, using dynamic programming.

Filter by
Sorted by
Tagged with
0 votes
1 answer
25 views

Does FPT allow for doubling the parameter?

I have recently come across a result that showed that a given problem is in FPT when parameterized by the treewidth of a graph. However, they did this by showing that the problem is in FPT when ...
user avatar
  • 145
0 votes
0 answers
21 views

The length of the formula in Monadic second-order logic

The Courcelle's theorem as following: Obviously, we need the length of the $\varphi$~(that is $||\varphi||$)~in Theorem. However, how to caculate the length of $\varphi$? For example, $$\begin{...
user avatar
2 votes
1 answer
306 views

Dynamic Programming for Feedback Vertex Set - bounded treewidth

Saw it on another post that there is a way of solving FVS in polynomial time if the treewidth is constant, using dynamic programming?... If I'm given the treewidth of a graph, how do I solve it in ...
user avatar
  • 39
-3 votes
1 answer
152 views

If G has no simple path on x vertices ,then the treewidth of G is upper bounded by x

Statement: If G has no simple path on x vertices ,then the treewidth of G is upper bounded by x. Hint: Begin by computing a DFS tree, and prove an upper bound on its height. I am supposed to prove the ...
user avatar
  • 73
4 votes
1 answer
109 views

Is there a graph theory textbook that covers treewidth thoroughly?

Can someone recommend a graph theory textbook that covers treewidth thoroughly? Something that focuses on the graph-theoretic structure of bounded treewidth graphs rather than solving problems on them....
user avatar
  • 83
3 votes
0 answers
61 views

Bounded treewidth implies bounded clique-width

We have a graph G of treewidth $\operatorname{tw}(G)\leq k$, for some $k\in\mathbb{N}$. I've seen a claim that that implies that the clique-width of the same graph is at most $k \cdot 2^k$. This ...
user avatar
  • 91
4 votes
2 answers
357 views

Size of tree decomposition

Given a graph $G$ with $n$ vertices, let $(X, T)$ be a tree decomposition of $G$ with the smallest width. Is the number of nodes in $T$ upper bounded by $n$? I have googled it but all materials I ...
user avatar
  • 41
3 votes
3 answers
83 views

treewidth of a given graph

Is the treewidth of this graph equal to 2? I have tried to prove it through the definition of a tree decomposition. If its not correct can someone give any hints?
user avatar
5 votes
1 answer
142 views

How does treewidth behave under graph minor operations?

It is a well-known fact that for any minor H of a graph G (commonly written as $H \leq_m G$), the treewidth of H is smaller than or equal to that of G. Minors of a graph are created through the ...
user avatar