<p>Just a partial answer. Gallai's conjecture was recently proven for planar graphs: <a href="https://arxiv.org/abs/2110.08870" rel="nofollow noreferrer">https://arxiv.org/abs/2110.08870</a>.</p>
<p>The paper gives an algorithm to find the <span class="math-container">$\lceil \frac{n}{2}\rceil$</span> desired paths. It is &quot;polynomial&quot; (it uses a &quot;black-box&quot; for finding <span class="math-container">$K_5$</span> subdivisions, I don't know if it can be done polynomially). However, I think that it is too complex to be implemented.</p>

CC BY-SA 4.0
2021-11-15T19:26:24.810Z
Thanks for the pointer.
Chandra Chekuri
CC BY-SA 4.0
2021-11-15T18:24:46.497Z
2021-11-15T18:24:46.497Z
Lamine
<p>Found the following paper <a href="https://www.sciencedirect.com/science/article/pii/0166218X8490101X" rel="noreferrer">&quot;NP-completeness of some problems of partitioning and covering in graphs&quot;</a> by B.Péroche.</p>
<p>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.</p>
<p>The OP said that partitioning into trails is acceptable (a trail is a walk that can repeat vertices but not edges). If <span class="math-container">$G$</span> is connected and Eulerian then there is a single trail that contains all edges which is optimum. Suppose <span class="math-container">$G$</span> is not Eulerian and say it has <span class="math-container">$2k$</span> odd-degree vertices. Then it is easy to see that one needs at least <span class="math-container">$k$</span> 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 <span class="math-container">$2k$</span> odd-degree vertices. Now it becomes Eulerian. Take the Eulerian trail which now contains the <span class="math-container">$k$</span> matching edges. We can assume that the first edge in the trail is a matching edge. Removing these <span class="math-container">$k$</span> matching edges should give <span class="math-container">$k$</span> trails that partition all the original edges.</p>

CC BY-SA 4.0
2021-10-15T11:50:01.443Z
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. https://www.ime.usp.br/~pf/grafos-exercicios/bondy-conjectures/beautiful.pdf . Lovasz proved that one can always partition into $\lceil n/2 \rceil$ paths and cycles which implies an upper bound of $n+1$.
Chandra Chekuri
CC BY-SA 4.0
2021-10-15T13:45:49.010Z
It appears that the best bound known for Gallai's conjecture is $\lceil 2n/3 \rceil$. The introduction of the paper https://arxiv.org/abs/1911.05501 has a nice discussion with several useful pointers and fascinating questions on graph decomposition into paths and cycles.
Chandra Chekuri
CC BY-SA 4.0
2021-10-15T01:30:21.243Z
2021-10-15T01:30:21.243Z
Chandra Chekuri
<p>In a Python plotting application,</p>
<blockquote>
<p>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.</p>
</blockquote>
<p>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 <a href="https://en.wikipedia.org/wiki/Hamiltonian_path_problem" rel="nofollow noreferrer">Hamiltonian path problem</a>, <a href="https://en.wikipedia.org/wiki/Travelling_salesman_problem" rel="nofollow noreferrer">traveling salesman problem</a>, <a href="https://cstheory.stackexchange.com/q/40344/64695">this question</a> etc.). Any practical heuristic is good enough.</p>
<p>Any hints?</p>

CC BY-SA 4.0
2021-10-14T13:27:07.830Z
Also asked here: https://math.stackexchange.com/questions/2028594/minimum-number-of-edge-disjoint-paths-needed-to-cover-a-graph
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 https://doi.org/10.1006/jctb.1996.0012
Neal Young
CC BY-SA 4.0
2021-10-14T13:36:06.457Z
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.
Neal Young
CC BY-SA 4.0
2021-10-14T13:41:26.893Z
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.
Nico Schlömer
CC BY-SA 4.0
2021-10-14T15:43:47.840Z
I assume  you want simple paths? Suppose graph is Eulerian. We have a single closed walk. I assume you wouldn't want that, right?
Chandra Chekuri
CC BY-SA 4.0
2021-10-14T17:42:08.053Z
@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.
Nico Schlömer
CC BY-SA 4.0
2021-10-14T21:15:04.503Z
The greedy algorithm suggested there seems to be for non-simple graphs, as it suggests using paths that repeat vertices.  And BTW now that I look more closely, the flow-based answer there probably only works for *directed* graphs...
Neal Young
CC BY-SA 4.0
2021-10-15T07:34:57.500Z
@NealYoung The proposed flow solution will not work, since a flow may use cycles.
Kristoffer Arnsfelt Hansen
<graph-theory><graph-algorithms>
exact path cover for undirected graph
Nico Schlömer
# exact path cover for undirected graph

(Asked by: username_0 on 2021-10-14)

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](https://en.wikipedia.org/wiki/Hamiltonian_path_problem), [traveling salesman problem](https://en.wikipedia.org/wiki/Travelling_salesman_problem), [this question](https://cstheory.stackexchange.com/q/40344/64695) etc.). Any practical heuristic is good enough.

Any hints?

**Tags:** graph-theory, graph-algorithms
> **Comments:**
> **username_1**: Also asked here: https://math.stackexchange.com/questions/2028594/minimum-number-of-edge-disjoint-paths-needed-to-cover-a-graph 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 https://doi.org/10.1006/jctb.1996.0012  
> **username_1**: 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.  
> **username_0**: 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.  
> **username_2**: I assume  you want simple paths? Suppose graph is Eulerian. We have a single closed walk. I assume you wouldn't want that, right?  
> **username_0**: @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.  
> **username_1**: The greedy algorithm suggested there seems to be for non-simple graphs, as it suggests using paths that repeat vertices.  And BTW now that I look more closely, the flow-based answer there probably only works for *directed* graphs...  
> **username_3**: @NealYoung The proposed flow solution will not work, since a flow may use cycles.  

---

## 2 answers

### Answer by username_2 on 2021-10-15. Score: 6 | Accepted answer

Found the following paper ["NP-completeness of some problems of partitioning and covering in graphs"](https://www.sciencedirect.com/science/article/pii/0166218X8490101X) 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.

> **Comments:**
> **username_2**: 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. https://www.ime.usp.br/~pf/grafos-exercicios/bondy-conjectures/beautiful.pdf . Lovasz proved that one can always partition into $\lceil n/2 \rceil$ paths and cycles which implies an upper bound of $n+1$.  
> **username_2**: It appears that the best bound known for Gallai's conjecture is $\lceil 2n/3 \rceil$. The introduction of the paper https://arxiv.org/abs/1911.05501 has a nice discussion with several useful pointers and fascinating questions on graph decomposition into paths and cycles.  

---

### Answer by username_4 on 2021-11-15. Score: 2

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.

> **Comments:**
> **username_2**: Thanks for the pointer.  

---

