On the pathwidth of almost semicomplete digraphs

DOI10.1007/978-3-662-48350-3_68MaRDI QIDQ3452843zbMATH OpenOpenAlexFDO

Authors Kenta Kitsunai, Yasuaki Kobayashi, Hisao Tamaki

Publication date 19 November 2015

Published in Algorithms - ESA 2015 (Search for Journal in Brave)

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

Mathematics Subject Classification ID

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

Abstract: We call a digraph {em $h$-semicomplete} if each vertex of the digraph has at most $h$ non-neighbors, where a non-neighbor of a vertex $v$ is a vertex $ueqv$ such that there is no edge between $u$ and $v$ in either direction. This notion generalizes that of semicomplete digraphs which are $0$-semicomplete and tournaments which are semicomplete and have no anti-parallel pairs of edges. Our results in this paper are as follows. (1) We give an algorithm which, given an $h$-semicomplete digraph $G$ on $n$ vertices and a positive integer $k$, in $(h+2k+1{)}^{2k}{n}^{O(1)}$ time either constructs a path-decomposition of $G$ of width at most $k$ or concludes correctly that the pathwidth of $G$ is larger than $k$. (2) We show that there is a function $f(k,h)$ such that every $h$-semicomplete digraph of pathwidth at least $f(k,h)$ has a semicomplete subgraph of pathwidth at least $k$. One consequence of these results is that the problem of deciding if a fixed digraph $H$ is topologically contained in a given $h$-semicomplete digraph $G$ admits a polynomial-time algorithm for fixed $h$.

Recommendations

• On width measures and topological problems on semi-complete digraphs
• Computing cutwidth and pathwidth of semi-complete digraphs via degree orderings
• Characterizations and directed path-width of sequence digraphs
• Tournament pathwidth and topological containment
• Jungles, bundles, and fixed-parameter tractability

Cites work

• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A Polynomial Time Algorithm for Bounded Directed Pathwidth
• A well-quasi-order for tournaments
• Digraph searching, directed vertex separation and directed pathwidth
• Disjoint paths in tournaments
• Edge-disjoint paths in digraphs with bounded independence number
• Graph minors. XIII: The disjoint paths problem
• Graph minors. XX: Wagner's conjecture
• scientific article; zbMATH DE number 1498519 (Why is no real title available?)
• Linear layouts in submodular systems
• On the pathwidth of almost semicomplete digraphs
• The directed subgraph homeomorphism problem
• Tournament minors
• Tournament pathwidth and topological containment

Cited in

(14)

• A uniform approach to semi-dynamic problems on digraphs
• How to compute digraph width measures on directed co-graphs
• On width measures and topological problems on semi-complete digraphs
• Comparing linear width parameters for directed graphs
• Computing cutwidth and pathwidth of semi-complete digraphs via degree orderings
• On the pathwidth of almost semicomplete digraphs
• Exploring the complexity of layout parameters in tournaments and semicomplete digraphs
• scientific article; zbMATH DE number 867679 (Why is no real title available?)
• Exploring the complexity of layout parameters in tournaments and semi-complete digraphs
• An excluded half-integral grid theorem for digraphs and the directed disjoint paths problem
• Jungles, bundles, and fixed-parameter tractability
• Characterizations and directed path-width of sequence digraphs
• A minimum semi-degree sufficient condition for one-to-many disjoint path covers in semicomplete digraphs
• Tournament pathwidth and topological containment

This page was built for publication: On the pathwidth of almost semicomplete digraphs

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