Planar support graph conjecture for shrinking rules C1, C2, and C3

Let GG be a graph, and let (y,x)PAG(y,x)\in P^G_A be a vector. The support graph Gˉ\bar{G} of (y,x)(y,x) is the graph associated with this vector. Planar support graph conjecture. If Gˉ\bar{G} is planar, then the combination of the rules C1 and C2 dominates the rule C3. This conjecture is motivated by computational observations on planar support graphs, where rule C3 did not simplify the graph beyond the simplifications obtained using C1 and C2. The paper notes that the rules correspond to edge contractions, which preserve planarity, but does not establish the conjecture.

Sources & referencesView supporting material

Primary source

Gorka Kobeaga, María Merino and Jose A. Lozano, “On Solving Cycle Problems with Branch-and-Cut: Extending Shrinking and Exact Subcycle Elimination Separation Algorithms”, arXiv:2004.14574 (2021).

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.