On the Pathwidth of Almost Semicomplete Digraphs

We call a digraph

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

 + 2

k

 + 1)

2

k

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

.