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.
Author: | Marco Blanco, Ralf BorndörferORCiD, 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: | https://doi.org/10.1016/j.endm.2015.07.057 |