1
$\begingroup$

Problem definition

I have a directed graph $G = (V,E)$, with positive weights $w(e)>0\:s.t\:\forall e \in E$

I would like to find the longest walk (i.e. edges and nodes may be repeated) in terms of most accumulated weight, under the condition that once an edge $e$ is traversed, its weight will become its own negative weight, $-w(e)$.

A few notes:

  • I did not prove it, but I believe this walk to exist. There's no infinite walk since all edges will become negative after at most $|E|$ steps.
  • If it makes it any easier, we can assume this $G$ is strongly connected.

My attempts so far. You can likely skip this, but it might help someone

A greedy solution, inspired by the solution to the Chinese Postman Problem (1):

  1. Extract the flow graph $F$ from the CPP solution for directed graphs suggested by Wikipedia (1),such that $F=(V,E')$ is a subgraph of $G$ with edges $E'$ from $u\in V\:s.t. outdegree(u)<indegree(u)$ (now called $NEG$) to vertices $v\in V\:s.t. outdegree(v)>indegree(v)$ (now called $POS$).
  2. For every pair $(neg,pos)\:s.t. neg\in NEG\:and\:pos\in POS$
    1. Calculate: (a) the shortest path from $neg$ to $pos$ in $F$ (This path will be duplicated in $G$, so the shorter the better), and (b) the shortest path from $pos$ to $neg$ in $G$ (the worst case of weight gain from duplicating the edges along (a))
    2. If (a)>(b), I assume that adding the extra traversals is not worth it, so I remove the edges of (b) from $G$.
  3. Run the CPP solution from (1) on $G$ with the pruned edges.

This algorithm is greedy and doesn't sound optimal to me, but it does improve my results.

Bellman-Ford

I also tried something based on Bellman-Ford, but anything related to dynamic programming doesn't work for me, likely because my memory is "conditional" on which nodes I have traversed.

Dynamic Shortest Path

I tried looking at solutions for dynamic shortest path (In this case our problem is both incremental and decremental, since we need to remove an edge after it's traversed, and add the same edge with negative weight), but these seem very complicated, not to mention that they're for the shortest, not the longest path.

Incorporating CPP - A Better Attempt:

  1. In the original solution to CPP, we augment $G$ with the additional edges from $F$, let's call this new graph $G'$. For every new edge $e$ we add, we should set its weight to be $-w(e)$.
  2. The longest trail in $G'$ (Not walk anymore, since $G'$ already contains the necessary duplicate edges to traverse the entire graph and is Eulerian) should translate to the longest walk in $G$.

This attempt is the most promising to me, but I don't know how to implement longest trail with duplicate vertices (The algorithms I've found online look for trails rather than path, and may duplicate edges). Also, I was hoping that maybe the relation to CPP could help me find a polynomial-time solution rather than an NP-Hard one.

I rarely post, and I tried hard to make this question clear and readable, please let me know if anything needs editing. Thanks.

$\endgroup$
2

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.