## 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