Integrality conjecture for the linear program on directed graphs
Integrality conjecture for the linear program on directed graphs
Let be a directed graph, let be a subgraph of , and let , , and be the vertex sets used to define the linear program . The program has optimal value .
Integrality conjecture. If the optimal value of is , 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
Sign in to submit a solution.
No solutions have been posted yet.