3
$\begingroup$

I've looked at the feedback vertex set and thought about connecting the problem to finding vertex disjoint cycles.

My first thought was that if there are at most k vertex disjoint cycles in a graph, then k is a bound for the feedback vertex set problem and there is a subset of k vertices satisfying the requirement (i.e. there exists a subset of size k s.t. the graph without the subset is cycle-free)

However, I easily found this example that refutes it: graph example

Here there is only 1 disjoint cycle, but we have to remove 2 vertices from the graph to obtain a cycle free graph.

My question is, can we find a bound for the feedback vertex set problem by looking at disjoint cycles? (for example, for graphs with at most k disjoint cycles the feedback vertex set is bounded by 2k, or maybe even by k+1 as I've shown here)

P.S. I'm asking specifically about digraphs.

$\endgroup$
  • $\begingroup$ It's a pretty good lower bound -- you must select at least one vertex from each disjoint cycle. Getting an upper bound seems harder. $\endgroup$ – j_random_hacker May 7 '18 at 14:02

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.