Polynomial-time conjecture for subgraphs with boundedly many components
Statement
Let be a finite graph and let be a subgraph of with at most components, where is a natural number. The notions -Eulerian and semi -Eulerian mean, respectively, that has an -Eulerian circuit or an -Eulerian trail: a closed or open trail in containing every edge of . Polynomial-time conjecture. For every natural number , determining whether is -Eulerian or semi -Eulerian can be done in polynomial time. The paper establishes NP-completeness for unrestricted subgraphs and a linear-time algorithm for connected subgraphs; the conjecture proposes polynomial-time solvability for every fixed bound on the number of components.
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.