Partition edges into edge disjoint walks

Question

Consider an undirected graph $G=(V,E)$ and two sequences of $k$ vertices $S=s_1,\ldots,s_k$ and $T=t_1,\ldots,t_k$. A set of $k$ walks is called a $(S,T)$-walk partition if

1. the walks form a partition the edges of $E$, and
2. there exists a permutation $\pi:[k]\to[k]$, such that the $i$th walk is a $s_it_{\pi(i)}$-walk. (A $st$-walk is a walk that starts with vertex $s$ and ends with vertex $t$)

We consider the following problem.

$k$-walk partition

Input: Graph $G$ and two sequence of $k$ vertices $S$ and $T$.

Output: Does there exists a $(S,T)$-walk partition in $G$.

Is this problem studied? I'm interested when $k$ is a constant. When $k=1$, this is the same as checking if there is a Eulerian trail from $s_1$ to $t_1$.

Answer 1

• Create a new source and connect it to $s_1,\ldots,s_k$, and create a new sink and connect it to $t_1,\ldots,t_k$.

• Every edge has capacity $1$ and cost $−1$.

• With this, the problem is a special case of the min-cost flow problem.