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

  • 3
    This is a special case of min-cost flow, were all edge capacities are $1$ and all edge costs are $-1$. – Gamow May 4 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 at 15:11
up vote 5 down vote accepted
  • 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

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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