Planar support graph conjecture for shrinking rules C1, C2, and C3
Planar support graph conjecture for shrinking rules C1, C2, and C3
Let be a graph, and let be a vector. The support graph of is the graph associated with this vector. Planar support graph conjecture. If 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.