3
$\begingroup$

In a Python plotting application,

I have an undirected connected graph, not necessarily simple, that I'd like to cover with paths such that each edge is contained in exactly one path.

The number of nodes/edges will typically be a few hundred or a few thousand. One solution is to create a new path for every edge, but that's a little too rough. Ideally I'd find the minimum number of paths, but I get the notion that this might be NP-hard (see the Hamiltonian path problem, traveling salesman problem, this question etc.). Any practical heuristic is good enough.

Any hints?

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ Also asked here: math.stackexchange.com/questions/2028594/… One suggested answer is to reduce the problem to a flow problem (thereby solving it in polynomial time): add artificial source s and sink t each connected to all vertices (with infinite-capacity edges), give every previously existing edge a capacity and lower bound of 1, then ask for a minimum-size feasible flow (this can be found via linear programming or existing flow algorithms). For an absolute bound see doi.org/10.1006/jctb.1996.0012 $\endgroup$
    – Neal Young
    Oct 14, 2021 at 13:27
  • $\begingroup$ p.s. That first link also suggests a fast greedy algorithm, but it's not clear that it gives the optimal solution for every instance. $\endgroup$
    – Neal Young
    Oct 14, 2021 at 13:36
  • $\begingroup$ The question in the link asks about simple graphs, in my case there may (and will) be loops. Anyway, the greedy approach might just work. $\endgroup$
    – Nico Schlömer
    Oct 14, 2021 at 13:41
  • $\begingroup$ I assume you want simple paths? Suppose graph is Eulerian. We have a single closed walk. I assume you wouldn't want that, right? $\endgroup$
    – Chandra Chekuri
    Oct 14, 2021 at 15:43
  • $\begingroup$ @ChandraChekuri Simple would be nice, but repeating vertices aren't a show-stopper. I cannot allow repeating edges though. The graph can be non-Eulerian. $\endgroup$
    – Nico Schlömer
    Oct 14, 2021 at 17:42

2 Answers 2

Reset to default
6
$\begingroup$

Found the following paper "NP-completeness of some problems of partitioning and covering in graphs" by B.Péroche.

The paper proves that deciding whether the edges of a graph can be partitioned into two simple paths is NP-Complete. I haven't looked at the reduction but it may also prove that finding the min number of paths may be hard to approximate to a large factor.

The OP said that partitioning into trails is acceptable (a trail is a walk that can repeat vertices but not edges). If $G$ is connected and Eulerian then there is a single trail that contains all edges which is optimum. Suppose $G$ is not Eulerian and say it has $2k$ odd-degree vertices. Then it is easy to see that one needs at least $k$ trails to partition the edges since each odd degree vertex must be the end point of one of these trails. It seems that this achievable easily as follows. Add an arbitrary matching on the $2k$ odd-degree vertices. Now it becomes Eulerian. Take the Eulerian trail which now contains the $k$ matching edges. We can assume that the first edge in the trail is a matching edge. Removing these $k$ matching edges should give $k$ trails that partition all the original edges.

Improve this answer
$\endgroup$
2
  • $\begingroup$ The OPs problem is related to Gallai's conjecture which says that in any simple connected graph there is a partition of the edges into $\lceil n/2 \rceil$ paths where $n$ is the number of nodes. According to Bondy it is one of the beautiful conjectures in graph theory. ime.usp.br/~pf/grafos-exercicios/bondy-conjectures/… . Lovasz proved that one can always partition into $\lceil n/2 \rceil$ paths and cycles which implies an upper bound of $n+1$. $\endgroup$
    – Chandra Chekuri
    Oct 15, 2021 at 11:50
  • $\begingroup$ It appears that the best bound known for Gallai's conjecture is $\lceil 2n/3 \rceil$. The introduction of the paper arxiv.org/abs/1911.05501 has a nice discussion with several useful pointers and fascinating questions on graph decomposition into paths and cycles. $\endgroup$
    – Chandra Chekuri
    Oct 15, 2021 at 13:45
2
$\begingroup$

Just a partial answer. Gallai's conjecture was recently proven for planar graphs: https://arxiv.org/abs/2110.08870.

The paper gives an algorithm to find the $\lceil \frac{n}{2}\rceil$ desired paths. It is "polynomial" (it uses a "black-box" for finding $K_5$ subdivisions, I don't know if it can be done polynomially). However, I think that it is too complex to be implemented.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Thanks for the pointer. $\endgroup$
    – Chandra Chekuri
    Nov 15, 2021 at 19:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.