Abstract: We give a family of counter examples showing that the two sequences of polytopes $\Phi_{n,n}$ and $\Psi_{n,n}$ are different. These polytopes were defined recently by S. Friedland in an attempt at a polynomial time algorithm for graph isomorphism.
Introduction
The Graph Isomorphism (GI) problem—determining if two graphs are structurally identical—is one of the most famous puzzles in computer science. It occupies a unique middle ground in complexity theory: while it is not known to be solvable in polynomial time (in the class P), it is also generally believed not to be NP-complete. This ambiguity has led to numerous attempts to find a polynomial-time algorithm.
In early 2008, mathematician S. Friedland proposed a potential breakthrough. He defined two sequences of polytopes (high-dimensional geometric shapes): $\Phi_{n,n}$ and $\Psi_{n,n}$. Friedland’s approach suggested that if these two shapes were identical, the Graph Isomorphism problem could be reduced to Linear Programming, a class of problems for which efficient polynomial-time solvers already exist. This paper by Cai, Lu, and Xia investigates whether that equality actually holds, providing a definitive "reality check" for this proposed solution.
Methodology
The authors use a combination of combinatorial group theory and matrix analysis to test the proposed equality. The core of the proof involves constructing a large $n^2 \times n^2$ matrix $T$ that acts as a bridge between two $n \times n$ matrices, $A$ and $B$.
- Matrix Construction: Matrix $A$ is built using standard cyclic shifts, a structure that is well-understood in combinatorial group theory. Matrix $B$ is then defined as a permuted version of $A$ using a specific permutation $\sigma$.
- Permutation Analysis: A critical lemma (Lemma 2.1) establishes that for a broad class of permutations, there is no pair of permutation matrices $P$ and $Q$ such that $B = PAQ$. This effectively shows that $A$ and $B$ are not isomorphic in a way that can be easily detected by simple row and column swaps.
- Geometric Proof: The authors prove that the matrix $T$ satisfies all the linear constraints required to be an "extreme point" (a corner) of the polytope $\Phi_{n,n}$, yet it cannot be expressed as a convex combination of tensor products, meaning it lies outside the polytope $\Psi_{n,n}$.
The Local vs. Global Gap
A key insight of the paper is the distinction between local and global constraints. The polytope $\Phi_{n,n}$ is defined by "local" linear constraints involving sums of rows and columns.
As shown in the figure above, these constraints are purely algebraic. In contrast, the polytope $\Psi_{n,n}$ is defined "globally" as the convex hull of tensor products of doubly stochastic matrices. The authors show that local constraints are not enough to capture the global structure required for graph isomorphism. By using the properties of cyclic groups, the authors were able to create a rigid structure ($A$ and $B$) that is easy to analyze but "broken" enough under certain permutations to prevent the linear programming approach from working.
Key Results
The paper formally proves that $\Psi_{n,n} \subsetneq \Phi_{n,n}$ for all $n \geq 4$. This result is not just a single counter-example; the authors show that for any $n \geq 4$, there exists an exponential number of such matrices, indicating a fundamental gap between the local linear constraints and the global structure of the Graph Isomorphism problem.
- Refutation of the "P=GI" Path: Because these polytopes are different, Friedland's specific strategy for a polynomial-time algorithm for Graph Isomorphism is shown to be incorrect.
- Extreme Points: The authors demonstrate that the matrix $T$ they constructed is an extreme point of the larger polytope. This is significant because linear programming solvers typically look at these "corners," and this result shows the solver would find "false positives" that don't correspond to actual graph isomorphisms.
Conclusion
The paper serves as a reminder that the Graph Isomorphism problem remains one of the most elusive targets in complexity theory. While it does not provide an alternative polynomial-time algorithm, it highlights the inherent difficulty of the problem. The authors briefly mention work by other researchers (Babai and Onn) which suggests that the "harder" polytope, $\Psi_{n,n}$, is actually related to NP-hard problems. This implies that even if we could perfectly describe $\Psi_{n,n}$, optimizing over it would likely be computationally impossible anyway.
Summary updated