Motivation
By chance, I stumbled upon the blog post by errorgorn titled Solving Problems with Min Cut Max Flow Duality. When they mentioned using flow (for certain problems) in a similar way to 2SAT, something clicked for me. While I knew how to solve a variety of flow problems along with forming certain flow networks ad hoc, there was this entire subset of flow problems which I previously did not understand how to do.
The blog post does a great job of explaining many of the concepts/applications, but there were certain things that got black-boxed. In order to understand things, my brain works such that truly understanding what is going on under the hood (often through proofs) helps me better intuit how to use and abuse a tool. Naturally, I tried to search the internet for more information on this topic. Unfortunately, I quickly came to realize that not much material as in-depth as the aforementioned blog post exists (or at least, I failed to find it).
In writing this blog post, I hope to help provide the very resource that I failed to find. I hope this makes the topic more accessible to others and serves as a resource for explaining both why and how.
Note that, while I give a brief introduction into what maximum flow is, this blog post is best ingested after having learned the general concepts of flow.
Introduction/Preliminary
What is Maximum Flow?
To start, let $$$G$$$ be a directed graph with edge weights called capacities. This is sometimes referred to as a network or flow network.
For the purposes of finding "flow," we have a start and end vertex where we want to find the maximum amount of "flow" from the start to the end. These are typically called the source and sink, respectively, and denoted $$$s$$$ and $$$t$$$, respectively.
The name maximum flow serves well as a pictorial descriptor of what it means: consider releasing some amount of units of liquid from the source. Our goal is to find out the maximum amount of units which can flow to (reach) the sink without surpassing the capacities of any edges in the flow network. For example, if we find a (simple) path from $$$s$$$ to $$$t$$$ all of which have positive capacities, then the maximum flow possible strictly along this path is the minimum capacity out of all edges along this path.
What Is a Cut?
Suppose we have a connected, undirected graph $$$G$$$ (there exists a path between every pair of vertices). We will denote the set of vertices as $$$V(G)$$$ and the set of edges as $$$E(G)$$$. Then a set of edges, $$$K\subseteq E(G)$$$, is called an edge cut if removing all edges in $$$K$$$ from $$$G$$$, denoted as $$$G\setminus K$$$, disconnects the graph.
Suppose we have $$$X,Y \subseteq V(G)$$$. We denote the set of edges between them as $$$[X,Y]$$$. If $$$Y = \overline{X}$$$, then $$$[X,Y]$$$ is an edge cut. What this means is that removing these edges from $$$G$$$ ($$$G\setminus [X,Y]$$$) disconnects all vertices in $$$X$$$ from all vertices in $$$Y$$$, i.e. there does not exist $$$x \in X, y \in Y$$$ such that there exists a path from $$$x$$$ to $$$y$$$ in $$$G$$$ (sometimes called an $$$x,y$$$-path for the individual case and an $$$X,Y$$$-path overall).
Note that, up until now, we have been talking about undirected graphs. However, flow networks are directed. Let us slightly redefine things. Now, $$$G$$$ is a flow network. For $$$X,Y \subseteq V(G)$$$, we define $$$[X,Y]$$$ as the set of edges going from $$$X$$$ to $$$Y$$$ (i.e. forming $$$X,Y$$$-paths of length 1). We will denote the capacity of an edge, $$$e$$$, as $$$c(e)$$$ and the value of the edge cut (when $$$Y = \overline{X}$$$) as $$$v([X,Y]) = \displaystyle \sum_{e \in [X,Y]} c(e)$$$, i.e. the sum of capacities.
From here on out, the "edge" portion of "$$$\textit{edge}$$$ cut" will be omitted. Do note that this is technically ambiguous (and can lead to confusion if context is omitted) as vertex cuts also exist. I am choosing to omit it regardless in favor of common practice/use of terminology in this branch of graph theory.
What Is a Minimum Cut?
When we ask for the minimum cut in the context of a flow network, what we really mean is the minimum value for an $$$s,t$$$-cut. That is, out of all $$$S,T \subseteq V(G)$$$ such that $$$T = \overline{S}, s \in S, t \in T$$$, we want the pair with the smallest value for $$$v([S,T])$$$.
Relationship Between Minimum Cut and Maximum Flow
There is a theorem which states how, in a flow network, the minimum $$$s,t$$$-cut equals the maximum $$$s,t$$$-flow. I will avoid proving this here as it would make a long blog post even longer and it's not the main focus.
Cost-Benefit Flow
What Does This Mean?
Cost
Suppose we have a boolean variable, $$$b$$$, with a cost of $$$\begin{cases}T & \phantom{\lnot}b\\ F & \lnot b\end{cases}$$$ and we want to choose the value of $$$b$$$ such that the cost is minimized. Our goal is to represent this using flow.
If we have a flow network consisting solely of an $$$s,t$$$-path, then the maximum flow must be the smallest capacity along this path (otherwise, we would surpass the smallest capacity which is not possible). In turn, the minimum cut is also the smallest capacity along this path.
Accordingly, we can represent $$$b$$$ as the flow network $$$s \overset{F}{\longrightarrow} b \overset{T}{\longrightarrow} t$$$. Note that we could have equivalently represented this with the labels swapped. (It is fine to do so, but be sure you are consistent with this for when we build off this later). Also note that $$$\lnot b$$$ corresponds to the cut $$$[\{s\}, \{b,t\}]$$$ and $$$b$$$ corresponds to the cut $$$[\{s,b\}, \{t\}]$$$. (This is because having the left/false edge in the cut means $$$b$$$ is to the right of the cut and vice versa.)
We now have the foundation for cost, but what about benefit?
Benefit
Suppose we have a boolean variable, $$$b'$$$, with a benefit of $$$\begin{cases}T' & \phantom{\lnot}b'\\ F' & \lnot b'\end{cases}$$$, and we want to choose the value of $$$b'$$$ such that the benefit is maximized. Once again, we want to represent this with flow.
But hang on, we are now maximizing, so how can we use the minimum cut to get our answer?
We can do this by making the benefit values negative (since $$$x \leq y \iff -x \geq -y$$$, i.e. we can convert a maximization problem to a minimization problem). So now we can make a similar graph of the form $$$s \overset{-F'}{\longrightarrow} b' \overset{-T'}{\longrightarrow} t$$$, right?
Well, not quite. As you might have noticed, we now have negative edge capacities. This is not a valid flow network (at least, not without redefining aspects of a flow network). How do we fix this?
To figure this out, let us take a step back. Suppose we have the flow network $$$s \overset{F}{\longrightarrow} b \overset{T}{\longrightarrow} t$$$ from earlier again. I claim that we can add $$$k$$$ to both edge capacities so long as we subtract it from the resultant minimum cut found. That is, we now have the flow network $$$s \overset{F+k}{\longrightarrow} b \overset{T+k}{\longrightarrow} t$$$. Note that there are only two possible cuts since $$$b$$$ can either be together with $$$s$$$ or together with $$$t$$$. The cut $$$[\{s,b\}, \{t\}]$$$ has the value $$$T+k$$$ while the cut $$$[\{s\}, \{b,t\}]$$$ has the value $$$F+k$$$. In both cases, the cut's value has increased by $$$k$$$. Since the minimum cut must be one of these (in particular, the smallest one), $$$k$$$ always gets added to the minimum cut. Accordingly, adding $$$k$$$ to both edge capacities is equivalent to adding $$$k$$$ to the minimum cut, so we can also undo it by subtracting $$$k$$$ at the end.
This gets us most of the way to fixing our negative capacities issue; however, what was outlined above assumes we started with a valid flow network in the first place (before adding $$$k$$$). Do we actually need this assumption? No! Suppose we simply work backwards; that is, we start out with a flow network with a sufficiently large $$$k$$$ baked into the capacities. If we run flow on this, we then get the minimum cut, $$$c$$$, which has $$$k$$$ baked into it. We can then subtract $$$k$$$ from $$$c$$$ which will in turn subtract $$$k$$$ from each capacity giving us our desired ("original") capacities.
I will concede that this isn't the most rigorous of proofs, but it ultimately boils down to separating the result from the behavior. We could arguably construct an alternative proof by observing the linearity between the final answer and the supposed capacities even when they don't form a valid flow network.
Now, we can finally fix the negative flow. Let $$$m = \min(-F', -T')$$$. We now have the flow network of $$$s \overset{-F'-m}{\longrightarrow} b' \overset{-T'-m}{\longrightarrow} t$$$, where we add $$$m$$$ to the resultant minimum cut (since $$$m \leq 0$$$, $$$-m \geq 0$$$, so we have the same format as $$$+k$$$ above). Note that $$$-F',-T' \geq m$$$, so $$$-F'-m, -T'-m \geq 0$$$.
Cost-Benefit
If you look closely at what we just did, you might notice something really interesting. Since we are subtracting $$$m$$$ from both capacities and $$$m$$$ was equal to one of them, we always make one edge have capacity exactly 0 and the other have the absolute difference. But wait, we can do the same thing back when we were working with cost! Why can we do this? Well, what we found for adding $$$k$$$ also occurs for subtracting $$$k$$$ by using the exact same logic of it impacting all cuts equally. So we can also make cost have one side be 0 and the other side be the absolute difference (of course, which side it is on matters if we want to be consistent; as mentioned prior, sit tight for just a bit longer as to why we want to be consistent).
In other words, after offsetting the final answer, we only need to worry about a cost (equivalently, benefit) on one side. So how does this tie into combining both cost and benefit?
Well, first let us consider $$$b$$$ having both a cost, $$$x$$$, and a benefit, $$$y$$$, for the same state. Note that cost and benefit are opposites. In other words, the cost of this state is $$$x-y$$$ or cost $$$-$$$ benefit... wait, that's part of the title of this blog post! But the connections don't end here (after all, this is an observation which could have been made from the get-go). Notice how, earlier, we converted benefit on its own into a cost by... making it negative! Okay, I know, this is still not that special.
What actually ties this all together is when one state has a cost and the other has a benefit. For example, suppose we have $$$b$$$ with $$$\begin{cases}\text{cost}\phantom{\text{fitt }} T & \phantom{\lnot}b\\ \text{benefit } F & \lnot b\end{cases}$$$. Then we have the flow network of $$$s \overset{-F}{\longrightarrow} b \overset{T}{\longrightarrow} t$$$. Since $$$-F \leq T$$$, we can let $$$m = -F$$$, at which point we get $$$s \overset{-F-m}{\longrightarrow} b \overset{T-m}{\longrightarrow} t$$$ with $$$m$$$ added back to the minimum cut at the end, or equivalently $$$s \overset{0}{\longrightarrow} b \overset{T+F}{\longrightarrow} t$$$ with $$$-F$$$ added back to the minimum cut at the end... wait, $$$T+F$$$ is not cost $$$-$$$ benefit! Okay, I must confess, the title of this blog post is a happy accident in that it describes how cost and benefit are opposites relative to the same state. The real reason I named it cost-benefit is because of the relationship between cost and benefit, nothing more nothing less. However, I wasn't kidding when I said that having cost and benefit on opposing states ties it all together.
Notice how we ended up with $$$0$$$ and $$$T+F$$$. What we did was reframe the entire problem such that it is relative to one state; the true state is $$$T+F$$$ in distance away from the false state, as is the case in the other direction. For example, if both sides are cost (equivalently, benefit) with false being $$$x$$$ cost and true being $$$y$$$ cost, then they are each distance $$$|y-x|$$$ away from each other. We are able to pin one state and say that the other is exactly $$$z$$$ better/worse. The reason why I spent so much time on this is because of how instrumental the ability to shift around values in this manner is in fleshing out other aspects of what I call "cost-benefit flow."
Key Takeaways
- If we have a cost, $$$x$$$, corresponding to $$$b$$$, this is the same as shifting our frame of reference such that $$$b$$$ no longer has any cost (or benefit). To do so, we shift both $$$b$$$ and $$$\lnot b$$$ down by $$$x$$$ and the final answer up by $$$x$$$. In other words, we give $$$\lnot b$$$ a benefit of $$$x$$$ and add $$$x$$$ to the final answer.
- If we have a benefit, $$$y$$$, corresponding to $$$b$$$, this is the same as shifting our frame of reference such that $$$b$$$ no longer has any benefit (or cost). To do so, we shift both $$$b$$$ and $$$\lnot b$$$ up by $$$y$$$ and the final answer down by $$$y$$$. In other words, we give $$$\lnot b$$$ a cost of $$$y$$$ and subtract $$$y$$$ from the final answer.
It is important to note that when I talk about cost and benefit, this is referring to their values from their frame of reference; what this means is that a cost of $$$k$$$ is the same as a benefit of $$$-k$$$ (so if I say a benefit of $$$k$$$, I am really referring to how it is represented as $$$-k$$$ in the flow network, which must always get fixed/offset accordingly before running flow).
Adding More Variables
So far, all we have is a single boolean variable where we run flow to determine which state has a smaller value. If we stopped here, this would be comically useless.
Suppose we have $$$n$$$ boolean variables, $$$b_1, b_2, \dots, b_n$$$, each with their own cost/benefit per state. How can we represent all of these in one flow network? Let us start off simple by creating the path flow network which we have been working with individually for each one. Each one has its own copy of $$$s$$$ and $$$t$$$. If we merge all $$$s$$$ vertices into a single $$$s$$$ vertex and all $$$t$$$ vertices into a single $$$t$$$ vertex, then notice how each one can behave completely independently. After all, the only $$$s,t$$$-paths in this flow network are exactly the paths we started with.
One key thing we must consider is the behavior of fixing negative values within the flow network/making one state relative to the other. Since we haven't formed any new paths, for all other variable states fixed except $$$b_i$$$, there are two possible cuts, both of which would have the aforementioned $$$m_i$$$ subtracted from them. Just like before, this would require us to add $$$m_i$$$ back to the final minimum cut found. Accordingly, we can update all the paths within the flow network to have the form $$$s \overset{F'_i-m_i}{\longrightarrow} b_i \overset{T'_i-m_i}{\longrightarrow} t$$$ (where $$$F'_i, T'_i$$$ have a negative value if $$$F_i,T_i$$$ are benefit, respectively) and add $$$\displaystyle \sum_{i=1}^n m_i$$$ back to the final minimum cut found.
Representing More Advanced Logic
While we now have multiple variables in the same flow network, they are still completely decoupled. Let's change that!
Implications
Suppose we have two boolean variables, $$$a,b$$$. However, $$$a$$$ doesn't like to be true without $$$b$$$ also being true; violating this would have a cost of $$$k$$$. There are two ways to look at this:
- $$$a \land \lnot b$$$ has a cost of $$$k$$$
- $$$a \rightarrow b$$$ has a benefit of $$$k$$$
Why are these equivalent reframings of the problem? Well, note how $$$a \land \lnot b \iff \lnot(\lnot a \lor b) \iff \lnot(a \rightarrow b)$$$. Recall how cost and benefit are opposites! So if we can represent one, we can represent the other by shifting our frame of reference.
If you are confused as to why we can reframe benefit and cost between a boolean equation and its complement, look back at what we did with reframing $$$b$$$ and $$$\lnot b$$$. A careful inspection should make it clear that it was actually just a specific case of what we are doing here with $$$b$$$ as the equation. If you are still not convinced, I would recommend either trying to think of it in terms of meta variables, i.e. let $$$P$$$ represent when the equation is true and $$$\lnot P$$$ represent when it is false, or look at how cuts are impacted, similar to what we will do below.
Since it seems much easier to represent $$$a \land \lnot b$$$ (due to it only being true in one out of all four possible pairs of states), we will attempt to represent it in our graph. Our goal is to have the cut representing $$$a \land \lnot b$$$ increase in cost by $$$k$$$ with all other cuts left unaffected. Recall that being to the left of the cut means true and being to the right means false. Accordingly, we want the cut $$$[\{s,a\}, \{b,t\}]$$$ to have cost increased by $$$k$$$. Since only $$$a$$$ and $$$b$$$ move around when looking at different cuts, our new edge must involve them. Therefore, this cut alone gains a cost of $$$k$$$ if and only if we add the edge $$$a \overset{k}{\longrightarrow} b$$$.
In order to verify that no other cuts are impacted, note that the only way for this edge to be included in the cut is to have $$$a$$$ to the left of the cut and $$$b$$$ to the right. Well, there is only one way to do this; since we have fixed both $$$a$$$ and $$$b$$$, there are no other vertices free to move around. So this works!
However, we have not directly addressed what happens when there are more than two variables. Since our boolean equation does not depend on any other variables, all cuts with $$$a$$$ to the left and $$$b$$$ to the right will have $$$k$$$ added and every other cut will have nothing added, regardless of the state of other variables. So no issues arise in extending to more variables.
Since we now know that $$$a \land \lnot b$$$ with a cost of $$$k$$$ can be represented as $$$a \overset{k}{\longrightarrow} b$$$, we know how to represent the equation $$$a \rightarrow b$$$ with a benefit of $$$k$$$. That is, the equation $$$a \rightarrow b$$$ with benefit $$$k$$$ is the same as the edge $$$a \overset{k}{\longrightarrow} b$$$ with $$$k$$$ subtracted from the final answer.
Inclusion-Exclusion
There are certain equations which we are unable to represent (at least with the current way we are constructing our flow network). It would be great if we could represent an equation as simpler/different equations that are already representable (i.e. $$$b, \lnot b, a \land \lnot b$$$).
Consider the meta equation $$$P \lor Q$$$, where $$$P,Q$$$ are themselves boolean equations (i.e. they can depend on multiple variables) and we have some cost $$$k$$$. How can we represent $$$P \lor Q$$$ differently? Suppose we break it up separately into $$$P, Q$$$, each with their own cost $$$k$$$. When only one of them is true ($$$P \land \lnot Q$$$, $$$\lnot P \land Q$$$), this works great! After all, we only impact those particular cuts once. However, when both of them are true ($$$P \land Q$$$), we double count by impacting those cuts twice. How can we fix this? Well, since $$$P \land Q$$$ is the only (meta) state which double counts, we can cancel out one of the costs of $$$k$$$ by giving $$$P \land Q$$$ a benefit of $$$k$$$.
In summary, given the meta equation $$$P \lor Q$$$ with cost $$$k$$$, we can reframe it as giving $$$P$$$ a cost of $$$k$$$, giving $$$Q$$$ a cost of $$$k$$$, and giving $$$P \land Q$$$ a benefit of $$$k$$$. Similarly, given the meta equation $$$P \lor Q$$$ with benefit $$$k$$$, we can reframe it as giving $$$P$$$ a benefit of $$$k$$$, giving $$$Q$$$ a benefit of $$$k$$$, and giving $$$P \land Q$$$ a cost of $$$k$$$.
Implications Revisited
With inclusion-exclusion in mind, we are able to find an alternative way to represent $$$a \rightarrow b$$$ with benefit $$$k$$$. To start, note that $$$a \rightarrow b \iff \lnot a \lor b$$$. Now, by defining the meta variables $$$P = \lnot a, Q = b$$$, we get that we give $$$\lnot a$$$ a benefit of $$$k$$$, $$$b$$$ a benefit of $$$k$$$, and $$$\lnot a \land b$$$ a cost of $$$k$$$. Notice how this differs from our original derivation of implications; our offset of the final answer is different, and the direction of the edge between $$$a$$$ and $$$b$$$ is reversed (the original derivation uses $$$a \land \lnot b$$$, whereas this new one uses $$$b \land \lnot a$$$).
So we have that the equation $$$a \rightarrow b$$$ with benefit $$$k$$$ can equivalently be represented as $$$s \overset{k}{\longrightarrow} b \overset{k}{\longrightarrow} a \overset{k}{\longrightarrow} t$$$ and $$$2k$$$ subtracted from the final answer.
Equality and Inequality/XOR
Suppose we have two boolean variables, $$$a,b$$$. However, $$$a$$$ and $$$b$$$ like to be the same; having this be the case gives a benefit of $$$k$$$. Equivalently, having this not be the case (i.e. they are different) has a cost of $$$k$$$.
First, note that $$$a \neq b$$$ is equivalent to $$$a \oplus b$$$ in boolean logic (where $$$\oplus$$$ represents XOR). Additionally, the only two cases where $$$a \neq b$$$ are $$$a \land \lnot b$$$ and $$$\lnot a \land b$$$. So $$$a \neq b \iff a \oplus b \iff a \land \lnot b \lor \lnot a \land b$$$. Letting $$$P = a \land \lnot b, Q = \lnot a \land b$$$ and using inclusion exclusion, we must give $$$a \land \lnot b$$$ a cost of $$$k$$$, $$$\lnot a \land b$$$ a cost of $$$k$$$, and $$$a \land \lnot b \land \lnot a \land b \iff \bot$$$ a benefit of $$$k$$$. Since the last one is never true ($$$\bot$$$ means contradiction), there are no cuts which we need to impact with a benefit.
So we have that $$$a \neq b$$$ (equivalently, $$$a \oplus b$$$) with a cost of $$$k$$$ can be represented as $$$a \overset{k}{\longrightarrow} b$$$ and $$$b \overset{k}{\longrightarrow} a$$$. Accordingly, we can represent $$$a = b$$$ with a benefit of $$$k$$$ as $$$a \overset{k}{\longrightarrow} b$$$, $$$b \overset{k}{\longrightarrow} a$$$, and $$$k$$$ subtracted from the final answer.
What Remains
To simplify things, let us look at only what we have derived for benefit (since everything has an equivalent cost counterpart). We currently foundationally have $$$\lnot a \lor b$$$ and $$$a \lor \lnot b$$$. As you may have noticed, we have not derived anything for $$$a \lor b$$$ or $$$\lnot a \lor \lnot b$$$. Why is this the case? Well, if we also had both of these, then we could fully represent MAX-2SAT (related to MAX-SAT) which is NP-hard. In other words, we would be able to prove that P $$$=$$$ NP (that the class of all polynomial-time algorithms is the same as the class of all non-deterministic polynomial-time algorithms). If you don't understand what this means, that's okay; the gist of it is that either we solved a problem that has been left unsolved for half a century and a $1 million check will be showing up at our door tomorrow (unlikely), or we made a mistake.
In this case, the mistake was assuming that we had $$$a \lor b$$$ and $$$\lnot a \lor \lnot b$$$ in addition to what we have found so far (in terms of benefit). So it is flat-out not possible to represent all of these at the same time. However, notice how this would only become a problem if we were able to represent both for the same set of variables at the same time (even indirectly through a chain of other variables).
Flipping Variables
Remember how I pointed out that, on its own, the orientation of true and false for a lone variable doesn't matter, but we should fix the orientation so that we can build off it later? Well, here we are! (Technically, we also built off it earlier when extending to multiple variables since we assumed all variables have the same orientation.)
Normal And
Suppose we have two boolean variables, $$$a,b$$$, and we want to give a cost of $$$k$$$ when both are true. Is there some modification we can make to the flow network which would allow for this? Of course, as discussed before, it would have to have restrictions, i.e. not being able to represent certain other logic.
Well, there is only one cut we want to impact, namely $$$[\{s,a,b\}, \{t\}]$$$. Any edge we add here would involve $$$t$$$, but it isn't immediately clear how to make an edge (or edges) in such a way that $$$a,b$$$ are coupled. Instead, let's look at a different cut, namely the one that, up until now, represented $$$a \land \lnot b$$$: $$$[\{s,a\}, \{b,t\}]$$$. This one has the ideal structure for what we desire, but it currently represents something else!
What if we flip the meaning of $$$b$$$? That is, its left edge is the cost for true and the right edge is the cost for false (i.e. being to the left of the cut means false and to the right means true). Then the aforementioned cut would mean $$$a \land b$$$! Similarly, the cut $$$[\{s,b\}, \{a,t\}]$$$ would now mean $$$\lnot a \land \lnot b$$$. Note how it doesn't matter which variable we flip so long as we are consistent with direction of edges between them (and make sure only one is flipped).
It follows that we can represent a cost of $$$k$$$ for $$$a \land b$$$ with $$$a \overset{k}{\longrightarrow} b$$$ and a cost of $$$k$$$ for $$$\lnot a \land \lnot b$$$ with $$$b \overset{k}{\longrightarrow} a$$$. Don't forget that which variable got flipped matters! Which edge corresponds to which equation would swap if we chose to flip $$$a$$$ instead.
While it's great that we can now represent such an equation, as we mentioned before, we must have some restrictions. So what is the catch? Well, we can no longer represent $$$a \land \lnot b$$$ or $$$\lnot a \land b$$$. This is quite the restriction, but notice how this only impacts all equations involving the flipped variable. We will solidify this more a bit later.
Normal Or
Suppose we have two boolean variables, $$$a,b$$$, with a benefit of $$$k$$$ when either is true. As per usual, we have two ways we can tackle this.
Using negation, notice how $$$a \lor b \iff \lnot(\lnot a \land \lnot b)$$$, so we can do the usual of instead doing a cost of $$$k$$$ for $$$\lnot a \land \lnot b$$$ and subtracting $$$k$$$ from the final answer. (Note that the direction of the edge will be different depending on which of $$$a,b$$$ you choose to flip.)
Using inclusion-exclusion, we get benefit of $$$k$$$ for $$$a$$$, benefit of $$$k$$$ for $$$b$$$, and cost of $$$k$$$ for $$$a \land b$$$. (We would end up subtracting $$$2k$$$ from the answer when we convert both benefits to costs.)
Notice how we can also give a benefit of $$$k$$$ to $$$\lnot a \lor \lnot b$$$ in a similar manner since $$$\lnot a \lor \lnot b \iff \lnot(a \land b)$$$, and earlier we found that we are able to represent a cost of $$$k$$$ for $$$a \land b$$$ along with $$$\lnot a \land \lnot b$$$.
These are precisely the other two equations/clauses we were missing from earlier (in terms of benefit) pertaining to MAX-2SAT!
Equality and Inequality/XOR (Cost-Benefit Inverted)
Suppose we have two boolean variables, $$$a,b$$$, with a cost of $$$k$$$ when they are the same.
Notice how $$$a = b \iff a \land b \lor \lnot a \land \lnot b$$$ with $$$a \land b \land \lnot a \land \lnot b \iff \bot$$$. So from inclusion-exclusion, we can give cost of $$$k$$$ to $$$a \land b$$$ and cost of $$$k$$$ to $$$\lnot a \land \lnot b$$$.
From this, we get that giving a benefit of $$$k$$$ to $$$a \neq b \iff a \oplus b$$$ is the same as giving a cost to $$$a = b$$$ and subtracting $$$k$$$ from the final answer.
As you may have noticed, this is the same as back when we didn't have a variable flipped just with which side has cost and which side has benefit inverted. This helps exemplify what restrictions were in place in both cases (namely that having negative capacity for internal edges runs into problems) and what's stopping us from fully representing MAX-2SAT. If you are curious as to why we are able to represent similar versions of this in both frameworks (just with cost and benefit swapped), take a moment to consider what's special about $$$a = b$$$ and $$$a \neq b$$$.
Solidifying the Restrictions
Recall that flipping a variable only impacts the equations it is a part of. So when exactly can we represent a set of equations, $$$S$$$?
Assume we have reduced our equations (with associated cost/benefit), $$$S$$$, into the building blocks we have covered (with associated cost/benefit).
Let $$$X$$$ be the set of variables which remain unflipped and $$$Y$$$ be the set of variables which get flipped. If we can find $$$X,Y \subseteq V(G)$$$ with $$$Y = \overline X$$$ such that all equations of variables solely in $$$X$$$ or solely in $$$Y$$$ are representable with our unflipped logic abilities and every equation involving variables from both $$$X$$$ and $$$Y$$$ are representable with our flipped logic abilities (including being correct between cost and benefit), then it is possible to represent our set of equations.
Flipping Cost-Benefit
To wrap things up, I want to point out something that can be quite useful. Up until now, we have been working under the assumption that we want to minimize cost/maximize benefit. But what if we want to do the opposite? Well, this is surprisingly simple! We instead swap all instances of cost and benefit. In other words, instead of using cost $$$-$$$ benefit, we use benefit $$$-$$$ cost; a positive value now represents benefit, while a negative value now represents cost. Just be cognizant of avoiding negative internal edges (i.e. between variables); we must rework it by reframing the cost/benefit in terms of the negation or by using inclusion-exclusion (which isn't always possible).
Infinite Cost/Benefit
I decided to throw this in as a bonus since it can be quite useful for flow-related problems, even ones unrelated to cost-benefit flow (i.e. it can be applied to minimum cost flow). If we want to force a specific state to not happen, so long as we can represent the equation in a valid manner with cost associated directly to it, we can give it an effective cost of $$$\infty$$$. If the final answer is $$$\infty$$$, then there is no way to avoid all the states which we gave infinite cost to.
In practice, $$$\infty$$$ would be represented as a sufficiently large number, $$$M$$$, at which point checking if the final answer is $$$\infty$$$ really means checking if it is $$$\geq M$$$ before offsetting the answer by anything pertaining to benefit. This is because offsets from benefit could make the final answer go slightly below $$$M$$$ even if an edge with capacity $$$M$$$ was included. An example of a "sufficiently large number" for $$$M$$$ would be one greater than the sum of all positive, finite capacities (i.e. summing up all costs and adding 1).
We can do something similar with forcing a specific state to happen so long as we can represent the equation in a valid manner with benefit associated directly to it. If $$$M$$$ is what we consider as $$$\infty$$$ and we have $$$s$$$ states we always want to happen (each of which we accordingly assign a benefit of $$$M$$$), then it's possible only if the answer is strictly less than $$$-(s-1)\cdot M$$$.
In this case, we would want $$$M$$$ to be at least one greater than the maximum between the sum of costs and the sum of finite benefits. $$$-(s-1)\cdot M$$$ was found by noting that the $$$s$$$ states alone would make the final answer be $$$-s\cdot M$$$, and sum of all costs is $$$ \lt M$$$ (as with sum of all benefits), so we must get a final answer in the range $$$(-s\cdot M - M, -s\cdot M + M) = (-(s+1)\cdot M, (1-s)\cdot M) = (-(s+1)\cdot M, -(s-1)\cdot M)$$$. In other words, the final answer should be centered around $$$-s \cdot M$$$ with a margin/error of strictly less than $$$M$$$ (in either direction due to benefit vs cost).
Resources
A chunk of my knowledge and notation for general graph theory comes from the book Introduction to Graph Theory Second Edition by Douglas B. West. I would say that it does a good job of teaching many useful concepts of graph theory (though I will caution you that definitions in competitive programming for graphs are not always consistent with pure maths definitions, i.e. path in pure maths normally means simple path with walk meaning path; more info on paths, walks, and trails can be found here).
I wrote a little brute-forcer to sanity check/validate much of what I claimed throughout this article. It's nothing special and it's certainly not the best code out there, but I wanted to provide it to help lower the barrier to entry for those of you who want to play around with all of this yourself. For flow, I use kactl's implementation (it's just what I am used to since I typically participate in ICPC-style contests).
Just like how I started this blog post by mentioning Solving Problems with Min Cut Max Flow Duality by errorgorn, I wanted to end with mentioning it. Without it, I would not have gone down this interesting rabbit hole; it helped me directly learn a lot and led to me learning even more on my own.
Addendum
I know that this was by no means a short blog post. My goal in writing this was to allow someone who reads even a fraction of it to come away with having learned something new, whether that's the concept as a whole, a specific logic building block, or a new way to look at problems which utilize what I call Cost-Benefit Flow.
Thank you for taking a look and feel free to ask questions or give feedback in the comments. (I know, in the future I should probably be a bit less wordy; I'll make efforts towards that.)
