I am a research scholar currently working in computational complexity. I am working on a decision problem $P$ that is known to be W[2]-hard parameterized by the solution size on split graphs. As split graphs are chordal graphs, if a problem is NP-complete on split graphs, it is also NP-complete on chordal graphs. I wonder whether this also holds in terms of parameterized complexity. Can I say that the problem $P$ on chordal graphs is at least W[2]-hard? If not, can I also at least rule out the fixed-parameter tractability of the problem for the given parameter? Please let me know.
More information on parameterized complexity and W-hierarchy can be found here.


1 Answer 1


Yes, since the class of split graphs is a subclass of the class of chordal graphs, you can define a parameterized reduction from the problem parameterized by output size on split graph to the same problem parameterized by output size on chordal graph with $(G, k)\mapsto (G, k)$ where the output of the reduction is the same graph. Clearly, the resulting graph is a chordal graph, and hence, the problem is W[2]-hard on chordal graphs as well.

You can check the book parameterized complexity by Cygan et al. for more information about parameterized reductions.


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.