5 votes

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 ...
Albert Hendriks's user avatar
3 votes

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 ...
Kristoffer Arnsfelt Hansen's user avatar
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 ...
M.Monet's user avatar
  • 1,429
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 ...
Neal Young's user avatar
  • 10.8k
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 ...
Zuza's user avatar
  • 141
1 vote

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 ...
Louis's user avatar
  • 775

Only top scored, non community-wiki answers of a minimum length are eligible