A note on independent sets in sparse-dense graphs

08/08/2022
โˆ™
by   Uรฉverton S. Souza, et al.
โˆ™
0
โˆ™

Sparse-dense partitions was introduced by Feder, Hell, Klein, and Motwani [STOC 1999, SIDMA 2003] as a tool to solve partitioning problems. In this paper, the following result concerning independent sets in graphs having sparse-dense partitions is presented: if a n-vertex graph G admits a sparse-dense partition concerning classes ๐’ฎ and ๐’Ÿ, where ๐’Ÿ is a subclass of the complement of K_t-free graphs (for some ย t), and graphs in ๐’ฎ can be recognized in polynomial time, then: enumerate all maximal independent sets of G (or find its maximum) can be performed in n^O(1) time whenever it can be done in polynomial time for graphs in the class ๐’ฎ. This result has the following interesting implications: A P versus NP-hard dichotomy for Max. Independent Set on graphs whose vertex set can be partitioned into k independent sets and โ„“ cliques, so-called (k, โ„“)-graphs. concerning the values of k and โ„“ of (k, โ„“)-graphs. A P-time algorithm that does not require (1,โ„“)-partitions for determining whether a (1,โ„“)-graph G is well-covered. Well-covered graphs are graphs in which every maximal independent set has the same cardinality. The characterization of conflict graph classes for which the conflict version of a P-time graph problem is still in P assuming such classes. Conflict versions of graph problems ask for solutions avoiding pairs of conflicting elements (vertices or edges) described in conflict graphs.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset