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

DOI10.1007/978-3-642-40450-4_43MaRDI QIDQ2849341zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Fedor V. Fomin, Michał Pilipczuk

Publication date 17 September 2013

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

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

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)

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.

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

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
• Comparing linear width parameters for directed graphs
• 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
• 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)