Linear-Time Parameterized Algorithms via Skew-Symmetric Multicuts

DOI10.1145/3128600MaRDI QIDQ4554936zbMATH OpenOpenAlexFDO

Authors M. S. Ramanujan, Saket Saurabh

Publication date 12 November 2018

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1304.7505

zbMATH Keywords

backdoors to satisfiabilitygraph bipartizationgraph separation problems

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Abstract: A skew-symmetric graph $(D=(V,A),sigma)$ is a directed graph $D$ with an involution $sigma$ on the set of vertices and arcs. In this paper, we introduce a separation problem, $d$-Skew-Symmetric Multicut, where we are given a skew-symmetric graph $D$, a family of $calT$ of $d$-sized subsets of vertices and an integer $k$. The objective is to decide if there is a set $XsubseteqA$ of $k$ arcs such that every set $J$ in the family has a vertex $v$ such that $v$ and $sigma(v)$ are in different connected components of $D^{\prime }=(V,Asetminus(Xcupsigma(X))$. In this paper, we give an algorithm for this problem which runs in time $O((4d{)}^k(m+n+ell))$, where $m$ is the number of arcs in the graph, $n$ the number of vertices and $ell$ the length of the family given in the input. Using our algorithm, we show that Almost 2-SAT has an algorithm with running time $O(4^k{k}^{4}ell)$ and we obtain algorithms for {sc Odd Cycle Transversal} and {sc Edge Bipartization} which run in time $O(4^k{k}^4(m+n))$ and $O(4^k{k}^5(m+n))$ respectively. This resolves an open problem posed by Reed, Smith and Vetta [Operations Research Letters, 2003] and improves upon the earlier almost linear time algorithm of Kawarabayashi and Reed [SODA, 2010]. We also 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 which runs in time $O(12^k{k}^{5}ell)$. This gives the first fixed-parameter tractable algorithm for this problem answering a question posed in a paper by a superset of the authors [STACS, 2013]. Using this result, we get an algorithm for Satisfiability which runs in time $O(12^k{k}^{5}ell)$ where $k$ is the size of the smallest q-Horn deletion backdoor set, with $ell$ being the length of the input formula.

Recommendations

• Linear time parameterized algorithms via skew-symmetric multicuts
• Parameterized approximations via d-skew-symmetric multicut
• Linear-Time Approximation Algorithms for the Max Cut Problem
• Parameterized complexity of length-bounded cuts and multicuts
• Simple and improved parameterized algorithms for multiterminal cuts
• Linear kernels and linear-time algorithms for finding large cuts
• Linear kernels and linear-time algorithms for finding large cuts
• A parameterized algorithm for mixed-cut
• Parametrized complexity of length-bounded cuts and multi-cuts
• An improved parameterized algorithm for the multicut problem

Cited in

(8)

• Faster graph bipartization
• Parameterized approximations via d-skew-symmetric multicut
• Linear time parameterized algorithms via skew-symmetric multicuts
• SAT backdoors: depth beats size
• Tractable graph structures in EFX orientation
• When recursion is better than iteration: a linear-time algorithm for directed acyclicity with few error vertices
• On the parameterized complexity of symmetric directed multicut
• Hitting meets packing: how hard can it be?

This page was built for publication: Linear-Time Parameterized Algorithms via Skew-Symmetric Multicuts

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4554936)