Exploring the complexity of layout parameters in tournaments and semicomplete digraphs

DOI10.1145/3196276zbMATH Open1454.68055arXiv1706.00617OpenAlexW2963055638WikidataQ129615052 ScholiaQ129615052MaRDI QIDQ4554366FDOQ4554366

Authors: Florian Barbero, Christophe Paul, Michał Pilipczuk 

Publication date: 13 November 2018

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

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.

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

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

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)

Cited In (6)

• Turing Kernelization for Finding Long Paths in Graph Classes Excluding a Topological Minor
• 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
• Turing kernelization for finding long paths in graph classes excluding a topological minor
• Subexponential parameterized algorithm for computing the cutwidth of a semi-complete digraph
• Title not available (Why is that?)

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)