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

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

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.