Finding Independent Sets in Unions of Perfect Graphs

Venkatesan T. Chakaravarthy, Vinayaka Pandit, Sambuddha Roy & Yogish Sabharwal
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...