On the Hardness of Short and Sign-Compatible Circuit Walks
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911791424995328 |
|---|---|
| author | Borgwardt, Steffen Grewe, Weston Kafer, Sean Lee, Jon Sanità, Laura |
| author_facet | Borgwardt, Steffen Grewe, Weston Kafer, Sean Lee, Jon Sanità, Laura |
| contents | The circuits of a polyhedron are a superset of its edge directions. Circuit walks, a sequence of steps along circuits, generalize edge walks and are "short" if they have few steps or small total length. Both interpretations of short are relevant to the theory and application of linear programming.
We study the hardness of several problems relating to the construction of short circuit walks. We establish that for a pair of vertices of a $0/1$-network-flow polytope, it is NP-complete to determine the length of a shortest circuit walk, even if we add the requirement that the walk must be sign-compatible. Our results also imply that determining the minimal number of circuits needed for a sign-compatible decomposition is NP-complete. Further, we show that it is NP-complete to determine the smallest total length (for $p$-norms $\lVert \cdot \rVert_p$, $1 < p \leq \infty$) of a circuit walk between a pair of vertices. One method to construct a short circuit walk is to pick up a correct facet at each step, which generalizes a non-revisiting walk. We prove that it is NP-complete to determine if there is a circuit direction that picks up a correct facet; in contrast, this problem can be solved in polynomial time for TU polyhedra. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_01066 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the Hardness of Short and Sign-Compatible Circuit Walks Borgwardt, Steffen Grewe, Weston Kafer, Sean Lee, Jon Sanità, Laura Optimization and Control 52B05, 68Q25, 90C60 The circuits of a polyhedron are a superset of its edge directions. Circuit walks, a sequence of steps along circuits, generalize edge walks and are "short" if they have few steps or small total length. Both interpretations of short are relevant to the theory and application of linear programming. We study the hardness of several problems relating to the construction of short circuit walks. We establish that for a pair of vertices of a $0/1$-network-flow polytope, it is NP-complete to determine the length of a shortest circuit walk, even if we add the requirement that the walk must be sign-compatible. Our results also imply that determining the minimal number of circuits needed for a sign-compatible decomposition is NP-complete. Further, we show that it is NP-complete to determine the smallest total length (for $p$-norms $\lVert \cdot \rVert_p$, $1 < p \leq \infty$) of a circuit walk between a pair of vertices. One method to construct a short circuit walk is to pick up a correct facet at each step, which generalizes a non-revisiting walk. We prove that it is NP-complete to determine if there is a circuit direction that picks up a correct facet; in contrast, this problem can be solved in polynomial time for TU polyhedra. |
| title | On the Hardness of Short and Sign-Compatible Circuit Walks |
| topic | Optimization and Control 52B05, 68Q25, 90C60 |
| url | https://arxiv.org/abs/2402.01066 |