Polynomial-time Algorithm for Maximum Weight Independent Set on P6-free Graphs
Polynomial-time Algorithm for Maximum Weight Independent Set on P6-free Graphs
复制标题
无P6图上最大权独立集的多项式时间算法
DOI：
10.1137/1.9781611975482.77
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Michal Pilipczuk
中科院分区：
文献类型：
--
作者：
Andrzej Grzesik;Tereza Klimošová;Marcin Pilipczuk;Michal Pilipczuk
在经典的最大权重独立集问题中，我们给定一个图 G，其顶点上具有非负权重函数，目标是在 G 中找到最大可能权重的独立集。虽然这个问题一般来说是 NP 困难的，但我们给出了一个适用于任何 P6-free 图的多项式时间算法，即在 6 个顶点上没有路径作为导出子图的图。这改进了 Lokshtanov 等人的 P5-free 图上的多项式时间算法。 [15] 以及 Lokshtanov 等人的无 P6 图上的拟多项式时间算法。 [14]。导致我们主要结果的主要技术贡献是枚举具有以下属性的多项式大小的顶点子集族ℱ：对于图中的每个最大独立集I，ℱ包含G的某些最小弦完成的所有最大团，该团不会添加任何与I的顶点相关的边。
In the classic Maximum Weight Independent Set problem, we are given a graph G with a nonnegative weight function on its vertices, and the goal is to find an independent set in G of maximum possible weight. While the problem is NP-hard in general, we give a polynomial-time algorithm working on any P6-free graph, that is, a graph that has no path on 6 vertices as an induced subgraph. This improves the polynomial-time algorithm on P5-free graphs of Lokshtanov et al. [15] and the quasipolynomial-time algorithm on P6-free graphs of Lokshtanov et al. [14]. The main technical contribution leading to our main result is enumeration of a polynomial-size family ℱ of vertex subsets with the following property: For every maximal independent set I in the graph, ℱ contains all maximal cliques of some minimal chordal completion of G that does not add any edge incident to a vertex of I.