Parameterized Complexity and Inapproximability of Dominating Set Problem in Chordal and Near Chordal Graphs
{{output}}
In this paper, we study the parameterized complexity of Dominating Set problem in chordal graphs and near chordal graphs. We show the problem is W[2]-hard and cannot be solved in time no(k) in chordal and s-chordal (s > 3) graphs unless W[1]=FPT. In addition, ... ...
