<p>I believe we can reduce this problem into standard weighted min-cut (and is thus in PTIME).</p>
<p>First, we notice that if <span class="math-container">$\rho(v) \geq |N^-(v)|$</span> for a vertex <span class="math-container">$v\in V$</span>, i.e., it has a penalty higher than its in-degree, then it is always worth adding all incoming edges of <span class="math-container">$v$</span> into <span class="math-container">$C$</span>. We thus assume that <span class="math-container">$\rho(v) &lt; |N^-(v)|$</span> for all <span class="math-container">$v$</span>. (This step might not be necessary.)</p>
<p>Now we split every vertex--i.e., replace every vertex <span class="math-container">$v\in V$</span> by two vertices <span class="math-container">$v^a$</span> and <span class="math-container">$v^b$</span> and replace every edge <span class="math-container">$(u,v)\in E$</span> by <span class="math-container">$(u^b,v^a)$</span>; and for each <span class="math-container">$v\in V$</span> add <span class="math-container">$(v^a,v^b)$</span> into our new <span class="math-container">$E$</span>.</p>
<p>Let us define the weight of <span class="math-container">$(v^a,v^b)$</span> as <span class="math-container">$(|N^-(v)| - \rho(v))$</span> for <span class="math-container">$v\in V$</span> and the weight of the rest of the edges as 1 (except <span class="math-container">$(v^s,v^s)$</span> and <span class="math-container">$(v^t,v^t)$</span> which are set to <span class="math-container">$\infty$</span>).</p>
<p>Thus, if there is a solution <span class="math-container">$C'$</span> of the weighted min-cut instance with cost <span class="math-container">$\kappa$</span>, then there is a solution <span class="math-container">$C$</span> for the original instance with cost <span class="math-container">$\kappa + \sum_{v\in V}\rho(v)$</span> and vice versa.</p>

CC BY-SA 4.0
2024-12-18T18:10:35.900Z
Hi, thanks for the answer but I don't understand the construction. Say you have 3 parallel paths of length 2 from $s$ to a vertex $v$, and one edge from $v$ to $t$, with $v$ having penalty value $\rho(v) = 3$ (equal to $|N^-(v)|$) and all other vertices having penalty 0. Then the optimal solution is to remove the 3 incoming edges of $v$, having cost 3 plus penalty 0. But in the weighted min-cut instance $C'$ that you build, the optimal solution has cost $\kappa = 1$, cutting the edge going out of $v^b$. I don't understand how this relates to the optimal solution of the original instance.
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2024-12-20T03:30:16.993Z
The node $v$ in your graph is represented in the new instance by an edge $(v^a,v^b)$ with weight $|N^-(v)| - \rho(v) = 0$. The optimal solution to this instance is to remove only this edge, and we obtain a total cost of $\kappa = 0$ (not 1, plus this $\kappa$ is equal to the optimal value of the original instance, minus $\sum_v \rho(v)$). I edited the answer slightly since some details might have been lost in the wording.
alsips-cl
CC BY-SA 4.0
2024-12-16T03:02:10.430Z
2024-12-19T21:01:24.817Z
2024-12-19T21:01:24.817Z
alsips-cl
<p>I am interested in the following variant of the <a href="https://en.wikipedia.org/wiki/Minimum_cut" rel="noreferrer">min-cut</a> problem. We are given a directed graph <span class="math-container">$G=(V,E)$</span> with <span class="math-container">$E\subseteq V\times V$</span>, a <em>penalty function</em> <span class="math-container">$\rho:V\to \mathbb{N}$</span>, and a source <span class="math-container">$s\in V$</span> and target <span class="math-container">$t\in V$</span>. A <em>cut</em> is a subset <span class="math-container">$C \subseteq E$</span> such that there is no directed path from <span class="math-container">$s$</span> to <span class="math-container">$t$</span> in <span class="math-container">$G\setminus C$</span> (the graph obtained from <span class="math-container">$G$</span> simply by removing the edges of <span class="math-container">$C$</span>). I define the <em>cost</em> of a cut <span class="math-container">$C$</span>, written <span class="math-container">$c(C)$</span>, to be
the number of edges in <span class="math-container">$C$</span> <em>plus</em> the penalty <span class="math-container">$\rho(v)$</span> of all nodes <span class="math-container">$v$</span> for which some incoming edge is not in <span class="math-container">$C$</span>. Formally, <span class="math-container">$c(C) = |C| + \sum_{\substack{v\in V \text{ s.t.}\\\exists v' \in V \text{ with } (v',v)\notin C}} \rho(v)$</span>. In other words, this is the usual cost of a cut, but you also pay a penalty when you do not cut all incoming edges of a node.</p>
<p><strong>Question:</strong> Has this variant already been studied? Is it PTIME?</p>

CC BY-SA 4.0
2024-12-14T19:02:32.593Z
If you are interested in the problem, let me point out that it is related to our recent preprint: https://arxiv.org/abs/2412.09411. In the vocabulary of the paper, the problem presented here subsumes the computation of the reliability of some queries left open by the paper, such as abcd|be.
Antoine Amarilli 'a3nm'
<reference-request><max-flow-min-cut>
Is this variant of min-cut PTIME?
M.Monet
# Is this variant of min-cut PTIME?

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

I am interested in the following variant of the [min-cut](https://en.wikipedia.org/wiki/Minimum_cut) problem. We are given a directed graph $G=(V,E)$ with $E\subseteq V\times V$, a *penalty function* $\rho:V\to \mathbb{N}$, and a source $s\in V$ and target $t\in V$. A *cut* is a subset $C \subseteq E$ such that there is no directed path from $s$ to $t$ in $G\setminus C$ (the graph obtained from $G$ simply by removing the edges of $C$). I define the *cost* of a cut $C$, written $c(C)$, to be
the number of edges in $C$ *plus* the penalty $\rho(v)$ of all nodes $v$ for which some incoming edge is not in $C$. Formally, $c(C) = |C| + \sum\_{\substack{v\in V \text{ s.t.}\\\exists v' \in V \text{ with } (v',v)\notin C}} \rho(v)$. In other words, this is the usual cost of a cut, but you also pay a penalty when you do not cut all incoming edges of a node.

**Question:** Has this variant already been studied? Is it PTIME?

**Tags:** reference-request, max-flow-min-cut

> **Comments:**
> **username_1**: If you are interested in the problem, let me point out that it is related to our recent preprint: https://arxiv.org/abs/2412.09411. In the vocabulary of the paper, the problem presented here subsumes the computation of the reliability of some queries left open by the paper, such as abcd|be.  

---

## 1 answers

### Answer by username_2 on 2024-12-16. Score: 0

I believe we can reduce this problem into standard weighted min-cut (and is thus in PTIME).

First, we notice that if $\rho(v) \geq |N^-(v)|$ for a vertex $v\in V$, i.e., it has a penalty higher than its in-degree, then it is always worth adding all incoming edges of $v$ into $C$. We thus assume that $\rho(v) < |N^-(v)|$ for all $v$. (This step might not be necessary.)

Now we split every vertex--i.e., replace every vertex $v\in V$ by two vertices $v^a$ and $v^b$ and replace every edge $(u,v)\in E$ by $(u^b,v^a)$; and for each $v\in V$ add $(v^a,v^b)$ into our new $E$.

Let us define the weight of $(v^a,v^b)$ as $(|N^-(v)| - \rho(v))$ for $v\in V$ and the weight of the rest of the edges as 1 (except $(v^s,v^s)$ and $(v^t,v^t)$ which are set to $\infty$).

Thus, if there is a solution $C'$ of the weighted min-cut instance with cost $\kappa$, then there is a solution $C$ for the original instance with cost $\kappa + \sum\_{v\in V}\rho(v)$ and vice versa.

> **Comments:**
> **username_1**: Hi, thanks for the answer but I don't understand the construction. Say you have 3 parallel paths of length 2 from $s$ to a vertex $v$, and one edge from $v$ to $t$, with $v$ having penalty value $\rho(v) = 3$ (equal to $|N^-(v)|$) and all other vertices having penalty 0. Then the optimal solution is to remove the 3 incoming edges of $v$, having cost 3 plus penalty 0. But in the weighted min-cut instance $C'$ that you build, the optimal solution has cost $\kappa = 1$, cutting the edge going out of $v^b$. I don't understand how this relates to the optimal solution of the original instance.  
> **username_2**: The node $v$ in your graph is represented in the new instance by an edge $(v^a,v^b)$ with weight $|N^-(v)| - \rho(v) = 0$. The optimal solution to this instance is to remove only this edge, and we obtain a total cost of $\kappa = 0$ (not 1, plus this $\kappa$ is equal to the optimal value of the original instance, minus $\sum_v \rho(v)$). I edited the answer slightly since some details might have been lost in the wording.  

---

