<ul>
<li><p>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$.</p></li>
<li><p>Every edge has capacity $1$ and cost $−1$.</p></li>
<li><p>With this, the problem is a special case of the min-cost flow problem.</p></li>
</ul>

CC BY-SA 4.0
2018-05-04T16:39:37.737Z
2018-05-04T16:39:37.737Z
Gamow
<p>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 </p>

<ol>
<li>the walks form a partition the edges of $E$, and</li>
<li>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$)</li>
</ol>

<p>We consider the following problem.</p>

<blockquote>
  <p><strong>$k$-walk partition</strong></p>
  
  <p><strong>Input:</strong> Graph $G$ and two sequence of $k$ vertices $S$ and $T$.</p>
  
  <p><strong>Output:</strong> Does there exists a $(S,T)$-walk partition in $G$.</p>
</blockquote>

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

CC BY-SA 4.0
2018-05-04T08:14:04.117Z
This is a special case of min-cost flow, were all edge capacities are $1$ and all edge costs are $-1$.
Gamow
CC BY-SA 4.0
2018-05-04T15:11:33.760Z
@Gamow make this an answer? I wonder if there are simpler characterizations like the case of $k=1$.
Chao Xu
<graph-theory><graph-algorithms>
Partition edges into edge disjoint walks
Chao Xu
# Partition edges into edge disjoint walks

(Asked by: username_0 on 2018-05-03)

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

**Tags:** graph-theory, graph-algorithms
> **Comments:**
> **username_1**: This is a special case of min-cost flow, were all edge capacities are $1$ and all edge costs are $-1$.  
> **username_0**: @Gamow make this an answer? I wonder if there are simpler characterizations like the case of $k=1$.  

---

## 1 answers

### Answer by username_1 on 2018-05-04. Score: 5 | Accepted answer

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


---

