24
$\begingroup$

We know that Maximum Independent Set (MIS) is hard to approximate within a factor of $n^{1-\epsilon}$ for any $\epsilon > 0$ unless P = NP. What are some special classes of graphs for which better approximation algorithms are known?

What are the graphs for which polynomial-time algorithms are known? I know for perfect graphs this is known, but are there other interesting classes of graphs?

Improve this question
$\endgroup$
1

5 Answers 5

Reset to default
19
$\begingroup$

There is a truly awesome list of all known graph classes that have some nontrivial algorithms for MIS: see this entry in the graph classes website.

Improve this answer
$\endgroup$
3
  • 9
    $\begingroup$ That list aims exclusively for exact algorithms. On the approximation, the major class might be the PTAS on planar graphs, bounded genus graphs, and H-minor-free graphs. $\endgroup$
    – Yixin Cao
    Commented Nov 9, 2012 at 18:36
  • $\begingroup$ Thanks Suresh. The list is quite comprehensive. Thanks also to Yan for the approximation results. $\endgroup$
    – Arindam Pal
    Commented Nov 10, 2012 at 2:15
  • 2
    $\begingroup$ the corresponding references are: Brenda S. Baker: Approximation Algorithms for NP-Complete Problems on Planar Graphs. J. ACM 41(1): 153-180 (1994); David Eppstein: Diameter and Treewidth in Minor-Closed Graph Families. Algorithmica 27(3): 275-291 (2000); Erik D. Demaine, Mohammad Taghi Hajiaghayi, Ken-ichi Kawarabayashi: Algorithmic Graph Minor Theory: Decomposition, Approximation, and Coloring. FOCS 2005: 637-646. See also: courses.csail.mit.edu/6.889/fall11/lectures/L08.html and courses.csail.mit.edu/6.889/fall11/lectures/L09.html $\endgroup$
    – Christian Sommer
    Commented Nov 14, 2012 at 19:16
12
$\begingroup$

I don't have a good overview of this problem, but I can give some examples. A simple approximation algorithm would be to find some order of the nodes and greedily select the nodes to be in the independent set if non of its previous neighbors have been selected in the independent set.

If the graph has degeneracy $d$ then using the degeneracy ordering will give a $d$-approximation. hence for graphs of degeneracy $n^{1-\epsilon}$ we have a good enough approximation.

There is a couple of other techniques for approximations that work too, but I don't know them well. See: http://en.wikipedia.org/wiki/Baker%27s_technique and http://courses.engr.illinois.edu/cs598csc/sp2011/Lectures/lecture_7.pdf

For the polynomial algorithms solving the problems exactly The link Suresh gave is the best. Which graphclasses that are more interesting is hard to say.

One class you wont find in that list is the complement of $k$-degenerate graphs. Since max clique can be solved in $O(2^k n)$ on graphs of degeneracy $k$ see http://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm especially the work of Eppstein. Then Independent set is polynomial on G if the complement of G has degeneracy $O(\log n)$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ As Mohammad Al-Turkistany said in his answer cubic planar graphs are one of those non perfect graphs where independent set can be approximated. All planar graphs has degeneracy at most 5, and graphs of genus k has degeneracy O(k) and independent set can hence approximated. $\endgroup$
    – Martin Vatshelle
    Commented Nov 10, 2012 at 5:10
5
$\begingroup$

For the class of cubic planar graphs, this paper, An approximation algorithm for the maximum independent set problem in cubic planar graphs by Elarbi Choukhmane and John Franco, gives a polynomial time approximation algorithm. The approximation factor of their algorithm is 6/7.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ That was already obsolete by Baker's technique (FOCS'83) at the time it was published in 1986 $\endgroup$
    – David Eppstein
    Commented Jan 26, 2014 at 19:14
4
$\begingroup$

I haven't checked the answers above, so my apologies if there is an overlap. Here is a special case where you can solve it exactly in polynomial time. If your graph G is a line graph, then run a polynomial time algorithm to find the root graph H, and then find a maximum matching in H.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Both line graphs and complement of line graphs are polynomial and covered by the list given by Suresh Venkat. $\endgroup$
    – Martin Vatshelle
    Commented Nov 14, 2012 at 1:32
3
$\begingroup$

In geometric intersection graphs, there are several interesting approximations, PTASs, and sub-exponential exact algorithms. See the Wikipedia article Maximum Disjoint Set for a survey.

Improve this answer
$\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.