ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Assume that GG and HH are 22-connected and 22-edge connected graphs of genus at least two. Choose a base edge ee 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 ee 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 in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.