文章基本信息

标题：Finding Independent Sets in Unions of Perfect Graphs
本地全文：下载
作者：Venkatesan T. Chakaravarthy ; Vinayaka Pandit ; Sambuddha Roy 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2010
卷号：8
页码：251-259
DOI：10.4230/LIPIcs.FSTTCS.2010.251
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Approximation Algorithms; Comparability Graphs; Hardness of approximation