### 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...