Edge-disjoint paths in digraphs with bounded independence number

Alexandra Fradkin, Paul Seymour

Research output: Contribution to journalArticle

14 Scopus citations

Abstract

A digraph H is infused in a digraph G if the vertices of H are mapped to vertices of G (not necessarily distinct), and the edges of H are mapped to edge-disjoint directed paths of G joining the corresponding pairs of vertices of G. The algorithmic problem of determining whether a fixed graph H can be infused in an input graph G is polynomial-time solvable for all graphs H (using paths instead of directed paths). However, the analogous problem in digraphs is NP-complete for most digraphs H. We provide a polynomial-time algorithm to solve a rooted version of the problem, for all digraphs H, in digraphs with independence number bounded by a fixed integer α. The problem that we solve is a generalization of the k edge-disjoint directed paths problem (for fixed k).

Original languageEnglish (US)
Pages (from-to)19-46
Number of pages28
JournalJournal of Combinatorial Theory. Series B
Volume110
DOIs
StatePublished - Jan 1 2015

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Keywords

  • Digraphs
  • Disjoint paths
  • Independence number
  • Linking problem
  • Polynomial-time algorithm
  • Tournaments

Fingerprint Dive into the research topics of 'Edge-disjoint paths in digraphs with bounded independence number'. Together they form a unique fingerprint.

  • Cite this