2015/07/07 by Kitsunai, Kenta, Kobayashi, Yasuaki, Tamaki, Hisao
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1507.01934
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 u ≠ v 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 nO(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.