Polynomial-time reconstruction for a non-series base edge
Statement
Assume that and are -connected and -edge connected graphs of genus at least two. Choose a base edge that is not a series edge, and consider the lifting process that tests rigidity and, when rigidity is detected, reconstructs the relevant series-fixing automorphism.
Polynomial-time lifting conjecture. When the chosen base edge is not a series edge, the above process can be carried out in at worst polynomial time in the number of vertices and edges.
The claim concerns the computational complexity of the lifting criterion for determining when an isomorphism of graphic matroids comes from an honest graph isomorphism. The source says that a careful complexity analysis would be interesting and gives no evidence of a proof or disproof.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.