'How to find maximal eulerian subgraph?
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.
Solution 1:[1]
It is proved in 1979 that determining if a given graph contains a spanning Eulerian subgraph is NP-complete. Ref: W. R. Pulleyblank, A note on graphs spanned by Eulerian graphs, J. Graph Theory 3, 1979, pp. 309–310,
Please refer to this
Finding the maximum size (number of edges) of spanning Eulerian subgraph of a graph (if it exists) is an active research area.
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|---|
| Solution 1 | rootShiv |