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.

enter image description here

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.

Circles

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.

  • This problem is NP-complete. I don't have a simple proof, which is why this is a comment and not an answer, and of course you don't have to believe me without proof, but that should help direct people in the right direction. The reason I believe this is that I have a complicated reduction in mind (and am too lazy to write it up). – Mikhail Rudoy Aug 5 '17 at 2:21
  • @MikhailRudoy I would have guessed that we can iteratively improve the solution. But basically you are saying that vertex edge choices heavily influence each other. Very curious if someone can come up with a proof. Feel free to sketch your idea more! – vincent Aug 5 '17 at 2:34
  • @MikhailRudoy Would this change if we assumed that the graph is planar / with coordinates? I found this question very interesting: math.stackexchange.com/questions/8140/… – vincent Dec 24 '17 at 18:21
  • 1
    The reduction that I'm thinking of also works if the graph is planar and the vertices are specified by coordinates. The reason I'm being too lazy to write it up is that the reduction is not from a well known problem but rather from a problem I made up called TRVB which people are generally not familiar with (see arxiv.org/abs/1706.07900). The key idea of the reduction is to simulate an "edge" in a TRVB instance using two parallel paths of degree-2 vertices in your problem and simulate a "breakable vertex" using a single vertex in your problem. – Mikhail Rudoy Dec 27 '17 at 4:48

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).

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.