Skip to main content

Edge-disjoint paths in digraphs with bounded independence number

Author(s): Fradkin, Alexandra; Seymour, Paul D

Download
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1s954
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 alpha. The problem that we solve is a generalization of the k edge-disjoint directed paths problem (for fixed k). (C) 2014 Elsevier Inc. All rights reserved.
Publication Date: Jan-2015
Electronic Publication Date: 22-Jul-2014
Citation: Fradkin, Alexandra, Seymour, Paul. (2015). Edge-disjoint paths in digraphs with bounded independence number. JOURNAL OF COMBINATORIAL THEORY SERIES B, 110 (19 - 46. doi:10.1016/j.jctb.2014.07.002
DOI: doi:10.1016/j.jctb.2014.07.002
ISSN: 0095-8956
EISSN: 1096-0902
Pages: 19 - 46
Type of Material: Journal Article
Journal/Proceeding Title: JOURNAL OF COMBINATORIAL THEORY SERIES B
Version: Author's manuscript



Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.