On Polynomial Kernels for Structural Parameterizations of Odd Cycle Transversal
On Polynomial Kernels for Structural Parameterizations of Odd Cycle Transversal
复制标题
奇循环横截面结构参数化的多项式核
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Stefan Kratsch
中科院分区：
文献类型：
--
作者：
B. Jansen;Stefan Kratsch
奇循环横向问题 (OCT) 询问是否可以通过删除最多 l 个顶点将给定图变成二分图（即 2 色）。我们研究 OCT 的结构参数化的多项式核化性，即实例是否可以有效地减少到所选参数的大小多项式。当参数化为 l 时，奇循环遍历是否承认多项式内核是参数化复杂性中的一个主要开放问题。
从积极的一面来看，我们展示了 OCT 的多项式核，当参数化为树宽最大为 w 的二分图类的顶点删除距离时（对于任何常数 w）；这概括了参数反馈顶点集数（即到森林的距离）。
作为补充，我们排除了由到外平面图的距离参数化的 OCT 多项式核，条件是假设 NP ⊈ coNP/poly。因此，树宽 w 图的二分性要求是必要的。分别给出了通过距簇和共簇图的距离进行参数化的下界，以及通过顶点覆盖数（即距独立集的距离）参数化的加权 OCT 的下界。
The Odd Cycle Transversal problem (OCT) asks whether a given graph can be made bipartite (i.e., 2-colorable) by deleting at most l vertices. We study structural parameterizations of OCT with respect to their polynomial kernelizability, i.e., whether instances can be efficiently reduced to a size polynomial in the chosen parameter. It is a major open problem in parameterized complexity whether Odd Cycle Transversal admits a polynomial kernel when parameterized by l.
On the positive side, we show a polynomial kernel for OCT when parameterized by the vertex deletion distance to the class of bipartite graphs of treewidth at most w (for any constant w); this generalizes the parameter feedback vertex set number (i.e., the distance to a forest).
Complementing this, we exclude polynomial kernels for OCT parameterized by the distance to outerplanar graphs, conditioned on the assumption that NP ⊈ coNP/poly. Thus the bipartiteness requirement for the treewidth w graphs is necessary. Further lower bounds are given for parameterization by distance from cluster and co-cluster graphs respectively, as well as for Weighted OCT parameterized by the vertex cover number (i.e., the distance from an independent set).
由反馈边缘集参数化的两层平面化
DOI：
10.1016/j.tcs.2013.01.029
发表时间：
2013
期刊：
Theor. Comput. Sci.
影响因子：
--
作者：
J. Uhlmann;M. Weller
通讯作者：
M. Weller