1
$\begingroup$

I call the problem as DOM. Given a graph $G$ and an integer $d$, Decision problem DOM - "Does there exists a dominating set of size less than or equal to 'd' in G? " DOM is NP Complete problem. But, if we specify some class of graphs $G'$ and if we ask the same question, then DOM might be solved in polynomial time. (Eg : Given $C_n$, and an integer $d$ , you can verify DOM in polynomial time ) Till date , for which all classes of graphs, DOM problem can be solved in polynomial time ? [Let me know where I can find research papers worked on this topic]

$\endgroup$
0
$\begingroup$

I guess that related Wikipedia article is a rather complete and up to date source. According to it, a minimum dominating set can be found in linear time in series-parallel graphs. On the other hand, even for planar graphs the problem remains NP-hard, but it admits a polynomial-time approximation scheme (PTAS) and a fixed-parameter algorithm is known.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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