I'm considering the following problem: Given a directed graph $G = (V,A)$ with unit capacities, determine if there exists a flow from $x$ to $y$ ($x = y$ is allowed) with a specific length $k$, i.e., if $f(a)$ denotes the flow on arc $a \in A$, we want to find a flow from $x$ to $y$ such that $\sum_{a \in A} f(a) = k$.

Do you know if this problem is of interest in research and if yes, what it is called?

(Note that this problem is equivalent to finding a trail (i.e. a closed walk without repeating edges) from $x$ to $y$ of length $k$).

Thanks in advance!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.