0
$\begingroup$

I am Balchandar Reddy, a research scholar. I am currently working on the parameterized complexity of a problem for the parameter clique width. The problem is known to be polynomial-time solvable on graphs with bounded clique width; does this indicate that the problem is FPT for the parameter clique width? Similary, if the problem is linear-time solvable on graphs with bounded clique width, does this indicate the same? Please clarify.

$\endgroup$

1 Answer 1

5
$\begingroup$

Not necessarily, being polynomial-time solvable for graphs with bounded clique-width means that on graphs of clique-width less than $k$ an algorithm solves the problem in $O(n^{f(k)})$ time for some function $f$, so it only implies that the problem is XP (slice wise polynomial) with respect to clique-width.

On the other hand if the problem is linear-time solvable on graphs with bounded clique-width, then an algorithm solves it in $O(f(k)\cdot n)$ for graphs with clique-width at most $k$, so it is indeed FPT, as FPT means being solvable in $O(f(k)\cdot n^c)$ for some function $f$ and $c>0$.

$\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.