How to find maximal eulerian subgraph of a given graph? By "maximal" I mean subgraph with maximal number of edges, vertices, or both. My idea is to find basis of cycle space and combine basis cycles in a proper way, but I don't know how to do it (and is it a good idea or not).
UPD. Source graph is connected.
Some thoughts. Graph is eulerian iff it is connected (with possible isolated vertices) and all vertices have even degree.
It is 'easy' to satisfy second criteria by removing (shortest) paths between pairs of odd degree vertices.
Connectivity is problematic since removing edges can produce unconnected graph.
An example which shows that 'simple' (greedy) solution is not easy to produce. Modify complete graph K5 by splitting each edge in two edges (or more). Take two these modified K5 graph and from each one take two vertices (A, B from first and C, D from second). Connect A-C and B-D. Greedy approach would remove these added edges since they are the shortest paths. With that graph becomes unconnected. Solution would be to remove paths A-B and C-D.
It seems to me that algorithm should take a care about subgraph connectivity while removing edges. For sure algorithm should preserve that each subset of odd degree vertices, of which no pair are used to remove path between them, should have connectivity larger than cardinality of subset.
I would try (for a test) with recursive brute force solution with optimization. O is list of odd degree vertices.
def remove_edges(O, G):
if O is empty:
return solution
for f in O:
for t in O\{f}":
G2 = G without path edges between (f,t)
if G2 is unconnected:
continue
return remove_edges(O\{f,t}, G2)
Optimization can be to order sets O and O{f} by vertices that have shortest paths. That can be done by finding shortest lengths between all pairs of vertices from O before removing edges. That can be done by BFS from each O vertex.