Hitting Selected (Odd) Cycles
Hitting Selected (Odd) Cycles
复制标题
击中选定的（奇数）周期
DOI：
--
复制
发表时间：
2017
影响因子：
0.8
通讯作者：
Saket Saurabh
中科院分区：
文献类型：
--
作者：
D. Lokshtanov;P. Misra;M. Ramanujan;Saket Saurabh
在子集奇数周期横向（子集OCT）问题中，输入是图$ g $，一个顶点$ t $的子集和一个正整数$ k $，目的是确定是否存在$ k $的尺寸顶点子集与每个奇数周期相交，其中包含$ t $的顶点。显然，子集OCT是对经典奇数循环横向问题的概括，其中目的是确定是否存在$ k $大小的顶点子集，该子集与给定图中的每个奇数相交。我们指出的是，子集OCT还概述了众所周知的多道路切割问题，以及奇怪的多路切割问题的奇偶校验限制。最近，Kakimura，Kawarabayashi和Kobayashi [Soda的论文集，2012年，第1726---1736页]提出了一个固定参数可处理的（FPT）算法，用于此问题，该算法在时间$ f（k）Mn^3 $中运行图形未成年人，其中$ f $是某些功能，$ n $和$ m $表示图表中的顶点和边缘的数量。但是，此功能对$ k的依赖性...
In the Subset Odd Cycle Transversal (Subset OCT) problem, the input is a graph $G$, a subset of vertices $T$ and a positive integer $k$ and the objective is to determine whether there exists a $k$-sized vertex subset that intersects every odd cycle containing a vertex from $T$. Clearly, Subset OCT is a generalization of the classic Odd Cycle Transversal problem where the objective is to determine whether there exists a $k$-sized vertex subset that intersects every odd cycle in the given graph. We remark that Subset OCT also generalizes the well known Multiway Cut problem, as well as a parity constrained variant, the Odd Multiway Cut problem. Recently, Kakimura, Kawarabayashi, and Kobayashi [Proceedings of SODA, 2012, pp. 1726--1736] proposed a fixed parameter tractable (FPT) algorithm for this problem that runs in time $f(k)mn^3$ using the theory of graph minors, where $f$ is some function, and $n$ and $m$ denote the number of vertices and edges in the graph. However, the dependence of this function on $k...