[Model] EulerianPath

[zhangjieqingithub]

Motivation

The repository currently has path and walk-cover relatives such as Hamiltonian Path and Chinese Postman variants, but it does not have the classical Eulerian path feasibility problem itself.

This model is useful because it is:

• a standard directed-graph path problem in its own right,
• polynomial-time solvable, so it broadens the catalog beyond NP-hard problems,
• distinct from postman problems, which allow repeated traversals and optimize length rather than asking for an exact once-per-arc traversal.

Associated rule:

• [Rule] EulerianPath to ILP #1025: EulerianPath -> ILP

Definition

Name: EulerianPath
Reference:

• J?rgen Bang-Jensen, Gregory Z. Gutin, Digraphs: Theory, Algorithms and Applications, 2nd ed., Springer, 2009. https://doi.org/10.1007/978-1-84800-998-1
• J?rgen Ebert, ?Computing Eulerian trails,? Information Processing Letters 28(2):93-97, 1988. https://doi.org/10.1016/0020-0190(88)90170-6

Given a finite directed multigraph
D = (V, A),
with loops and parallel arcs allowed, determine whether there exists a directed trail that uses every arc in A exactly once.

Important conventions for this proposal:

• repeated arc occurrences are distinguished,
• loops are allowed,
• isolated vertices are allowed and ignored,
• a closed trail is accepted,
• the empty-arc instance is accepted, witnessed by the empty trail.

So EulerianPath is a satisfaction problem.

Variables

Let m = |A|.

• Count: m position variables
• Per-variable domain: {0,1,...,m-1}
• Meaning: the variable at position t specifies which arc occurrence is used as the t-th arc of the trail

Thus a configuration represents an ordering of the individual arc occurrences, not merely a sequence of visited vertices.

Schema (data type)

Type name: EulerianPath
Variants: none initially

Field	Type	Description
graph	DirectedGraph	The input directed multigraph D = (V, A), with repeated arcs and loops allowed

No start or end vertex is part of the input; they are existential.

Complexity

EulerianPath on directed multigraphs is solvable in linear time.

A standard algorithm:

1. ignores isolated vertices,
2. checks weak connectivity of the support,
3. checks the in-degree / out-degree balance condition,
4. constructs a witness by a Hierholzer-style traversal.

This gives complexity
O(num_vertices + num_arcs).

References:

• https://doi.org/10.1007/978-1-84800-998-1
• https://doi.org/10.1016/0020-0190(88)90170-6

Extra Remark

Let S be the set of vertices incident to at least one arc. Then the instance is a yes-instance iff either:

• A is empty, or
• the underlying undirected graph on S is connected and:
  • either every vertex satisfies outdeg(v) = indeg(v),
  • or there exist vertices s != t such that
    outdeg(s) = indeg(s) + 1,
    indeg(t) = outdeg(t) + 1,
    and every other vertex is balanced.

Loops contribute 1 to both indegree and outdegree of their incident vertex.

Reduction Rule Crossref

• [Rule] EulerianPath to ILP #1025

How to solve

• It can be solved directly in O(num_vertices + num_arcs) by the standard degree/connectivity test plus Hierholzer-style witness construction.
• It can be reduced to ILP via [Rule] EulerianPath to ILP #1025 ([Rule] EulerianPath to ILP).
• Other, refer to ...

Example Instance

Let

• V = {0,1,2}
• A = {a_0, a_1, a_2, a_3}

with arc occurrences

• a_0 = (0,1)
• a_1 = (0,1) (parallel to a_0)
• a_2 = (1,2)
• a_3 = (2,0)

This is a directed multigraph with a repeated arc.

Expected Outcome

This is a yes-instance.

One valid witness is the arc ordering
(a_0, a_2, a_3, a_1),
which traces the directed trail
0 -> 1 -> 2 -> 0 -> 1.

It uses every arc occurrence exactly once, including both copies of the arc (0,1).

A small no-instance for contrast is:

• V = {0,1}
• A = {(0,1), (0,1), (0,1), (1,0)}

Here the support is connected, but

• outdeg(0) - indeg(0) = 2
• indeg(1) - outdeg(1) = 2

so the directed balance criterion fails and no Eulerian path exists.

BibTeX

@book{BangJensenGutin2009Digraphs,
  author    = {J?rgen Bang-Jensen and Gregory Z. Gutin},
  title     = {Digraphs: Theory, Algorithms and Applications},
  edition   = {2},
  publisher = {Springer London},
  year      = {2009},
  doi       = {10.1007/978-1-84800-998-1},
  url       = {https://doi.org/10.1007/978-1-84800-998-1}
}

@article{Ebert1988ComputingEulerianTrails,
  author  = {J?rgen Ebert},
  title   = {Computing Eulerian trails},
  journal = {Information Processing Letters},
  volume  = {28},
  number  = {2},
  pages   = {93--97},
  year    = {1988},
  doi     = {10.1016/0020-0190(88)90170-6},
  url     = {https://doi.org/10.1016/0020-0190(88)90170-6}
}