Skip to main content

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
4 votes
3 answers
203 views

MSOL and Courcelle's theorem for maximum clique

The Clique Problem is known to be NP-complete but is known to be fixed-parameter-tractable (FPT) if the treewidth of the underlying graph is fixed. The traditional proof is by a dynamic programming ...
Lisa E.'s user avatar
  • 537
1 vote
1 answer
77 views

MSOL for a vertex-cover enlargement problem

Consider the following problem. Given a graph $G=(V,E)$, and two positive integers $k$ and $\gamma$, decide if there is a set of new edges to be added such that $|E'|\le k$, and any subset $V'\...
Lisa E.'s user avatar
  • 537
2 votes
0 answers
22 views

Tree width given path decomposition

I have a family of graphs whose path decompositions I know. Is it possible to compute the tree-width of these graphs in polynomial time?
Lisa E.'s user avatar
  • 537
1 vote
0 answers
28 views

Minimum number of vertices in a tree with pathwidth $h$?

Let $\mathcal{T}_h$ be the set of trees with pathwidth $h$. What is the minimum,$|V(T)|$ over all $T \in \mathcal{T}_h$. I'm guessing this is a fairly easy question. We know that a complete binary ...
Harry Vinall-Smeeth's user avatar
1 vote
1 answer
32 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 ...
Balchandar Reddy's user avatar
2 votes
0 answers
102 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 ...
Eric_'s user avatar
  • 465
2 votes
1 answer
84 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 ...
Benicio Agüero's user avatar
0 votes
0 answers
27 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 ...
Nestor Mermoz Thea's user avatar
1 vote
1 answer
54 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 ...
user20519169's user avatar
0 votes
1 answer
115 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 ...
mehrnoosh's user avatar
0 votes
1 answer
33 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 ...
Gorid's user avatar
  • 145
1 vote
0 answers
34 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{...
Yuhang Bai's user avatar
2 votes
1 answer
541 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 ...
Tami H's user avatar
  • 39
-3 votes
1 answer
164 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 ...
John19's user avatar
  • 63
5 votes
1 answer
162 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....
Hao S's user avatar
  • 93
3 votes
0 answers
108 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 ...
NayCey's user avatar
  • 111
5 votes
3 answers
742 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 ...
Matteo's user avatar
  • 51
3 votes
3 answers
163 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?
rumetalmI's user avatar
5 votes
1 answer
167 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 ...
SmeltQuake's user avatar