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?


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.