2
$\begingroup$

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$. Example of G

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$ – Pål GD Apr 6 at 13:44

Your Answer

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

Browse other questions tagged or ask your own question.