<p>It turns out that this problem is just the <a href="https://en.wikipedia.org/wiki/Project_selection_problem" rel="nofollow noreferrer">project selection problem</a> in disguise. In the project selection problem, you have a set of projects (left-hand-side vertices) yielding a revenue (their image by <span class="math-container">$f$</span>), you have a set of machines (right-hand-side vertices) having a cost (their image by <span class="math-container">$g$</span>), and whenever you select a project then you must purchase a specific subset of machines (its neighborhood in <span class="math-container">$G$</span>). An optimal solution to the project selection problem maximizes the total revenue of selected project minus the total cost of the machines that must be purchased, which is precisely the definition of <strong>weighted deficiency</strong> above.</p>
<p>Then, the project selection problem can be solved in PTIME by reducing to a <a href="https://en.wikipedia.org/wiki/Maximum_flow_problem" rel="nofollow noreferrer">maximum flow problem</a>.</p>
<p>Note that this result generalizes, beyond bipartite graphs, to arbitrary directed graphs. In the general problem, you have a directed graph <span class="math-container">$G = (V, E)$</span> and a cost function <span class="math-container">$f\colon V \to \mathbb{Z}$</span> giving an integer cost to every vertex, and you want to select a subset of vertices <span class="math-container">$V' \subseteq V$</span> such that <span class="math-container">$f(V') := \sum_{v \in V'} f(v)$</span> is maximal and, whenever there is a directed path from <span class="math-container">$u \in V$</span> to <span class="math-container">$v \in V$</span>, then if <span class="math-container">$u \in V'$</span> then <span class="math-container">$v \in V'$</span>. This problem also reduces to a variant of project selection on an arbitrary directed graph which can also be reduced to a maximum flow problem: cf <a href="https://ocw.tudelft.nl/wp-content/uploads/Algoritmiek_Project_Selection.pdf" rel="nofollow noreferrer">these course notes</a>.</p>

CC BY-SA 4.0
2024-10-29T12:26:29.993Z
2024-10-29T12:26:29.993Z
Antoine Amarilli 'a3nm'
<p>This question is about whether the measure on bipartite graphs called <em>deficiency</em>, which is PTIME to compute, can be generalized to a weighted variant and is still PTIME to compute in this setting.</p>
<p>Given a bipartite graph <span class="math-container">$G = (U \cup V, E)$</span> with <span class="math-container">$E \subseteq U \times V$</span>, for any subset <span class="math-container">$U' \subseteq U$</span> of left-hand-side vertices, the <em><a href="https://en.wikipedia.org/wiki/Deficiency_(graph_theory)" rel="nofollow noreferrer">deficiency</a></em> of <span class="math-container">$U'$</span> is the number of left-hand-side vertices in <span class="math-container">$U'$</span> minus the number of right-hand-side vertices adjacent to <span class="math-container">$U'$</span>. Formally, the deficiency is <span class="math-container">$\mathrm{def}_G(U') := |U'| - |\mathrm{N}(U')|$</span>, where I write <span class="math-container">$\mathrm{N}(U')$</span> to mean the set of neighbors of vertices of <span class="math-container">$U'$</span>, i.e., <span class="math-container">$\mathrm{N}(U') := \bigcup_{u \in U'} \{v \in V \mid (u, v) \in E\}$</span>. The <em>deficiency</em> of <span class="math-container">$G$</span> (relative to <span class="math-container">$U$</span>) is then the minimum deficiency of a subset of <span class="math-container">$U$</span>, i.e., it is <span class="math-container">$\mathrm{def}(G) := \max_{U' \subseteq U} \mathrm{def}_G(U')$</span>.</p>
<p>It is known that the deficiency of a bipartite graph <span class="math-container">$G$</span> can be computed in PTIME, e.g., from the theorem cited on the <a href="https://en.wikipedia.org/wiki/Deficiency_(graph_theory)" rel="nofollow noreferrer">Wikipedia page</a> which relates deficiency to the size of a <a href="https://en.wikipedia.org/wiki/Maximum_cardinality_matching" rel="nofollow noreferrer">maximum matching</a>.</p>
<p>My question is: <strong>what happens in the weighted case?</strong> Suppose I have functions <span class="math-container">$f\colon U \to \mathbb{N}$</span> and <span class="math-container">$g\colon V \to \mathbb{N}$</span>, and I now define the <em>weighted deficiency</em> of a set of left-hand-side vertices <span class="math-container">$U'$</span> to be the <em>total weight</em> of the vertices in <span class="math-container">$U'$</span> minus the <em>total weight</em> of the neighboring right-hand-side vertices. In other words, for <span class="math-container">$U' \subseteq U$</span>, writing <span class="math-container">$f(U') := \sum_{u \in U'} f(u)$</span> and <span class="math-container">$g(V') := \sum_{v \in V'} g(v)$</span> for <span class="math-container">$V'\subseteq V$</span>, I define <span class="math-container">$\mathrm{wdef}_{G,f,g}(U') := f(U') - g(\mathrm{N}(U'))$</span>. And the weighted deficiency of the weighted graph is then <span class="math-container">$\mathrm{wdef}(G,f,g) := \max_{U' \subseteq U} \mathrm{wdef}_{G,f,g}(U')$</span>.</p>
<p><strong>Given a graph <span class="math-container">$G$</span> and weight functions <span class="math-container">$f$</span> and <span class="math-container">$g$</span>, can I compute the weighted deficiency in PTIME?</strong></p>
<p>(Note that, if the values of <span class="math-container">$f$</span> and <span class="math-container">$g$</span> are polynomial, then they can be encoded simply by duplicating the vertices. The interesting case is when the values of <span class="math-container">$f$</span> and <span class="math-container">$g$</span> are written in binary in the input.)</p>

<graph-theory><graph-algorithms>
Can you compute in PTIME a weighted version of deficiency on a bipartite graph?
Antoine Amarilli 'a3nm'
# Can you compute in PTIME a weighted version of deficiency on a bipartite graph?

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

This question is about whether the measure on bipartite graphs called *deficiency*, which is PTIME to compute, can be generalized to a weighted variant and is still PTIME to compute in this setting.

Given a bipartite graph $G = (U \cup V, E)$ with $E \subseteq U \times V$, for any subset $U' \subseteq U$ of left-hand-side vertices, the *[deficiency](https://en.wikipedia.org/wiki/Deficiency_(graph_theory))* of $U'$ is the number of left-hand-side vertices in $U'$ minus the number of right-hand-side vertices adjacent to $U'$. Formally, the deficiency is $\mathrm{def}\_G(U') := |U'| - |\mathrm{N}(U')|$, where I write $\mathrm{N}(U')$ to mean the set of neighbors of vertices of $U'$, i.e., $\mathrm{N}(U') := \bigcup\_{u \in U'} \{v \in V \mid (u, v) \in E\}$. The *deficiency* of $G$ (relative to $U$) is then the minimum deficiency of a subset of $U$, i.e., it is $\mathrm{def}(G) := \max\_{U' \subseteq U} \mathrm{def}\_G(U')$.

It is known that the deficiency of a bipartite graph $G$ can be computed in PTIME, e.g., from the theorem cited on the [Wikipedia page](https://en.wikipedia.org/wiki/Deficiency_(graph_theory)) which relates deficiency to the size of a [maximum matching](https://en.wikipedia.org/wiki/Maximum_cardinality_matching).

My question is: **what happens in the weighted case?** Suppose I have functions $f\colon U \to \mathbb{N}$ and $g\colon V \to \mathbb{N}$, and I now define the *weighted deficiency* of a set of left-hand-side vertices $U'$ to be the *total weight* of the vertices in $U'$ minus the *total weight* of the neighboring right-hand-side vertices. In other words, for $U' \subseteq U$, writing $f(U') := \sum\_{u \in U'} f(u)$ and $g(V') := \sum\_{v \in V'} g(v)$ for $V'\subseteq V$, I define $\mathrm{wdef}\_{G,f,g}(U') := f(U') - g(\mathrm{N}(U'))$. And the weighted deficiency of the weighted graph is then $\mathrm{wdef}(G,f,g) := \max\_{U' \subseteq U} \mathrm{wdef}\_{G,f,g}(U')$.

**Given a graph $G$ and weight functions $f$ and $g$, can I compute the weighted deficiency in PTIME?**

(Note that, if the values of $f$ and $g$ are polynomial, then they can be encoded simply by duplicating the vertices. The interesting case is when the values of $f$ and $g$ are written in binary in the input.)

**Tags:** graph-theory, graph-algorithms


---

## 1 answers

### Answer by username_0 on 2024-10-29. Score: 2

It turns out that this problem is just the [project selection problem](https://en.wikipedia.org/wiki/Project_selection_problem) in disguise. In the project selection problem, you have a set of projects (left-hand-side vertices) yielding a revenue (their image by $f$), you have a set of machines (right-hand-side vertices) having a cost (their image by $g$), and whenever you select a project then you must purchase a specific subset of machines (its neighborhood in $G$). An optimal solution to the project selection problem maximizes the total revenue of selected project minus the total cost of the machines that must be purchased, which is precisely the definition of **weighted deficiency** above.

Then, the project selection problem can be solved in PTIME by reducing to a [maximum flow problem](https://en.wikipedia.org/wiki/Maximum_flow_problem).

Note that this result generalizes, beyond bipartite graphs, to arbitrary directed graphs. In the general problem, you have a directed graph $G = (V, E)$ and a cost function $f\colon V \to \mathbb{Z}$ giving an integer cost to every vertex, and you want to select a subset of vertices $V' \subseteq V$ such that $f(V') := \sum\_{v \in V'} f(v)$ is maximal and, whenever there is a directed path from $u \in V$ to $v \in V$, then if $u \in V'$ then $v \in V'$. This problem also reduces to a variant of project selection on an arbitrary directed graph which can also be reduced to a maximum flow problem: cf [these course notes](https://ocw.tudelft.nl/wp-content/uploads/Algoritmiek_Project_Selection.pdf).


---

