ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let GG be a finite graph and let HH be a subgraph of GG with at most kk components, where kk is a natural number. The notions SS-Eulerian and semi SS-Eulerian mean, respectively, that HH has an SS-Eulerian circuit or an SS-Eulerian trail: a closed or open trail in GG containing every edge of HH. Polynomial-time conjecture. For every natural number kk, determining whether HH is SS-Eulerian or semi SS-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 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.