<p>Here's an expansion on the my comment.</p>
<p>Let <span class="math-container">$\textsf{MAXFLOW}=\{\left&lt;G,k\right&gt; \mid \text{ $G$ is a flow network with some flow $f$ where $|f|\ge k$\}}$</span>, and let <span class="math-container">$\textsf{2-UNSAT}=\{\left&lt;\varphi\right&gt; \mid \text{$\varphi$ is an unsatisfiable 2-CNF Boolean formula}\}.$</span></p>
<ol>
<li>Let <span class="math-container">$\textsf{PATH}=\{\left&lt;G,s,t\right&gt; \mid \text{ There is a path from $s$ to $t$ in $G$}\}$</span>. <span class="math-container">$\textsf{PATH}$</span> is a fairly well-known <span class="math-container">$\mathbf{NL}$</span>-complete problem (you can see Aurora and Barak for more info on that). Any reduction to <span class="math-container">$\textsf{PATH}$</span> can be made into a reduction to <span class="math-container">$\textsf{MAXFLOW}$</span>. Given <span class="math-container">$G,s,t$</span>, treat <span class="math-container">$G$</span> as a flow network with source <span class="math-container">$s$</span> and sink <span class="math-container">$t$</span> in which each edge has capacity <span class="math-container">$1$</span>. There is a path from <span class="math-container">$s$</span> to <span class="math-container">$t$</span> in <span class="math-container">$G$</span> iff there is a non-zero flow from <span class="math-container">$s$</span> to <span class="math-container">$t$</span> in <span class="math-container">$G$</span>. Given this, we can just describe a reduction from <span class="math-container">$\textsf{2-UNSAT}$</span> to <span class="math-container">$\textsf{PATH}$</span>, and then treat the resulting graph as a flow network as described here.</li>
<li>Given a 2-CNF Boolean formula <span class="math-container">$\varphi$</span> with <span class="math-container">$n$</span> variables <span class="math-container">$x_1,...,x_n$</span>, each clause <span class="math-container">$(x\vee y)$</span> can be written instead as the logically equivalent clause <span class="math-container">$(\neg x \to y)$</span> or equivalently <span class="math-container">$(\neg y \to x)$</span>. We define the implication graph <span class="math-container">$G_\varphi$</span> for <span class="math-container">$\varphi$</span> as the graph with nodes <span class="math-container">$2n$</span> nodes <span class="math-container">$\{x_1,...,x_n,\neg x_1,...,\neg x_n\}$</span>. <span class="math-container">$G_\varphi$</span> has an edge from literal <span class="math-container">$x$</span> to literal <span class="math-container">$y$</span> if <span class="math-container">$(x\to y)$</span> is equivalent to a clause in <span class="math-container">$\varphi$</span>. We'll take for granted that <span class="math-container">$\varphi$</span> is unsatisfiable iff there is an <span class="math-container">$i$</span> such that <span class="math-container">$x_i$</span> can reach <span class="math-container">$\neg x_i$</span> and <span class="math-container">$\neg x_i$</span> and reach <span class="math-container">$x_i$</span> in <span class="math-container">$G_\varphi$</span>. That is, there is a closed walk containing <span class="math-container">$x_i$</span> and <span class="math-container">$\neg x_i$</span>.</li>
</ol>
<p>With this in mind, given <span class="math-container">$\varphi$</span>, we want to construct a graph <span class="math-container">$H_\varphi$</span> with nodes <span class="math-container">$s$</span> and <span class="math-container">$t$</span>, such that <span class="math-container">$s$</span> can reach <span class="math-container">$t$</span> iff there is some <span class="math-container">$i$</span> such that <span class="math-container">$G_\varphi$</span> has a closed walk containing <span class="math-container">$x_i$</span> and <span class="math-container">$\neg x_i$</span>. Let's describe this by building it up from some basic gadgets!</p>
<p>Let <span class="math-container">$G$</span> be a graph containing a pair of nodes <span class="math-container">$x,y$</span>. We can make a corresponding graph <span class="math-container">$P_{G,x,y}$</span> with special nodes <span class="math-container">$s$</span> and <span class="math-container">$t$</span> such that there is a path from <span class="math-container">$s$</span> to <span class="math-container">$t$</span> in <span class="math-container">$P_{G,x,y}$</span> iff <span class="math-container">$G$</span> has a path from <span class="math-container">$x$</span> to <span class="math-container">$y$</span>. Let <span class="math-container">$P_{G,x,y}$</span> be the graph <span class="math-container">$G$</span> but with additional nodes <span class="math-container">$s$</span> and <span class="math-container">$t$</span>, where <span class="math-container">$s$</span> has an edge to <span class="math-container">$x$</span>, and <span class="math-container">$y$</span> has an edge to <span class="math-container">$t$</span>.</p>
<p>We can extend this gadget to to make a graph <span class="math-container">$C_{G,x,y}$</span> with dedicated nodes <span class="math-container">$s$</span> and <span class="math-container">$t$</span> such that <span class="math-container">$s$</span> has a path to <span class="math-container">$t$</span> iff <span class="math-container">$G$</span> has a closed walk containing <span class="math-container">$x$</span> and <span class="math-container">$y$</span>. Simply construct <span class="math-container">$P_{G,x,y}$</span> with start node <span class="math-container">$s$</span> and end node <span class="math-container">$v_{middle}$</span> and <span class="math-container">$P_{G,y,x}$</span> with start node <span class="math-container">$v_{middle}$</span> and end node <span class="math-container">$t$</span>.</p>
<p>Now, given <span class="math-container">$G_\varphi$</span>, we can create <span class="math-container">$n$</span> disjoint gadgets <span class="math-container">$C_{G_\varphi,x_1,\neg x_1},...,C_{G_\varphi,x_n,\neg x_n}$</span> with their own dedicated source nodes <span class="math-container">$s_1,...,s_n$</span> and sink nodes <span class="math-container">$t_1,...,t_n$</span>. Our goal in determining unsatisfiability is to determine that at least one of these gadgets has a path from its source vertex <span class="math-container">$s_i$</span> to its sink vertex <span class="math-container">$t_i$</span>. What's left to do is create our dedicated source node <span class="math-container">$s$</span> with an edge to each gadget's source node <span class="math-container">$s_i$</span>, and create a dedicated sink node <span class="math-container">$t$</span> with an edge from each gadgets dedicated sink node <span class="math-container">$t_i$</span>. There is a path from <span class="math-container">$s$</span> to <span class="math-container">$t$</span> iff there is an <span class="math-container">$i$</span> such that there is a path from <span class="math-container">$s_i$</span> to <span class="math-container">$t_i$</span>.</p>
<p>And that's the full reduction! I think each detail except for the lemma about closed walks in reachability graphs should be fairly easy to verify, and I think the proof of the closed walk lemma about the implication graph is not too bad!</p>
<p>As far as giving a natural reduction from <span class="math-container">$\textsf{2-SAT}$</span> to <span class="math-container">$\textsf{MAXFLOW}$</span> goes, I don't have a clear reduction in mind. One could always try analyzing the nondeterministic space <span class="math-container">$O(\log(n))$</span> algorithm for <span class="math-container">$\text{2-SAT}$</span> to get a similar reduction through <span class="math-container">$\textsf{PATH}$</span>, or try to look at a circuit computing <span class="math-container">$\textsf{2-SAT}$</span> and then go through a reduction from <span class="math-container">$\textsf{Circuit-Eval}$</span> to <span class="math-container">$\textsf{MAXFLOW}$</span>. I'm not sure that either of these would yield anything satisfying, but if you needed an explicit reduction, that's one way to try to find one.</p>

CC BY-SA 4.0
2024-10-16T20:02:25.750Z
Thank you for your answer! Even though your answer doesn't yield a satisfying assigment, it still answers the question since when $k = 0$ then clearly the maximum flow has a value $k$
 iff the formula is satisfiable. I will try to find another reductions that does.
Daniel García
CC BY-SA 4.0
2024-10-16T15:56:02.050Z
2024-10-16T15:56:02.050Z
Dylan McKay
<p>Theoretically, I believe that it is possible to reduce any problem in P to Maximum Flow since it's P-Complete. However, I've been unable to find a natural (many-one) transformation from a 2-SAT formula to a maximum flow circuit such that the maximum flow has a value <span class="math-container">$k$</span> iff the formula is satisfiable. Ideally, the process yields a satisfying assignment if one exists. How do you reduce 2-SAT formula to a Maximum Flow Circuit?</p>

CC BY-SA 4.0
2024-10-13T07:43:15.303Z
If I remember correctly, I think 2-CNF formulas $\varphi$ have a really nice property that, if you consider the graph $G$ of variables and their negations where $x$ has an edge to y if $x\to y$ is a clause (that is, $(\neg x \vee y)$ is a clause), then $\varphi$ is unsatisfiable iff there is an $x$ such that $x$ and $\neg x$ share a cycle in $G$. This gives a pretty natural reduction from 2-UNSAT to s-t reachability, which then has a pretty straightforward reduction to max flow. If this is the kind of thing you're looking for, happy to write a more detailed answer!
Dylan McKay
CC BY-SA 4.0
2024-10-14T23:33:21.600Z
@DylanMcKay I am interested in your line of reasoning. I believe you're not mistaken when you say that x
 and its negation cannot be reached from one another in the implication graph. I've tried this approach but I was unable to predetermine a value k for the flow while implying an assignment with it because some of the nodes in the same strongly connected component might not be traversed. Therefore, I would be interested in a more detailed answer, that would be very helpful. Thanks!
Daniel García
CC BY-SA 4.0
2024-10-16T14:36:04.513Z
Before I do write-up something terribly detailed, I want to point out that what I mentioned is technically a reduction from 2-UNSAT to MAXFLOW, rather than 2-SAT to MAXFLOW. The idea would be to make a graph $G$ with nodes $s$ and $t$ so that there is a path from $s$ to $t$ iff there is some literal $x$ which can reach $\neg x$ in the implication graph of $\phi$. And then with a capacity 1 on each edge, the question is just simply whether or not there is a flow $>0$ from $s$ to $t$. I'll write that up if it's helpful! I don't have a many-one reduction in mind from 2-SAT to MAXFLOW.
Dylan McKay
CC BY-SA 4.0
2024-10-16T14:47:31.610Z
@DylanMcKay I think that a reduction from 2-UNSAT would be helpful! Upon further inspection, it seems that many NP-Complete are related to the implication graphs of those formulas which makes it difficult to perform the reduction due to their intractability. Therefore, a reduction from 2-UNSAT would be welcome.
Daniel García
<cc.complexity-theory><reductions><max-flow-min-cut><2sat>
How Do You Reduce a 2-SAT Formula to a Maximum Flow Circuit?
Daniel García
# How Do You Reduce a 2-SAT Formula to a Maximum Flow Circuit?

(Asked by: username_0 on 2024-10-12)

Theoretically, I believe that it is possible to reduce any problem in P to Maximum Flow since it's P-Complete. However, I've been unable to find a natural (many-one) transformation from a 2-SAT formula to a maximum flow circuit such that the maximum flow has a value $k$ iff the formula is satisfiable. Ideally, the process yields a satisfying assignment if one exists. How do you reduce 2-SAT formula to a Maximum Flow Circuit?

**Tags:** cc.complexity-theory, reductions, max-flow-min-cut, 2sat

> **Comments:**
> **username_1**: If I remember correctly, I think 2-CNF formulas $\varphi$ have a really nice property that, if you consider the graph $G$ of variables and their negations where $x$ has an edge to y if $x\to y$ is a clause (that is, $(\neg x \vee y)$ is a clause), then $\varphi$ is unsatisfiable iff there is an $x$ such that $x$ and $\neg x$ share a cycle in $G$. This gives a pretty natural reduction from 2-UNSAT to s-t reachability, which then has a pretty straightforward reduction to max flow. If this is the kind of thing you're looking for, happy to write a more detailed answer!  
> **username_0**: @DylanMcKay I am interested in your line of reasoning. I believe you're not mistaken when you say that x  and its negation cannot be reached from one another in the implication graph. I've tried this approach but I was unable to predetermine a value k for the flow while implying an assignment with it because some of the nodes in the same strongly connected component might not be traversed. Therefore, I would be interested in a more detailed answer, that would be very helpful. Thanks!  
> **username_1**: Before I do write-up something terribly detailed, I want to point out that what I mentioned is technically a reduction from 2-UNSAT to MAXFLOW, rather than 2-SAT to MAXFLOW. The idea would be to make a graph $G$ with nodes $s$ and $t$ so that there is a path from $s$ to $t$ iff there is some literal $x$ which can reach $\neg x$ in the implication graph of $\phi$. And then with a capacity 1 on each edge, the question is just simply whether or not there is a flow $>0$ from $s$ to $t$. I'll write that up if it's helpful! I don't have a many-one reduction in mind from 2-SAT to MAXFLOW.  
> **username_0**: @DylanMcKay I think that a reduction from 2-UNSAT would be helpful! Upon further inspection, it seems that many NP-Complete are related to the implication graphs of those formulas which makes it difficult to perform the reduction due to their intractability. Therefore, a reduction from 2-UNSAT would be welcome.  

---

## 1 answers

### Answer by username_1 on 2024-10-16. Score: 1 | Accepted answer

Here's an expansion on the my comment.

Let $\textsf{MAXFLOW}=\{\left \mid \text{ $G$ is a flow network with some flow $f$ where $|f|\ge k$\}}$, and let $\textsf{2-UNSAT}=\{\left<\varphi\right> \mid \text{$\varphi$ is an unsatisfiable 2-CNF Boolean formula}\}.$

1. Let $\textsf{PATH}=\{\left \mid \text{ There is a path from $s$ to $t$ in $G$}\}$. $\textsf{PATH}$ is a fairly well-known $\mathbf{NL}$-complete problem (you can see Aurora and Barak for more info on that). Any reduction to $\textsf{PATH}$ can be made into a reduction to $\textsf{MAXFLOW}$. Given $G,s,t$, treat $G$ as a flow network with source $s$ and sink $t$ in which each edge has capacity $1$. There is a path from $s$ to $t$ in $G$ iff there is a non-zero flow from $s$ to $t$ in $G$. Given this, we can just describe a reduction from $\textsf{2-UNSAT}$ to $\textsf{PATH}$, and then treat the resulting graph as a flow network as described here.
2. Given a 2-CNF Boolean formula $\varphi$ with $n$ variables $x\_1,...,x\_n$, each clause $(x\vee y)$ can be written instead as the logically equivalent clause $(\neg x \to y)$ or equivalently $(\neg y \to x)$. We define the implication graph $G\_\varphi$ for $\varphi$ as the graph with nodes $2n$ nodes $\{x\_1,...,x\_n,\neg x\_1,...,\neg x\_n\}$. $G\_\varphi$ has an edge from literal $x$ to literal $y$ if $(x\to y)$ is equivalent to a clause in $\varphi$. We'll take for granted that $\varphi$ is unsatisfiable iff there is an $i$ such that $x\_i$ can reach $\neg x\_i$ and $\neg x\_i$ and reach $x\_i$ in $G\_\varphi$. That is, there is a closed walk containing $x\_i$ and $\neg x\_i$.

With this in mind, given $\varphi$, we want to construct a graph $H\_\varphi$ with nodes $s$ and $t$, such that $s$ can reach $t$ iff there is some $i$ such that $G\_\varphi$ has a closed walk containing $x\_i$ and $\neg x\_i$. Let's describe this by building it up from some basic gadgets!

Let $G$ be a graph containing a pair of nodes $x,y$. We can make a corresponding graph $P\_{G,x,y}$ with special nodes $s$ and $t$ such that there is a path from $s$ to $t$ in $P\_{G,x,y}$ iff $G$ has a path from $x$ to $y$. Let $P\_{G,x,y}$ be the graph $G$ but with additional nodes $s$ and $t$, where $s$ has an edge to $x$, and $y$ has an edge to $t$.

We can extend this gadget to to make a graph $C\_{G,x,y}$ with dedicated nodes $s$ and $t$ such that $s$ has a path to $t$ iff $G$ has a closed walk containing $x$ and $y$. Simply construct $P\_{G,x,y}$ with start node $s$ and end node $v\_{middle}$ and $P\_{G,y,x}$ with start node $v\_{middle}$ and end node $t$.

Now, given $G\_\varphi$, we can create $n$ disjoint gadgets $C\_{G\_\varphi,x\_1,\neg x\_1},...,C\_{G\_\varphi,x\_n,\neg x\_n}$ with their own dedicated source nodes $s\_1,...,s\_n$ and sink nodes $t\_1,...,t\_n$. Our goal in determining unsatisfiability is to determine that at least one of these gadgets has a path from its source vertex $s\_i$ to its sink vertex $t\_i$. What's left to do is create our dedicated source node $s$ with an edge to each gadget's source node $s\_i$, and create a dedicated sink node $t$ with an edge from each gadgets dedicated sink node $t\_i$. There is a path from $s$ to $t$ iff there is an $i$ such that there is a path from $s\_i$ to $t\_i$.

And that's the full reduction! I think each detail except for the lemma about closed walks in reachability graphs should be fairly easy to verify, and I think the proof of the closed walk lemma about the implication graph is not too bad!

As far as giving a natural reduction from $\textsf{2-SAT}$ to $\textsf{MAXFLOW}$ goes, I don't have a clear reduction in mind. One could always try analyzing the nondeterministic space $O(\log(n))$ algorithm for $\text{2-SAT}$ to get a similar reduction through $\textsf{PATH}$, or try to look at a circuit computing $\textsf{2-SAT}$ and then go through a reduction from $\textsf{Circuit-Eval}$ to $\textsf{MAXFLOW}$. I'm not sure that either of these would yield anything satisfying, but if you needed an explicit reduction, that's one way to try to find one.

> **Comments:**
> **username_0**: Thank you for your answer! Even though your answer doesn't yield a satisfying assigment, it still answers the question since when $k = 0$ then clearly the maximum flow has a value $k$  iff the formula is satisfiable. I will try to find another reductions that does.  

---

