Relaxed path decomposition of a graph

Question

Definition

Given a directed connected graph $G$ without multiple edges or self loops. We call a final path of $G$ a path ending with a vertex with no successor (the path can not be extended anymore) or ending with a vertex which is already in the path (path returned to an already visited vertex).

Given $v$ a vertex of $G$ we define $F_v(G)$ to be set of all final paths starting from $v$. And for every $p\in F_v(G)$ we denote by $E(p)$ the set of arcs (edges) of $p$.

Question

Does there exists an algorithm that returns for any directed connected graph $G=(V,E)$ and a given initial vertex $v\in V$ a set of final paths $F\subseteq F_v(G)$ such that: $$\bigcup_{p \in F} E(p)=E$$ ?

Additional notes:

• The paths are not supposed to be disjoint
• Any vertex of $G$ can be reached from the initial vertex $v$
• The graph $G$ is small ($|V|\approx 10$)
• The best solution returns a set of $F$ of small cardinality.

---

As an example if we have $G$ the following graph and $v=A$ :
+---+ +---+ +---+ | A +--------> | B +-----> | C | +---+ +---+ +-+-+ |^ | || +---+ | +---+ |+---+ D | <-+ | E | <----+ +---+ +---+ the algorithm could return $F=\{(A,B)(B,C)(C,D)(D,B),(A,B)(B,E)\}$ or better : $$F=\{(A,B)(B,C)(C,D)(D,B)(B,E)\} $$

Closely related problems

• Longest path problem
• Path decomposition problem
• Path-cycle decompositions
• Route inspection problem

Answer 1

Let $G = (V, E)$ be a digraph. We define a "rho of length $k$" as a finite sequence of $k$ vertices, each a neighbor of its predecessor, where exactly one of the following two conditions hold

1. All $k$ vertices are distinct, and the last vertex has no neighbors.
2. The first $k-1$ vertices of the sequence are distinct, and the last vertex is one of the first $k-1$ members of the sequence.

Let $R(G)$ be the set of all rhos contained in $G$. Given $\rho \in R(G)$ by abuse of notation define $E(\rho)$ to be the edges of $\rho$. Extending the notation $R$, let $R(G; v)$ be the set of all rhos in $G$ whose initial vertex is $v$. We describe the "Rho Cover Problem" for a graph $G$ and vertex $v$ as the problem of finding the smallest set of rhos which start at $v$ and cover the edges of $G$.

Mathematically speaking, we can exhaustively check all subsets of $\{E(\rho) : \rho \in R(G; v)\}$, note the ones which cover $E$, and return one of minimal cardinality. The conditions to show such a subset exists were addressed David Eppstein: for all edges $(w,z)$ in $G$ there must be a path from $v$ to $w$.

From a computer science perspective you can now ask if there is an "easy" solution. My expectation is that answering this question would involve either finding a polynomial time algorithm for this problem (in which case it would be "easy") or showing the problem is NP-complete (in which case it would be "hard"). This would be best answered in either cs or cstheory depending on the caliber of the question (which I cannot judge).

From a programming perspective, you seem to be asking for a practical way to solve this problem for graphs with approximately 10 vertices. With so few vertices you can enumerate every rho v̶i̶a̶ ̶a̶ ̶d̶e̶p̶t̶h̶ ̶f̶i̶r̶s̶t̶ ̶s̶e̶a̶r̶c̶h̶ and consider the Rho Cover Problem as a special instance of the Set Cover Problem. As noted in the Wikipedia article on the Set Cover Problem this can be expressed as an Integer Linear Programming Problem. To solve such a problem I would recommend an academic licence of Gurobi. I have found it to be an extremely powerful piece of software designed first and foremost for optimization.

Best of luck.

Answer 2

No, because your assumptions are not strong enough to ensure that all edges belong to final paths. For instance, if the graph has any edges into $v$ itself, then these edges cannot belong to final paths starting from $v$.

On the other hand, it is trivial to find (in polynomial time) a set of final paths that cover all edges that can be covered. Given $G$ and $v$, for each edge $e=(u,w)$ test whether $u$ is reachable from $v$ in $G-w$. If so, find a path from $v$ to $u$ in $G-w$, add the edge $e$, and then continue greedily until stuck to find and output a final path containing $e$. If not, there can be no final path containing $e$.