Complete trail - walk traversing each vertex at least once, each edge at most once

Question

I would like to know the status of the following problem:

Given a simple graph, is there a walk traversing each vertex at least once and each edge at most once?

(I am asking for a complete trail, a sort of cross-breed between Eulerian and Hamitonian walks, in a way.)

In particular, is that problem known to be solvable in polynomial time, or NP-complete? Or is it suspected to belong in NPI? More generally, what is known on it?

Variants: One could also ask for a circuit rather than a trail, and/or consider oriented graphs instead.

Thanks in advance!

Answer 1

I now think that the problem is in fact trivially NP-complete.

Whether there is a Hamiltonian path / cycle in a cubic graph (or, in the oriented case, a graph in which each vertex is adjacent to at most three arcs) is known to be NP-complete and can be reduced immediately to the problem at hand and its variants (whether there is a complete trail / circuit): the target graph can be used as is. In a cubic graph, a trail can traverse a node at most once, so if one imposes at least one traversal, then the node is traversed exactly once: the two problems coincide (they have the same solutions).

In the general case, the existence of of Hamiltonian path / cycle implies that of a complete trail / circuit, so the problem is a generalization (or "broadening") of the Hamiltonian counterpart.