Linear-Time Parameterized Algorithms via Skew-Symmetric Multicuts
Linear-Time Parameterized Algorithms via Skew-Symmetric Multicuts
复制标题
通过斜对称多重切割的线性时间参数化算法
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Saket Saurabh
中科院分区：
文献类型：
--
作者：
M. Ramanujan;Saket Saurabh
偏斜的对称图（d =（v，a），σ）是一个有向图D，在一组顶点和弧线上有contrivationσ。在图表上，最初是由Tutte和Goldberg和Karzanov的。顶点的子集和整数k。 d'=（v，a（x∪σ（x））的组件。在这项工作中，我们给出了D-Skew-Skew-Ske-Ammetric Multisust算法，该算法在时间O（（4D）K（M+N+ℓ）中运行），其中m是图中的弧数，n是顶点，ℓ是输入中给出的家庭的长度。线性时间参数化算法，我们通过获得以下线性时间参数化算法来证明其实用性： - 我们证明几乎是2-SAT 1键对称的多模具，导致几乎2个sat的算法在时间O（4KK4ℓ）中运行，其中k是解决方案的大小，然后使用线性时间参数的长度。 - 保留将几乎2-SAT的减少，我们获得了奇数周期横向和边缘两次化的算法，这些算法分别在时间O（4KK4（M+N））和O（4KK5（M+N））中，其中K是k解决方案，以及n分别是Reed等人的边缘和顶点。特殊情况的3键对称性多源，为我们提供了一种删除Q-HORN后门设置检测算法，该算法在时间O（12kk5ℓ）中运行，其中k是解决方案的大小，而ℓ是输入公式的长度。这给出了第一个固定参数可用于此问题的算法，回答了Narayanaswamy等人的工作中所述的问题。 k是最小的Q-horn删除后门集的大小，其中是输入公式的长度。
A skew-symmetric graph (D=(V,A),σ) is a directed graph D with an involution σ on the set of vertices and arcs. Flows on skew-symmetric graphs have been used to generalize maximum flow and maximum matching problems on graphs, initially by Tutte and later by Goldberg and Karzanov. In this article, we introduce a separation problem, d-Skew-Symmetric Multicut, where we are given a skew-symmetric graph D, a family τ of d-size subsets of vertices, and an integer k. The objective is to decide whether there is a set X ⊑ A of k arcs such that every set J in the family has a vertex υ such that υ and σ(υ) are in different strongly connected components of D′=(V,A (X ∪ σ(X)). In this work, we give an algorithm for d-Skew-Symmetric Multicut that runs in time O((4d)k(m+n+ℓ)), where m is the number of arcs in the graph, n is the number of vertices, and ℓ is the length of the family given in the input. This problem, apart from being independently interesting, also captures the main combinatorial difficulty of numerous classical problems. Our algorithm for d-Skew-Symmetric Multicut paves the way for the first linear-time parameterized algorithms for several problems. We demonstrate its utility by obtaining the following linear-time parameterized algorithms: — We show that Almost 2-SAT is a special case of 1-Skew-Symmetric Multicut, resulting in an algorithm for Almost 2-SAT that runs in time O(4kk4ℓ), where k is the size of the solution and ℓ is the length of the input formula. Then, using linear-time parameter-preserving reductions to Almost 2-SAT, we obtain algorithms for Odd Cycle Transversal and Edge Bipartization that run in time O(4kk4(m+n)) and O(4kk5(m+n)), respectively, where k is the size of the solution, and m and n are the number of edges and vertices respectively. This resolves an open problem posed by Reed et al. and improves on the earlier almost-linear-time algorithm of Kawarabayashi and Reed. — We show that Deletion q-Horn Backdoor Set Detection is a special case of 3-Skew-Symmetric Multicut, giving us an algorithm for Deletion q-Horn Backdoor Set Detection that runs in time O(12kk5ℓ), where k is the size of the solution and ℓ is the length of the input formula. This gives the first fixed-parameter tractable algorithm for this problem answering a question posed in a work by Narayanaswamy et al. Using this result, we get an algorithm for Satisfiability that runs in time O(12kk5ℓ), where k is the size of the smallest q-Horn deletion backdoor set, with ℓ being the length of the input formula.