# Is this a variant of “Path Covering”?

According to 1, "a path cover of a directed graph G is a set of disjoint paths in G which together contain all the vertices of G".

In my research, I met a similar problem. There, you can add and subtract paths in G, and, should cover $$G$$ (exactly once) by a combination of addition of subtraction of a subset of paths in $$G$$.

Is this problem a variant of path covering? What is the name of this type of problems?

I try to set the problem formally. $$V=\{v_1,v_2,\cdots,v_{|V|}\}$$is a vertex set and $$G=(V,E)$$ is a directed graph. Let $$\mathcal{P}$$ be a set of all path in $$G$$. Let $$P = \{p_i\}_{i=1,2,\cdots,|P|} \subset \mathcal{P}$$.

For $$p∈ \mathcal{P}$$, $$vec(p)∈ \mathbb{Z}^{|V|}$$ denotes a vector of which $$i$$-th element is $$1 (0)$$ if the path $$p$$ contains (does not contain) the vertex $$v_i$$. For example, if $$V=\{v_1,\cdots,v_6\}, p \text{ is a path as: }v_1\to v_3 \to v_5$$ then $$vec(p)=(1,0,1,0,1,0)$$

The problem is you need find the vector $$(a_1,a_2,\dots,a_{|P|})∈ \mathbb{Z}^{|P|}$$ such that $$\sum_{i=1}^{|P|}a_i vec(p_i) = (1,1,1,\cdots,1)∈ \mathbb{Z}^{|V|}.$$

For example, if you have $$G$$ and $$P$$ shown in the following figure, then $$(a_1,a_2,a_3) = (1,-1,1)$$ because (intuitively) $$p_1 - p_2 + p_3 = V$$.

I think the problem becomes bit interesting if you add some constraints for $$P$$. For my case, $$P = \{p \mid v_i ∈ V, vert(p) = {v_i}\cup anc(v_i)\},$$ where $$vert(p)$$ is a set of vertices that are contained in $$p$$, and $$anc(v)$$ denotes a set of vertices that are ancestors of $$v_i$$

1 Diestel, "Graph Theory 5th ed." p.52.

• Your problem makes sense and it generalizes path covering if you add every single vertex as a path, and that you can subtract single vertices several times over. A path cover is allowed to "cover" the same vertex many times. – Pål GD Apr 6 at 13:44