Hartke's integrality gap conjecture for trees with at most 12 vertices

From papers

Let TT be a tree, and consider the linear program obtained from the MacGillivray–Wang integer program for virus spread by relaxing x(v){0,1}x(v)\in\{0,1\} to a linear constraint and adding constraint (6):

vux(v)+uv,l(v)=ix(v)1,\sum_{v \succeq u} x(v)+\sum_{u \succeq v,\,l(v)=i}x(v)\leq 1,

for each vertex uu and i>l(u)i>l(u). Hartke's integrality gap conjecture. The tree in Figure~ is the smallest tree such that the LP optimum under constraint (6) differs from the integer-program optimum. Equivalently, the strengthened linear program realizes the integer-program optimum for every tree with at most 12 vertices. The conjecture concerns the occurrence of integrality gaps: the displayed 13-vertex tree has LP optimum m=7.5m^*=7.5 and integer-program optimum m=7m=7, while the claim asserts that no smaller tree has such a gap.

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

Andrea Barnett, Robert Bond, Anthony Macias, Thomas W. Mattman, Bill Parnell and Ely Schoenfield, “COVID on trees and infinite grids”, arXiv:2409.14303 (2024).

Solutions 0

No solutions have been posted yet.