Finding Short Paths on Simple Polytopes

This paper resolves two major open problems by proving that computing shortest monotone paths on simple polytopes and determining their diameters are NP-hard, while also demonstrating that polynomial-time linear paths can be found on specific small extended formulations of any polytope.

The Gist

Imagine you are standing at the bottom of a massive, multi-sided mountain made of flat rock faces. This mountain is a polytope (a fancy geometric shape). Your goal is to get to the very peak, which represents the "optimal solution" to a math problem.

You can only move along the edges of the mountain, stepping from one corner (vertex) to an adjacent corner. This is how the famous Simplex Method works: it's a step-by-step hiking guide to solve linear programming problems (like maximizing profit or minimizing cost).

For decades, mathematicians have asked a simple question: "Is there a fast way to find the shortest hiking trail to the top?"

This new paper by Alexander Black and Raphael Steiner says: "No. In fact, finding that shortest path is incredibly hard, almost impossible to do quickly for complex mountains."

Here is the breakdown of their discovery using everyday analogies:

1. The "God's Shortcut" Problem

Imagine you have a map of the mountain. You want to find the absolute shortest route to the top.

• The Old Hope: Maybe there's a clever trick or a shortcut that lets you calculate this path instantly, no matter how big the mountain is.
• The New Reality: The authors prove that finding this shortest path is NP-hard. In computer science speak, this means it's like trying to solve a massive Sudoku puzzle where the number of possibilities grows so fast that even the world's fastest supercomputers would take longer than the age of the universe to solve it for a large enough mountain.

They specifically looked at "Simple Polytopes." Think of these as mountains where every corner is perfectly formed by exactly the right number of rock faces meeting (no messy, overlapping corners). You might think, "If the shape is simple, the path should be simple too." The authors say: "Not so fast. Even the simplest-looking mountains can have hidden, labyrinthine paths that are a nightmare to navigate."

2. The "Knapsack" Trap

To prove this, they didn't just look at random mountains. They used a specific type of shape called a "Fractional Knapsack Polytope."

• The Analogy: Imagine you are a thief with a backpack (a knapsack) and a pile of items. Some items are heavy, some are light, and some are even "negative weight" (they make the bag lighter). You want to fill the bag to get the most value.
• The Twist: They showed that even with this specific, well-understood type of problem, finding the shortest route to the best solution is still computationally impossible to do quickly. It's like saying, "Even if I give you a very specific, simple rulebook for packing your bag, figuring out the absolute fastest way to pack it is still a super-hard puzzle."

3. The "Tower of Babel" Construction (The Diameter Problem)

The paper also tackles a related question: "What is the longest possible distance between any two points on this mountain?" This is called the diameter.

• The Problem: For a long time, people wondered if the diameter was always small (related to the number of sides).
• The Solution: The authors built a "machine" (a mathematical construction they call "Siloing") that takes a mountain and builds a giant tower on top of it.
• The Metaphor: Imagine you have a small hill. You want to prove that the distance between the bottom and the top is huge. Instead of just making the hill taller, they build a spiral staircase (the "silo") that winds up and around. They proved that by stacking these staircases, you can force the distance between two points to be as long as you want, and calculating that exact length is just as hard as solving the shortest path problem.

4. The "Rock Extension" (The Good News)

If the news is all bad, why is this paper important? Because it ends with a glimmer of hope.

• The Discovery: They looked at a special type of mountain construction called a "Rock Extension" (named after a previous paper by Kaibel and Kukharenko).
• The Analogy: Imagine a mountain that is built with a secret "elevator shaft" running straight through it.
• The Result: They proved that for these specific "Rock Extension" mountains, you can find a path to the top quickly. It's not just a guess; there is a guaranteed, efficient algorithm to walk from any point to any other point on these specific shapes.
• Why it matters: This suggests that while the general problem is hard, there might be specific "special cases" (like the Rock Extensions) where the Simplex method could work perfectly fast. It narrows down exactly where the difficulty lies.

Summary: What does this mean for the real world?

• The Bad News: We cannot rely on a universal "magic button" to instantly find the shortest path for every linear programming problem. If you try to force the Simplex method to take the absolute shortest route, it might get stuck in a maze that takes forever to solve.
• The Good News: We now know exactly where the difficulty comes from. We know that for most "simple" shapes, the path is hard to find, but for specific, engineered shapes (Rock Extensions), it is easy.
• The Big Picture: This helps computer scientists understand the limits of optimization. It tells us that if we want a super-fast version of the Simplex method, we can't just look for a better rule for picking the next step; we might need to fundamentally change how we represent the problem (like using those Rock Extensions).

In a nutshell: The authors proved that finding the "God's Shortcut" on a math mountain is a trap. It's a puzzle designed to break computers. However, they also found a specific type of mountain where the shortcut does exist, giving us a new direction for future research.

Technical Summary

Here is a detailed technical summary of the paper "Finding Short Paths on Simple Polytopes" by Alexander E. Black and Raphael Steiner.

1. Problem Statement and Context

The paper addresses fundamental open questions regarding the computational complexity of navigating the graphs of simple polytopes (polytopes where every vertex is defined by exactly $d$ tight inequalities in $d$ dimensions). The central problems investigated are:

• Shortest Monotone Paths: Given a linear program (LP) over a simple polytope and a feasible starting basis, can one find the shortest sequence of pivots (a monotone path) to an optimal basis in polynomial time? This is often referred to as "God's pivot rule."
• Combinatorial Diameter: Given a simple polytope defined by inequalities, can one compute the diameter of its vertex-edge graph (the longest shortest path between any pair of vertices) in polynomial time?

These questions are critical to understanding the worst-case performance of the Simplex Method. While many pivot rules are known to have superpolynomial worst-case performance, the complexity of finding the optimal (shortest) path or the diameter remained open, particularly for simple polytopes. Previous hardness results often relied on degenerate polytopes where the vertex-edge graph and the feasible basis exchange graph do not coincide.

2. Methodology

The authors employ a combination of combinatorial reductions, polyhedral constructions, and structural analysis of specific polytope classes.

A. Reduction from Partition with Even Sum

To prove NP-hardness for shortest paths, the authors reduce the Partition with Even Sum problem (a variant of the classic Partition problem) to the problem of finding shortest paths on a specific class of polytopes.

• Construction: They define a polytope $P_b$ in dimension $d+2$ by intersecting a hypercube $[0, 1]^{d+2}$ with a specific half-space defined by the partition instance $b$.
• Properties: They prove $P_b$ is a simple polytope. The vertices of $P_b$ are combinatorially described, and the adjacency structure is analyzed.
• Key Insight: They show that the distance between two specific vertices, $(\emptyset, d+2)$ and $([d+1], d+2)$, is exactly $d+1$ if and only if a solution to the Partition instance exists. Any path shorter than $d+1$ is impossible due to the geometry, and a path of length $d+1$ exists only if the partition sum can be balanced.

B. The "Silo" Construction for Diameter

To extend the hardness of shortest paths to the diameter problem, the authors introduce a polyhedral construction called Siloing (or cyclic siloing).

• Truncation and Stacking: They iteratively apply truncation (cutting off a vertex with a hyperplane) to replace a vertex with a "tower" of new vertices.
• Preserving Simplicity: Unlike previous constructions (e.g., Frieze and Teng) that broke simplicity by stacking, this method uses iterative truncations to maintain the simple polytope property.
• Cyclic Siloing: By applying this construction cyclically ($r$ times) to two specific vertices $u$ and $v$, they create a structure where the distance between the new "peaks" of the silos is exactly $d(u, v) + 2rd(d-1)$.
• Diameter Isolation: They prove that for sufficiently large $r$, the diameter of the resulting polytope is determined entirely by the distance between these two peaks, effectively reducing the diameter computation to the shortest path problem between the original vertices.

C. Rock Extensions (Positive Result)

For the positive result, the authors analyze Rock Extensions, a construction by Kaibel and Kukharenko.

• Structure: A rock extension transforms a simple $d$-dimensional polytope into a $(d+1)$-dimensional simple polytope with a linear diameter bound ($O(m)$).
• Algorithm: They demonstrate that for rock extensions, one can find a path of length at most $2(m-d)$between any two vertices in **weakly polynomial time**. If a specific "distinguished vertex"$(o, 1)$ is known, the path can be found in strongly polynomial time.

3. Key Contributions and Results

Theorem 1.1: NP-Hardness of Shortest Paths on Simple Polytopes

The decision problem $k$-Distance on simple polytopes (determining if two vertices have distance $\le k$) is NP-hard.

• This resolves a 2022 open question by De Loera, Kafer, and Sanità.
• The hardness holds even for fractional knapsack polytopes with at most $2d+1$ facets.
• Corollary: Finding a path shorter than the Hirsch bound ($m-d$) by more than 2 is NP-hard.

Theorem 1.3: NP-Hardness of Monotone Paths

The decision problem $k$-Monotone-Distance on simple polytopes (finding a monotone path of length $\le k$ to an optimum) is NP-hard.

• This implies that Pivot-distance (finding the shortest sequence of pivots to an optimal basis) is NP-hard.
• This resolves the open question of whether "God's pivot rule" can be computed in polynomial time (assuming $P \neq NP$).

Theorem 1.5: NP-Hardness of Diameter

The decision problem Diameter of simple polytopes (determining if $\text{diam}(P) \le k$) is NP-hard.

• This resolves a 2003 open problem by Kaibel and Pfetsch.
• The proof relies on the reduction from the shortest path problem using the cyclic siloing construction.

Theorem 1.6: Polynomial Path Finding on Rock Extensions

While general shortest paths are hard, the authors show that for Rock Extensions:

• A path of length $\le 2(m-d)$ between any two vertices can be found in weakly polynomial time.
• If the distinguished vertex $(o, 1)$ is provided, the path can be found in strongly polynomial time.
• This suggests that complexity theory is not the primary obstruction to a polynomial-time Simplex method if one restricts the problem to rock extensions and uses a specific Phase 1 procedure.

4. Significance and Implications

1. Resolution of Long-Standing Open Problems: The paper definitively answers whether shortest paths and diameters on simple polytopes can be computed efficiently. The answer is no (under the assumption $P \neq NP$).
2. Distinction from Degenerate Cases: Previous hardness results for polytope diameters often relied on degenerate polytopes. This paper proves that the hardness persists even for simple polytopes, where the geometry is "cleaner" and the basis exchange graph coincides with the vertex-edge graph.
3. Implications for the Simplex Method: The result that finding the shortest monotone path is NP-hard implies that no pivot rule can guarantee finding the optimal path in polynomial time unless $P=NP$. This reinforces the view that the Simplex method's efficiency relies on average-case or smoothed analysis rather than worst-case guarantees.
4. Nuanced Positive Result: The paper provides a "silver lining" by showing that for a specific class of polytopes (Rock Extensions) with linear diameters, short paths can be found efficiently. This connects the complexity of the Simplex method to the existence of strongly polynomial algorithms for Linear Programming, suggesting that if a strongly polynomial LP solver exists, a strongly polynomial Simplex method (on rock extensions) also exists.
5. Methodological Innovation: The introduction of cyclic siloing to preserve simplicity while manipulating distances provides a new tool for polyhedral combinatorics, potentially applicable to other problems involving polytope graphs.

In summary, the paper establishes that the computational difficulty of navigating polytope graphs is intrinsic even in the simplest geometric settings, while simultaneously identifying a specific structural class where efficient navigation is possible, thereby refining our understanding of the barriers to a polynomial-time Simplex method.