Decompose undirected graph to minimum paths and cycles

Question

I would like to decompose undirected graph into a minimum number of paths and cycles that are edge-disjoint.

My idea is to first take longest paths, but it is not polynomial.

Do you know any polynomial algorithm?

Answer 1

You might be interested in the "chain decomposition" of a graph, as described by Jens Schmidt.

It's mentioned in this wikipedia article on Ear Decompositions. I've implemented it myself, and it's a nice simple algorithm.

Answer 2

could be fun is to use max flow / minimum cut - cut the graph in half using the least amount of cuts - do this a few times recursively until you get tractable sized subsets to run your longest path algorithm on.