Minimal Cost of Eulerian Path

Question

Problem:

Given a planar (undirected and mostly sparse) graph with an Eulerian Path, we introduce a cost function f: (v, e1, e2) for all two edges e1 and e2 that share a vertex v. The function also fulfills f(v, e1, e2) = f(v, e2, e1)

For an Eulerian Path we then define the overall cost as the sum of costs of all path-neighboring edges and the vertex in-between.

The goal is to obtain an Eulerian Path that has a minimal total cost. This has to be done somewhat efficiently, so testing all paths is not an option. Ideally answers should outline an algorithm.

Background:

The goal is to find a path that is "smooth". An example here is the B point in the image below. The flow is a lot smother if we go clockwise through the loop when coming from C.

Thoughts:

I think it is important to understand how many variations exist for an Eulerian Path and how we would obtain them.

1. There exists one very obvious variation, which is changing the direction of the path. We don't need to consider this variation since f(v, e1, e2) = f(v, e2, e1)
2. For any vertex with 0,..,n incoming and n,..,0 outgoing path segments, the path can be altered by swapping the ith incoming with the ith outgoing edge for i in 0,..,n. However this needs some alterations when the start/end vertex is included as well. Maybe we can just ignore it. Example: Point B and D
3. We can further swap "inner pairings with outer pairings", i.e. ith incoming and ith outgoing can be swapped with jth incoming and jth outgoing respectively for i, j in 1,..,n. Again we need to ignore start/end edge. This rule only applies if >= 6 edges join in a single vertex.

It becomes more difficult when the cycles from the vertex overlap, because then we can swap between them as well. Or do we not need to consider this at all? It's getting complicated and I'm no longer sure about correctness. So I’m kind of stuck.

• Can we somehow convert this into an optimization problem?
• Are there any papers on this topic? I couldn't find any.
• Should I approach the problem completely different?
• Can we somehow achieve minimal cost while executing Fleury's or Hierholzer's algorithm?

---

Edit (Aug 7 '17)

This presentation seems very interesting: https://www.cs.rochester.edu/~stefanko/Talks/EULER.pdf Unfortunately I wasn't able to find a paper accompanying it. At least counting Eulerian Cycle is #P-Complete.

Considering finding a minimum Eulerian Cycle for simplicity and using the idea of the Hierholzer's algorithm, we can find all simple cycles in the graph efficiently using e.g. http://www.cs.tufts.edu/comp/150GA/homeworks/hw1/Johnson%2075.PDF

We would then need to find the edge-disjoint edge cycle cover. But this still doesn't guarantee a minimal path or Eulerian Cycle, because we still have to fuse the sub-cycles together.

---

Edit (Jan 7 '18)

I've started looking at solving this for an Eulerian Cycle since we have to consider fewer edge cases and the cycle problem is easily converted into the path problem (see here).

There have been suggestions to solve this by optimizing for each node. However, as the next example shows (colors indicate Eulerian Cycle), the local optima "battle" for each other. The top node uses the local optima, however if we were to use the optimum for both nodes we would obtain two circles and no longer have an Eulerian path.

I'm thinking maybe we can break the Eulerian Cycle into several "locally optimal" walks and then fuse them together again (efficiently we could find those walks using the Hierholzer's algorithm and following the lowest cost edge). Not guaranteed to be optimal though I think (or is it if we fuse them optimally?).

What's next? I'll try to save up for a bounty to give this question some more exposure.

---

Edit (Nov 6 '18)

Still looking for an answer. I will try to implement my technique suggested above next. I'm no longer looking for a perfect algorithm, but one that approximates the solution.

Answer 1

The Eulerian cycle problem with "transition" costs $f$ is NP-hard by reduction from the Traveling Salesman Problem (TSP). Specifically, for any TSP instance given as a complete weighted graph on vertices $V = \{v_1,v_2,...,v_n\}$, encoded via the cost function $d : V \times V \rightarrow \cal{R}$, we can transform this into your problem in polynomial time as follows.

First, create a graph with a single "anchor" vertex $x$. Then, for each vertex $v_i \in V$, create a (self-looping*) edge $e_i = (x,x)$ with cost 0 (you can envision these self-loops as the separate "petals" of a flower-like graph in two-dimensions anchored around $x$). Finally, create a transition function $f$ (as per your definition) such that $f(x, e_i, e_j) = d(v_i, v_j)$. All Eulerian cycles (with transition costs from $f$) in this case are thus in 1:1 correspondence with all Hamiltonian cycles (i.e., solutions) of the original TSP instance and have equivalent cost. So if you can find a minimum-cost Eulerian cycle with such transition costs, then you can solve TSP to optimality, completing the reduction.

*Note that the self-looping edge encoding is not necessary, but it simplifies the description somewhat for the purposes of discussion above just to give the intuition (and your encoding seems to allow this). These self-loops can actually be broken up into separate "triangle" sub-graphs ($K_3$ gadgets), all anchored at the shared node $x$ whose edge transitions to other such gadgets are assigned costs accordingly from $d$ (but in a slightly-more-detailed manner).