1
$\begingroup$

It is known that finding an independent set (or a clique) of size at least $k$ in a graph is $W[1]$ hard, so it is unlikely that there is $f(k)\cdot n^{O(1)}$ time algorithm for finding an independent set of size greater than equal to $k$.

I was looking at the complementary problem - "Whether or not removal of at most $k$ vertices from a graph can make the resulting graph an independent set".

If the input graph $G$ contains a set $W$ of size at most $k$ for which $V(G)\setminus W$ is independent set, then it can be found in $2^{O(k \log k)}\cdot n^{O(1)}$ time as follows:

  1. Since vertices of independent set have degree at most $k$, we first remove from $G$ all vertices whose degree is more than $k$.
  2. There are now only $k^2$ edges in the current graph.
  3. Let $A$ be set of all vertices on which at least one edge is incident, then $V(G)\setminus A$ is an independent set of size at least $(n-2k^2)$.
  4. So $W$ must be contained in set $A$ whose size is at most $2k^2$. We can scan over all ${2k^2}\choose{k}$ subsets of A to check removal of which set makes the graph an independent set.

My question is does the new problem has $2^{O(k)}\cdot n^{O(1)}$ time algorithm?

$\endgroup$
  • $\begingroup$ The complementary problem is called vertex cover, and the parameterized vertex cover has been widely studied. You can find many results by google $\endgroup$ – Bangye Mar 13 '18 at 13:57
2
$\begingroup$

Yes, and the algorithm is straight forward branching.

Suppose that you are given a graph $G$ and an integer $k$. If $k = 0$, we simply return whether $G$ is an independent set. If $G$ is an independent set, we return "yes". Otherwise, we branch. If there is an edge $uv$ in $G$, we recurse on $G-u, k-1$ and $G-v, k-1$. Since the budget drops with one for every recursive call, we call ourselves at most $2^k$ times.

The correctness is left as an exercise.

$\endgroup$
1
$\begingroup$

Since complement of vertex cover is independent set, and there is $2^{O(k)}\cdot n^{O(1)}$ time algorithm for finding vertex cover of size at most $k$, it will imply $2^{O(k)}\cdot n^{O(1)}$ time algorithm for the problem considered.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.