论文标题
关于稀疏密度图中独立集的注释
A note on independent sets in sparse-dense graphs
论文作者
论文摘要
Feder，Hell，Klein和Motwani [Stoc 1999，Sidma 2003]引入了稀疏密集的分区，作为解决分区问题的工具。在本文中，介绍了有关具有稀疏密度分区的独立集的以下结果：如果$ n $ - vertex Graph $ g $承认一个稀疏的密度分区，涉及$ \ MATHCAL S $和$ \ MATHCAL D $，则$ \ Mathcal d $是$ K_T $ k_t $ thragral的$ k_t $ thragral and the $ k_ thragral and the $ k_t y-freee thrmighterge（ $ \ MATHCAL S $可以在多项式时间内识别，然后： 列举所有$ g $的最大独立集（或找到其最大值）可以在$ n^{o（1）} $时间中执行，每当可以在多项式时间内完成$ \ MATHCAL S $的图形时，每当可以完成。 该结果具有以下有趣的含义： P与NP二分法最大的NP二分法。在图形上的独立集可以将其顶点集分为$ K $独立集和$ \ ell $ cliques，所谓的$（k，\ ell）$ - 图形。关于$ k $的值和$ \ ell $的$（k，\ ell）$ - 图。 不需要$（1，\ ell）$的P时间算法来确定$（1，\ ell）$ - Graph $ G $是否已覆盖。覆盖良好的图是每个最大独立集具有相同基数的图形。 冲突图类的表征，P-pime图问题的冲突版本仍在假设这样的类中。图形问题的冲突版本要求解决方案，以避免冲突图中描述的一对冲突元素（顶点或边缘）。
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 $\mathcal S$ and $\mathcal D$, where $\mathcal D$ is a subclass of the complement of $K_t$-free graphs (for some ~$t$), and graphs in $\mathcal S$ 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 $\mathcal S$. 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 $\ell$ cliques, so-called $(k, \ell)$-graphs. concerning the values of $k$ and $\ell$ of $(k, \ell)$-graphs. A P-time algorithm that does not require $(1,\ell)$-partitions for determining whether a $(1,\ell)$-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.
