Comb inequality violation detection proven computationally hard
Separating comb inequalities is NP-hard
Computational Complexity
Summary
Figuring out if certain mathematical rules, called comb inequalities, are broken in travel route problems is very difficult. The authors show that this problem is as hard as solving some of the toughest logic puzzles known. They build special graphs that mimic logic rules to prove their point. This means computers cannot quickly guarantee finding these rule violations in all cases. The result helps explain why some ways to improve route planning are challenging to automate.
What this means in practice
- •For optimization algorithm developers: Designers can avoid attempts to perfectly separate comb inequalities, focusing on approximate approaches or heuristics for route optimization.
- •For complexity analysts: This classification helps determine which graph-based logical constraints can be efficiently tested when modeling combinatorial problems.
A theory result. No direct application yet.
Authors
Yohan Finet, Victor Drouin-Touchette
Abstract
Comb inequalities are important cutting planes for the symmetric travelling salesman problem, yet the complexity of their exact separation has remained a longstanding question in polyhedral combinatorics. We present a reduction from 3-SAT proving that deciding whether a comb inequality is violated is NP-complete and that the corresponding separation problem is NP-hard. This result holds even when the input vector belongs to the subtour elimination polytope, every edge value is zero, one half or one and the support graph is nonplanar with maximum degree four. The reduction constructs a graph in which six-vertex ladder gadgets encode Boolean relations and cubic graphs enforce consistency among occurrences of each logical variable. For a propositional logic formula with $v$ variables and $m$ clauses, the constructed graph has $40v+70m+30$ vertices and a linear number of positive edges. The reduction also proves hardness when every permitted tooth has two or four vertices with half of the tooth in the handle. We discuss consequences for approximating the maximum comb violation, optimization over the comb relaxation and explain why hardness of separation does not automatically transfer to larger inequality families.