Sufficiency of the NR-facet condition for parsimonious relaxations

About 19 years old · traced to

Let PnP_n be the Graphical Traveling Salesman Polyhedron, let GB\mathcal G_B be the graph associated with a relaxation RB\mathcal R_B, and call a facet of PnP_n an NR-facet when it has the stated non-rank property. Parsimonious-relaxation conjecture. If every connected component of GB\mathcal G_B contains a vertex corresponding to an NR-facet of PnP_n, then the relaxation RB\mathcal R_B has the parsimonious property. This conjectures that the necessary condition established in the cited theorem is also sufficient; the supplied text gives no resolution.

References

Primary source

Dirk Oliver Theis, “On the facial structure of Symmetric and Graphical Traveling Salesman Polyhedra”, arXiv:0712.1269 (2009).

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.