Computing cutwidth and pathwidth of semi-complete digraphs via degree orderings

DOI10.4230/LIPICS.STACS.2013.197MaRDI QIDQ2957884zbMATH OpenOpenAlexFDO

Authors Michał Pilipczuk

Publication date 30 January 2017

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

zbMATH Keywords

cutwidthpathwidthsemi-complete digraphtournament

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Abstract: The notions of cutwidth and pathwidth of digraphs play a central role in the containment theory for tournaments, or more generally semi-complete digraphs, developed in a recent series of papers by Chudnovsky, Fradkin, Kim, Scott, and Seymour [2, 3, 4, 8, 9, 11]. In this work we introduce a new approach to computing these width measures on semi-complete digraphs, via degree orderings. Using the new technique we are able to reprove the main results of [2, 9] in a unified and significantly simplified way, as well as obtain new results. First, we present polynomial-time approximation algorithms for both cutwidth and pathwidth, faster and simpler than the previously known ones; the most significant improvement is in case of pathwidth, where instead of previously known O(OPT)-approximation in fixed-parameter tractable time [6] we obtain a constant-factor approximation in polynomial time. Secondly, by exploiting the new set of obstacles for cutwidth and pathwidth, we show that topological containment and immersion in semi-complete digraphs can be tested in single-exponential fixed-parameter tractable time. Finally, we present how the new approach can be used to obtain exact fixed-parameter tractable algorithms for cutwidth and pathwidth, with single- exponential running time dependency on the optimal width.

Recommendations

• On width measures and topological problems on semi-complete digraphs
• Subexponential parameterized algorithm for computing the cutwidth of a semi-complete digraph
• Jungles, bundles, and fixed-parameter tractability
• On the pathwidth of almost semicomplete digraphs
• Exploring the complexity of layout parameters in tournaments and semi-complete digraphs

Cited in

(9)

• On width measures and topological problems on semi-complete digraphs
• Subexponential parameterized algorithm for computing the cutwidth of a semi-complete digraph
• Tournaments and Semicomplete Digraphs
• On the pathwidth of almost semicomplete digraphs
• Exploring the complexity of layout parameters in tournaments and semicomplete digraphs
• Sub-Exponential Time Parameterized Algorithms for Graph Layout Problems on Digraphs with Bounded Independence Number
• Exploring the complexity of layout parameters in tournaments and semi-complete digraphs
• Jungles, bundles, and fixed-parameter tractability
• Sub-exponential time parameterized algorithms for graph layout problems on digraphs with bounded independence number

This page was built for publication: Computing cutwidth and pathwidth of semi-complete digraphs via degree orderings

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