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.
Additional Services
| 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 |
