Question:
Given a graph $G$, How can we find the shortest path from vertex $x$ to $y$ with odd length?
Note: The time complexity is important to me. Can we somehow modify Breadth-first Search to do the trick?
[Math] Shortest path with odd length (linear time)
algorithmsgraph theory
Best Answer
A very elegant answer to the question can be found here.
Alternatively, you could always do it with a MIP: use binary variables $x_{ij}$ that take value $1$ if and only if edge $(i,j)$ is used, and minimize $$ \sum_{(i,j)\in E} x_{ij} $$ subject to $$ \begin{cases} \mbox{usual flow constraints} \\ \sum_{(i,j)\in E} x_{ij}=2k+1\\ k \in \mathbb{N}\\ x_{ij}\in \{0,1\} \end{cases} $$
Of course, the complexity is exponential so that is a major flaw to this method if theoretic time complexity is important. But it would be interesting to see how computation times evolve in practice, as the implementation is straightforward.