About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
FSTTCS 2010
Conference paper
Finding independent sets in unions of perfect graphs
Abstract
The maximum independent set problem (MAXIS) on general graphs is known to be NP-hard to approximate within a factor of n1-ε, for any ε > 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(√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. © Venkatesan T. Chakaravarthy, Vinayaka Pandit, Sambuddha Roy and Yogish Sabharwal.