Isomorphism conjecture for graphs obtained by fixed shrinking strategies

Let GG be a graph, let (y,x)PAG(y,x)\in P^G_A be a vector, and let

SRK{C1,C1C2,C1C2C3,S1,S1S2}\mathrm{SRK}\in\{\mathrm{C1},\mathrm{C1C2},\mathrm{C1C2C3},\mathrm{S1},\mathrm{S1S2}\}

be a fixed shrinking strategy. Shrinking-strategy isomorphism conjecture. The graphs obtained by applying SRK\mathrm{SRK} to (y,x)(y,x) are isomorphic. This conjecture formalizes the experimental observation that the final shrunk graph appeared independent of the ordering of the rules and shrinkable sets. The paper presents this as a suggestion based on computational results and does not provide a proof.

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.