0
$\begingroup$

I've learnt during graph algorithms studies that if a treewidth of a graph is greater than k+1 then there's no feedback vertex set of size k in this graph. I would like to understand why...I mean, I understand that if it's enough to remove k vertices to make the grapy acyclic, so there must be a tree composition whose width is at most k,. but I cant fully understand the connection. Can someone please elaborate it? Thanks in advance

$\endgroup$
  • 1
    $\begingroup$ What is the treewidth of an acyclic graph? How does the treewidth change when you delete (or add) a vertex from/to a graph? $\endgroup$ – Tom van der Zanden Nov 29 '17 at 15:43
  • $\begingroup$ Treewidth of an acyclic graph is either 1 if it's connected, too (since acyclic and connected graph is actually a tree...) And if it's a forest...hmm, what's the treewidth of a forest? And when you delete a vertex from the graph, the treewidth might improve up to 1 vertex, right? Makes sense? $\endgroup$ – DanielY Nov 29 '17 at 19:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.