5
votes
Accepted
Maximum flow with parity requirement on certain edges
We can construct a widget for an all-or-nothing flow of capacity 4 from vertex s to t using the widget below. The stars (*) indicate even flows. By recursively applying similar widgets one can emulate ...
- 166
3
votes
Accepted
A stronger Flow Decomposition Theorem?
The statement of Ahuja, Magnanti, and Orlin applies to general flows, not only $(s,t)$-flows. During decomposition, when removing a path flow, either one of the two endpoints become balanced or one ...
2
votes
Computing the existence of a path in a code execution graph
As such, your problem seems to be NP-complete. To see the membership in NP, you can first guess a path, and then check that this path ends with $V_q$ and is valid. For the hardness part, we can ...
- 1,227
2
votes
Maximum flow with parity requirement on certain edges
Theorem 1. The problem is NP-hard.
Proof sketch. By reduction from maximum independent set in cubic graphs (which is NP-hard).
Given a cubic graph $G=(V, E)$, the reduction outputs a flow network as ...
- 9,595
1
vote
Entries of the Inverse Laplacian
I originally wanted to pose the question, but then I started investigating and found a few very helpful interpretation that haven't been collected anywhere (to my knowledge). Hence, I will write my ...
- 141
1
vote
Accepted
Finding a path in a graph hitting a particular vertex
here is a sketch of the idea:
If you don't have the constraint that the path is simple (i.e. no edge is used twice) then you just have to find a path from $u$ to $v$ and one from $v$ to $w$.
If you ...
- 775
Only top scored, non community-wiki answers of a minimum length are eligible