# Tag Info

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 ...
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 ...

### 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 ...

### 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 ...
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 ...
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 ...

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