Integrality conjecture for the linear program on directed graphs

From papers

Let G=(V,D)G=(V,D) be a directed graph, let G1G_1 be a subgraph of GG, and let ZZ, PP, and YaY_a be the vertex sets used to define the linear program Lp(G,G1,Z,P,Ya)\operatorname{Lp}(G,G_1,Z,P,Y_a). The program has optimal value Z+P|Z|+|P|.

Integrality conjecture. If the optimal value of Lp(G,G1,Z,P,Ya)\operatorname{Lp}(G,G_1,Z,P,Y_a) is Z+P|Z|+|P|, then there is an integer solution.

The authors report that this implication held in all their computations. If true in general, it would allow the polynomial-time linear program to replace the corresponding integer linear program, which is NP-complete.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Nils Sturma and Mathias Drton, “Trek-Based Parameter Identification for Linear Causal Models With Arbitrarily Structured Latent Variables”, arXiv:2507.18170 (2025).

Solutions 0

No solutions have been posted yet.