0
$\begingroup$

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!

$\endgroup$

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.