The trek-identification linear program is not integral on its tight face

Abstract

Sturma and Drton (arXiv:2507.18170) give a graphical criterion for the identifiability of parameters of a linear structural equation model with arbitrarily structured latent variables, together with a sound and complete algorithm for testing it. The algorithmic core of that test is an integer linear program Lp(G,G₁,Z,P,Yₐ): a two-commodity packing of vertex-disjoint directed paths in which the two commodities leave a common super-source, share unit node capacities, and one of them is confined to a subgraph G₁ ⊆ G. Its value never exceeds ab(Z)+ab(P), and their Theorem 4.1 says that an integer solution of that value exists exactly when the path system the criterion needs exists. They conjecture that the linear relaxation is integral on its tight face — whenever the optimal value of the relaxation equals ab(Z)+ab(P), an integer optimum of that value exists — and observe that with the conjecture their identifiability algorithm, run with a bound on the size of the latent sets it searches over, would decide identifiability in polynomial time. We show that the conjecture is false. On an explicit instance with ab(V)=8 and ab(D)=12 the relaxation attains ab(Z)+ab(P)=2 at a half-integral point, while every integer feasible point has objective at most 1 and the value 1 is attained: the integrality gap of the instance is exactly 1. The failure is localised by three controls: the worked example of the source reproduces exactly; on the same graph with D₁=D an integer optimum of value 2 exists, so the subgraph restriction and not the graph is responsible; and deleting the single arc s₁ → w₁₁ already drops the optimal value below 2, so the instance is not padded. Outside the machine-checked development we report an enumeration showing that no counterexample of this shape exists on fewer than eight nodes and that there are exactly three on eight nodes up to relabelling, and a reduction from the directed two-vertex-disjoint-paths problem showing that deciding the existence of an integer solution of value ab(Z)+ab(P) is NP-hard — so the conjecture would in any case have implied P=NP. Nothing here touches the criterion itself, its completeness, or the correctness of the integer program; what falls is the conjectured polynomial-time shortcut. Every statement labelled Theorem below has been formally verified in Lean 4 against Mathlib; the two facts reported in Section [sec:outside] are marked as lying outside that development.

Open review

This founding-collection manuscript received AI review before publication. Independent human review is open. Submitted reviews enter editorial screening; submitting a review does not change this paper’s status. Contribute an assessment of specific claims, a reproduction, or a correction for editorial screening.

Archived files

1. Version 1 · current (opens in a new tab)

   Source snapshot 2026-09-07 03:53 UTC

   File fingerprint

   6eaa0de95f78198f19c5cef8eda4ebaaebd1914ba40cb9fac89663b718f63ca0