On the Path Avoiding Forbidden Pairs Polytope

  • Given a directed, acyclic graph, a source and a sink node, and a set of forbidden pairs of arcs, the path avoiding forbidden pairs (PAFP) problem is to find a path that connects the source and sink nodes and contains at most one arc from each forbidden pair. The general version of the problem is NP-hard, but it becomes polynomially solvable for certain topological configurations of the pairs. We present the first polyhedral study of the PAFP problem. We introduce a new family of valid inequalities for the PAFP polytope and show that they are sufficient to provide a complete linear description in the special case where the forbidden pairs satisfy a disjointness property. Furthermore, we show that the number of facets of the PAFP polytope is exponential in the size of the graph, even for the case of a single forbidden pair.

Export metadata

  • Export Bibtex
Metadaten
Author:Marco Blanco, Ralf Borndörfer, Michael Brückner, Nam-Dung Hoang, Thomas Schlechte
Document Type:Article
Parent Title (English):Electronic Notes in Discrete Mathematics
Volume:50
First Page:343
Last Page:348
Year of first publication:2015
DOI:http://dx.doi.org/10.1016/j.endm.2015.07.057

$Rev: 13581 $