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.
15
questions
0
votes
1
answer
23
views
Use of the degree variable in an MSOL formula
I am working on giving an MSOL formula for an NP-hard problem; this proves that the problem is linear-time solvable on bounded treewidth graphs. Given a graph $G = (V, E)$, the problem would be to ...
- 162
2
votes
0
answers
95
views
On definitions of graph width
Wikipedia shows graph width $k$ as the degeneracy, an ordering of the vertices $v_1,\ldots , v_k$ for which, if we orient each edge $(v_i, v_j)$ towards $i$ where $i<j$, the maximal degree is at ...
- 435
1
vote
1
answer
54
views
Clarifications about tree-width definition
I have read the definition of treewidth/tree-decomposition both in Wikipedia and in here:
https://medium.com/@karlrombauts/treewidth-how-all-graphs-are-trees-in-disguise-ec699b69e2fb
I'm finding ...
- 125
0
votes
0
answers
26
views
Tree Width of Directed Graph
I'm Nestor Mermoz Thea. I have two definition over the Directed strong pseudoforest and Directed weak pseudoforest that I don't really well understand.
Directed weak pseudoforest: A directed weak ...
1
vote
1
answer
44
views
Relationships between path width and clique size of interval graphs
I faced the following claim on wikiepdia about interval graphs (https://en.wikipedia.org/wiki/Interval_graph):
The pathwidth of an interval graph is one less than the size of its maximum clique.
I ...
- 13
0
votes
1
answer
73
views
Treewidth of a subdivision of a graph
Let $G$ be a graph and $G_s$ its $s$-subdivision, i.e. the graph obtained from $G$ by subdividing each edge $s$ times.
Why is the treewidth of $G$ the same as the treewidth of $G_s$?
(Subdividing an ...
- 11
0
votes
1
answer
31
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 ...
- 145
0
votes
0
answers
26
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{...
- 49
2
votes
1
answer
453
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 ...
- 39
-3
votes
1
answer
160
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 ...
- 63
4
votes
1
answer
135
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....
- 83
3
votes
0
answers
94
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 ...
- 111
5
votes
2
answers
567
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 ...
- 51
3
votes
3
answers
138
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?
- 43
5
votes
1
answer
153
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 ...
- 53