Non-brute force algorithm for a Eulerian like path

Question

I have a graph with an arbitrary amount of edges and vertexes. Each vertex having an arbitrary amount of edges connecting to it but in practice the number is usually around 3 or 4 no less than one and no more than a dozen. I want to find the path that goes to as many vertexes and edges as possible without using any edge more than once.

In addition there are a few special cases that I would like to add but an algorithm that doesn't solve for these is fine:

• There are pairs of vertexes that are connected with multiple edges. I can traverse multiple of these edges but I cannot immediately return to the previous vertex I was at without first going to another vertex.
• There are some edges that are one way.
• Some vertexes will change the destination of edges connected to themselves depending on the edge you arrived from. In practice this is always a vertex with two edges that if arrived from one edge will change the other edge to return to the source of the first edge and if arrived from the other edge the first will not change. In theory it doesn't have to be though.

I know this problem cannot be solved in polynomial time and I have thought of ways to speed up the brute force method I am just wondering if anyone else has any ideas.

Answer 1

Regarding the problem of visiting as many vertices/edges as possible without using any edge twice: one can look at this problem as the problem of finding an Eulerian subgraph with a maximum number of vertices/edges. Or alternatively, as the problem of deleting a minimum number of vertices/edges so as to make a graph Eulerian.

You might be interested in the following paper, which studies the complexity of such problems in detail. In particular, they show several polynomial-time solvable or fixed-parameter tractable cases. In particular, the edge deletion problems are solvable in n^3 time if a constant number of edge deletions is sufficient.

https://doi.org/10.1007/s00453-012-9667-x