License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2010.251
URN: urn:nbn:de:0030-drops-28683
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2010/2868/
Go to the corresponding LIPIcs Volume Portal

Chakaravarthy, Venkatesan T. ; Pandit, Vinayaka ; Roy, Sambuddha ; Sabharwal, Yogish

Finding Independent Sets in Unions of Perfect Graphs

pdf-format:
22.pdf (0.4 MB)

Abstract

The maximum independent set problem (MaxIS) on general graphs is known to be NP-hard to approximate within a factor of $n^{1-epsilon}$, for any $epsilon > 0$. However, there are many ``easy" classes of graphs on which the problem can be solved in polynomial time. In this context, an interesting question is that of computing the maximum independent set in a graph that can be expressed as the union of a small number of graphs from an easy class. The MaxIS problem has been studied on unions of interval graphs and chordal graphs. We study the MaxIS problem on unions of perfect graphs (which generalize the above two classes). We present an $O(sqrt{n})$-approximation algorithm when the input graph is the
union of two perfect graphs. We also show that the MaxIS problem on unions of two comparability graphs (a subclass of perfect graphs)
cannot be approximated within any constant factor.

BibTeX - Entry

@InProceedings{chakaravarthy_et_al:LIPIcs:2010:2868,
  author =	{Venkatesan T. Chakaravarthy and Vinayaka Pandit and Sambuddha Roy and Yogish Sabharwal},
  title =	{{Finding Independent Sets in Unions of Perfect Graphs}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)},
  pages =	{251--259},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-23-1},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{8},
  editor =	{Kamal Lodaya and Meena Mahajan},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2010/2868},
  URN =		{urn:nbn:de:0030-drops-28683},
  doi =		{10.4230/LIPIcs.FSTTCS.2010.251},
  annote =	{Keywords: Approximation Algorithms; Comparability Graphs; Hardness of approximation}
}

Keywords: Approximation Algorithms; Comparability Graphs; Hardness of approximation
Collection: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)
Issue Date: 2010
Date of publication: 14.12.2010

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI