Exploring the complexity of layout parameters in tournaments and semicomplete digraphs

DOI10.1145/3196276MaRDI QIDQ4554366zbMATH OpenOpenAlexWikidataFDO

Authors Florian Barbero, Christophe Paul, Michał Pilipczuk

Publication date 13 November 2018

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

Full work available at URL https://arxiv.org/abs/1706.00617, https://drops.dagstuhl.de/opus/volltexte/2017/7453/

zbMATH Keywords

tournamentscutwidthsemicomplete digraphskernelization theory

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27)

Abstract: A simple digraph is semi-complete if for any two of its vertices $u$ and $v$, at least one of the arcs $(u,v)$ and $(v,u)$ is present. We study the complexity of computing two layout parameters of semi-complete digraphs: cutwidth and optimal linear arrangement (OLA). We prove that: (1) Both parameters are $mathsfNP$-hard to compute and the known exact and parameterized algorithms for them have essentially optimal running times, assuming the Exponential Time Hypothesis; (2) The cutwidth parameter admits a quadratic Turing kernel, whereas it does not admit any polynomial kernel unless $mathsfNPsubseteqmathsfcoNP/extrmpoly$. By contrast, OLA admits a linear kernel. These results essentially complete the complexity analysis of computing cutwidth and OLA on semi-complete digraphs. Our techniques can be also used to analyze the sizes of minimal obstructions for having small cutwidth under the induced subdigraph relation.

Recommendations

• Exploring the complexity of layout parameters in tournaments and semi-complete digraphs
• Subexponential parameterized algorithm for computing the cutwidth of a semi-complete digraph
• Computing cutwidth and pathwidth of semi-complete digraphs via degree orderings
• On width measures and topological problems on semi-complete digraphs
• On the pathwidth of almost semicomplete digraphs

Cited in

(9)

• Component order connectivity in directed graphs
• A sub-exponential FPT algorithm and a polynomial kernel for minimum directed bisection on semicomplete digraphs
• Turing kernelization for finding long paths in graph classes excluding a topological minor
• Turing kernelization for finding long paths in graphs excluding a topological minor
• Subexponential parameterized algorithm for computing the cutwidth of a semi-complete digraph
• A sub-exponential FPT algorithm and a polynomial kernel for minimum directed bisection on semicomplete digraphs
• On width measures and topological problems on semi-complete digraphs
• Exploring the complexity of layout parameters in tournaments and semi-complete digraphs
• Component order connectivity in directed graphs

This page was built for publication: Exploring the complexity of layout parameters in tournaments and semicomplete digraphs

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