How to find long trails in a multidigraph

Question

I have a directed multigraph (a multigraph is a graph that can have more than one edge between any two nodes). In Wikipedia's terminology, this is a directed multigraph (edges without own identity). I want to find its longest directed trails (a directed trail is a directed walk in which all edges are distinct). I.e., I'm looking for long walks with repeated nodes, but distinct edges.

Note that this is an NP-hard problem. Otherwise, I would have asked for the longest trails, not merely long trails.

My graph has no weights and it is weakly connected (that is, if each edge were converted to an undirected edge, that undirected graph would be connected).

I define walk/trail/path length as the number of edges in the walk.

My current program is based on traversing the graph in a DFS-like manner. If allowed to run for, e.g., half an hour, it produces trails of less than satisfactory length, and I know that longer trails should be possible in that time budget.

Note that this problem is quite similar to the problem of finding the longest path of a directed graph, but with each edge having a max allowed visits number associated with it, equal to the cardinality of the corresponding edge set in the multidigraph.

In fact, it's possible to transform my problem to the longest path problem by producing the line graph of my graph and then finding its longest paths. However, I'm hoping for a smarter, more efficient solution.

The reason I'm mentioning the digraph longest path problem is that there are certain smart solutions to that problem, but they don't seem to translate to my multidigraph longest trail problem, sadly. In particular, I'm thinking of Miguel Raggi's Arxiv paper, finding long simple paths in a weighted digraph using pseudo-topological orderings. Those and other solutions are based on finding the longest path of a DAG subgraph (or, equivalently, some feedback arc set), which seems inapplicable to my problem (unless I do the mentioned line graph transformation), but I'd be happy for somebody here to prove me wrong.

What am I looking for, then?

Either of these two:

1. some method of finding long trails in my multidigraph, smarter than the naive approach.
2. some method of finding long paths in my multidigraph's line graph; but it should be more efficient than just looking for an arbitrary digraph's longest paths, i.e., it should take into account the fact that the graph that is being searched through is a line graph.

Some characteristics of my graph

It's got around 500 nodes and around 20000 edges. If the multiple edges are accounted for, the graph's got around 160000 edges.

Some characteristics of my graph's condensation

I don't know if the info on the condensation is relevant, but it might be. See the Wikipedia page for strongly connected components for definitions and examples of graph condensations.

There are less than 200 strongly connected components (equivalently, the condensation has less than 200 nodes), and the condensation's got around 220 edges. One of the SCCs consists of more than 300 original nodes, while every other SCC has only a single original node.

Info about node in-degree and out-degree over all nodes

This too is of dubious importance, but it may be useful. The images are just thumbnails that link to the full-sized plots (made with Vega-Lite):

         

Note about the scatterplots: each point in the scatterplots is "transparent" so that if there's only one data point in the same point of the plot it's displayed less prominently than if there are multiple in the same position.

Answer 1

Here's a suggestion for a simple greedy heuristic to apply to the big SCC. It's based on the observation that a cycle of edges can be traversed a number of times equal to the minimum multiplicity of any edge in the cycle, so looking for cycles in which all edges have large multiplicity may be a good strategy:

1. Order edges in the big SCC in decreasing order by multiplicity. Call this list of edges $X$. (Note: Each edge appears in $X$ just once, regardless of its multiplicity.)
2. Set $Y$ to be an empty list of edges.
3. If no edges remain in $X$, go to 7.
4. Choose the edge $e$ with highest multiplicity remaining in $X$. Remove it from $X$ and add it to $Y$.
5. Test whether $Y$ now contains a cycle (since this cycle must contain $e$, this check can be done quickly using a union/find data structure): If so, let $Z \subseteq Y$ be the edges in this cycle. Add the pair $(Z, m)$ to the set $C$, where $m$ is the minimum multiplicity of any edge in $Z$, clear out $Y$ and start over (recurse) with $X\setminus Z$.
6. Otherwise, go to 3.
7. At this point, we have a set of edge-disjoint cycles in $C$, as well as the maximum number of times each can be completely traversed. Note that if $(Z, m) \in C$, then the cycle $Z$ can be entered at any of its vertices, traversed $m$ times, and then exited at the same vertex; or entered at any vertex, traversed $m-1$ times, then (possibly after a further partial traversal) exited from any vertex, giving us some flexibility.
8. Find the vertex $v_1$ that is shared by the largest number of cycles in $C$; let these cycles be $C_1 \subseteq C$. If $C_1 = C$ then stop here: We can start at $v_1$ and traverse each cycle the full number of times in any order.
9. Otherwise, find the vertex $v_2$ that is shared by the largest number of cycles in $C\setminus C_1$ and is adjacent to $v_1$. Repeat this for $v_3$, etc., until $C$ is exhausted.
10. Starting at $v_1$, for each $i$ in increasing order, and for each cycle $C_{ij} \in C_i$ (in no particular order), add either $m_{ij}$ or $m_{ij}-1$ traversals of $C_{ij}$ to the the trail, whichever is larger and still allows us to stop at $v_{i+1}$ in preparation to begin traversing the following set of cycles.

Since the procedure is fairly quick, it may be worthwhile to rerun it many times, choosing a different order of edges each time, and pick the best overall.