0
$\begingroup$

I am a research scholar, and I currently work in parameterized algorithms. My current work involves proving that a problem is FPT for the parameter distance to clique. Although it is known that computing a distance to clique of size $k$ can be done in FPT time using a simple branching algorithm, I couldn't figure out how. Please elaborate on this. Once I get this, then I can assume that the distance to clique is given and solve the rest.
For a graph $G = (V, E)$, the parameter distance to clique is the cardinality of the smallest set $D \subseteq V$ such that $V \setminus D$ is a clique.

$\endgroup$
1
  • $\begingroup$ If the distance to clique is 0, then its about solving the problem for a clique. If i assume that for distance to clique it is FPT, then in this case it is polynomial time solvable on clique. @PålGD $\endgroup$ Jan 18, 2023 at 13:10

1 Answer 1

1
$\begingroup$

The distance to clique is the fewest number of vertices to remove such that the resulting graph is a clique.

Let us take the complement graph $\overline G$ of $G$. Now, we instead want to find the fewest number of vertices to remove such that the resulting graph is edgeless.

Recall that if $I$ is edgeless (i.e. an independent set), then $C$ is a vertex cover of $G$. Hence, distance to clique is simply vertex cover in the complement graph.

$\endgroup$

Your Answer

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

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