1
$\begingroup$

The problem of $k$-Almost Independent Set is to decide whether or not $(G,m)$ where $G$ is a graph and $m \in \mathbb{N}$ has a subset of $m$ vertices that induces a subgraph with at most $k$ edges. I know that Independent Set reduces to $k$-Almost Independent Set in a natural way (adding k pairs of vertices each joined by an edge). Is there a natural reduction in the reverse direction?

$\endgroup$

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.