pith. sign in

arxiv: 1604.02317 · v2 · pith:XCLWDCEOnew · submitted 2016-04-08 · 🧮 math.CO

Disjoint paths in unions of tournaments

classification 🧮 math.CO
keywords digraphtherealgorithmfixedgivenpathspolynomial-timeproblem
0
0 comments X
read the original abstract

Given $k$ pairs of vertices $(s_i,t_i)\;(1\le i\le k)$ of a digraph $G$, how can we test whether there exist vertex-disjoint directed paths from $s_i$ to $t_i$ for $1\le i\le k$? This is NP-complete in general digraphs, even for $k = 2$, but in an earlier paper we proved that for all fixed $k$, there is a polynomial-time algorithm to solve the problem if $G$ is a tournament (or more generally, a semicomplete digraph). Here we prove that for all fixed $k$ there is a polynomial-time algorithm to solve the problem when $V(G)$ is partitioned into a bounded number of sets each inducing a semicomplete digraph (and we are given the partition).

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.