I'm trying to come up with a list of rules that return an equivalent instance to the following problem, while eliminating all vertices of degree 2 or less from the graph:

Given a graph $G=(V,E)$, the goal is to know if there's a set $S\subseteq V$ of size at most $k$ such that $G-S$ is an Almost Forest.

An almost forest is a graph where every component is either a tree or a cycle.

So given any graph (multi-graph) and $k$: $(G,k)$

I know I can remove any component that's either a tree or a cycle, that includes isolated vertices and the graph obtained has a solution $S\subseteq V'$ of size at most $k$ iff the original graph has a solution of size at most $k$.

That eliminates all vertices of degree 0.

The problem with vertices of degree 1(leaves) is:

Suppose $v\in V$ is a leaf and let $u\in V$ be it's only neighbor. if $u$ is part of a cycle $C$ then $C$ is not a component so we must remove either $v$ or a vertex from $C$ to obtain an almost forest. If we delete $v$ we obtain a cycle(and possibly other vertices attached to it, and chords within it). If $C$ becomes a component then this is the best we could've done and picking $v$ was a smart choice so we reduce it to $(G-v,k-1)$. But if $C$ still has chords for example within it, it might have been smarter to delete some other vertex from $C$ that is an endpoint of the chord in $C$, so the reduction performed by picking $v$ is incorrect. Also as stated before $v$ might actually be a part of the solution so it definitely is not correct to reduce the instance to $(G-v,k)$. It seems as if it's impossible to remove leaves..

I'd love any ideas I can get..

  • $\begingroup$ cs.stackexchange.com/q/141786/755 $\endgroup$
    – D.W.
    Commented Jul 10, 2021 at 22:46
  • $\begingroup$ @D.W. I'm not asking the same thing. This is the same problem but I'm not talking about runtime complexity or an algorithm to solve the problem. $\endgroup$
    – giorgioh
    Commented Jul 11, 2021 at 5:50
  • $\begingroup$ Yes, thank you, I'm aware - that's why it is not marked as a duplicate. $\endgroup$
    – D.W.
    Commented Jul 11, 2021 at 6:36


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.