Subexponential parameterized algorithm for computing the cutwidth of a semi-complete digraph

DOI10.1007/978-3-642-40450-4_43zbMATH Open1395.68359DBLPconf/esa/FominP13arXiv1301.7314OpenAlexW1650190001WikidataQ60488446 ScholiaQ60488446MaRDI QIDQ2849341FDOQ2849341

Authors: Fedor V. Fomin, Michał Pilipczuk 

Publication date: 17 September 2013

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: Cutwidth of a digraph is a width measure introduced by Chudnovsky, Fradkin, and Seymour [4] in connection with development of a structural theory for tournaments, or more generally, for semi-complete digraphs. In this paper we provide an algorithm with running time 2^{O(sqrt{k log k})} * n^{O(1)} that tests whether the cutwidth of a given n-vertex semi-complete digraph is at most k, improving upon the currently fastest algorithm of the second author [18] that works in 2^{O(k)} * n^2 time. As a byproduct, we obtain a new algorithm for Feedback Arc Set in tournaments (FAST) with running time 2^{csqrt{k}} * n^{O(1)}, where c = 2pi / sqrt(3)*ln(2) <= 5.24, that is simpler than the algorithms of Feige [9] and of Karpinski and Schudy[16], both also working in 2^{O(sqrt{k})} * n^{O(1)} time. Our techniques can be applied also to other layout problems on semi-complete digraphs. We show that the Optimal Linear Arrangement problem, a close relative of Feedback Arc Set, can be solved in 2^{O(k^{1/3} sqrt{log k})} * n^{O(1)} time, where k is the target cost of the ordering.

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

Recommendations

• Exploring the complexity of layout parameters in tournaments and semi-complete digraphs
• Exploring the complexity of layout parameters in tournaments and semicomplete digraphs
• Computing cutwidth and pathwidth of semi-complete digraphs via degree orderings
• Algorithms and kernels for \textsc{Feedback Set} problems in generalizations of tournaments
• On width measures and topological problems on semi-complete digraphs

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) 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)

Cited In (13)

• Beyond bidimensionality: parameterized subexponential algorithms on directed graphs
• Computing cutwidth and pathwidth of semi-complete digraphs via degree orderings
• Exploring the complexity of layout parameters in tournaments and semi-complete digraphs
• The solution space of sorting with recurring comparison faults
• Exploring the complexity of layout parameters in tournaments and semicomplete digraphs
• A sub-exponential FPT algorithm and a polynomial kernel for minimum directed bisection on semicomplete digraphs
• Sub-Exponential Time Parameterized Algorithms for Graph Layout Problems on Digraphs with Bounded Independence Number
• Comparing linear width parameters for directed graphs
• On width measures and topological problems on semi-complete digraphs
• Algorithms and kernels for \textsc{Feedback Set} problems in generalizations of tournaments
• Tournaments and Semicomplete Digraphs
• The solution space of sorting with recurring comparison faults
• Sub-exponential time parameterized algorithms for graph layout problems on digraphs with bounded independence number

This page was built for publication: Subexponential parameterized algorithm for computing the cutwidth of a semi-complete digraph

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