# Partition edges into edge disjoint walks

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$.

• This is a special case of min-cost flow, were all edge capacities are $1$ and all edge costs are $-1$. – Gamow May 4 '18 at 8:14
• @Gamow make this an answer? I wonder if there are simpler characterizations like the case of $k=1$. – Chao Xu May 4 '18 at 15:11

• 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$.