سؤال

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?

لا يوجد حل صحيح

مرخصة بموجب: CC-BY-SA مع الإسناد
لا تنتمي إلى cs.stackexchange
scroll top