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.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.