<p>In &quot;Optimization procedures for the bipartite unconstrained 0-1 quadratic programming problem&quot; [Comput. Oper. Res. 51, 2014, pp. 123–129] the authors Abraham Duarte, Manuel Laguna, Rafael Martí, and Jesús Sánchez-Oro write:</p>
<p>&quot;The bipartite unconstrained 0-1 quadratic programming problem (BQP) is a difficult combinatorial problem defined on a complete graph that consists of selecting a subgraph that maximizes the sum of the weights associated with the chosen vertices and the edges that connect them. The problem has appeared under several different names in the literature, including maximum weight induced subgraph, maximum weight biclique, matrix factorization and maximum cut on bipartite graphs.&quot;</p>
<p>You didn't say your graph was complete but that doesn't make any significant difference (you might as well add all the missing edges with weight zero).</p>

CC BY-SA 4.0
2022-11-23T03:12:28.883Z
2022-11-23T03:12:28.883Z
David Eppstein
<p>This <a href="https://cstheory.stackexchange.com/questions/6297/maximizing-sum-edge-weights?rq=1">&quot;Related&quot; question</a> covers a special case that seems to be NP-hard. I'm still interested in a name for the problem, but my main question is answered.</p>

CC BY-SA 4.0
2022-11-11T19:55:15.783Z
It is not so common to see these kind of problems with negative weights and hence may not have a name in the literature.
Chandra Chekuri
CC BY-SA 4.0
2022-11-10T21:46:52.140Z
2022-11-10T21:46:52.140Z
tobwin
<p>My problem is quite simple to state, so it surely must have a name:</p>
<p>Given a graph <span class="math-container">$G=(V,E)$</span> with edge weights <span class="math-container">$w(e) \in \mathbb{Z}$</span>, find a <span class="math-container">$V'  \subseteq V$</span> that maximizes <span class="math-container">$\sum_{e \in E' } w(e)$</span>, where <span class="math-container">$ E' = \{ (u,v) | u \in V' \vee v\in V'\} $</span> is the edge set covered by <span class="math-container">$V'$</span>.</p>
<p>All I can find is variants involving vertex weights, which allows for easier (as far as I can see) reductions from classic problems to prove NP-hardness.</p>

CC BY-SA 4.0
2022-11-10T22:16:30.993Z
Related https://cs.stackexchange.com/questions/84555/the-heaviest-induced-subgraph-problem ; you are looking at an induced subgraph with maximal weight. I tried quick googling around this but only found variants with positive weights. That may still be an entry point for you.
holf
CC BY-SA 4.0
2022-11-10T22:48:25.033Z
Thanks, though I think an induced subgraph requires both ends to be included in the vertex subset. Googling didn't help me either, but stackoverflow suggested a related question immediately, which covers a simple reduction from Independent Set. So I was able to answer my own question.
tobwin
CC BY-SA 4.0
2022-11-11T01:55:45.250Z
I may be misunderstanding the problem. Without any constraints on $V'$, why would you not let $V' = V$ and cover all edges in the graph?
Chandra Chekuri
CC BY-SA 4.0
2022-11-11T02:21:46.647Z
@ChandraChekuri, edge weights can be negative, so that might not be the optimal solution.
D.W.
CC BY-SA 4.0
2022-11-11T06:27:24.607Z
@tobwin In the definition you give in your post, both end points of the edge are in $V'$ so $(V',E')$ is indeed the subgraph induced by $V'$. Am I missing something?
holf
CC BY-SA 4.0
2022-11-11T07:41:40.720Z
@holf the problem I have in mind requires just one vertex to be selected. Isn't that what I'm saying with $u \in V' \vee v \in V'$?
tobwin
CC BY-SA 4.0
2022-11-11T07:57:58.030Z
Yes my bad, I did not even parse the $\lor$ and was too focused on having both vertices in $V'$.
holf
<graph-theory><optimization>
What is this graph problem, and how hard is it?
tobwin
# What is this graph problem, and how hard is it?

(Asked by: username_0 on 2022-11-10)

My problem is quite simple to state, so it surely must have a name:

Given a graph $G=(V,E)$ with edge weights $w(e) \in \mathbb{Z}$, find a $V' \subseteq V$ that maximizes $\sum\_{e \in E' } w(e)$, where $ E' = \{ (u,v) | u \in V' \vee v\in V'\} $ is the edge set covered by $V'$.

All I can find is variants involving vertex weights, which allows for easier (as far as I can see) reductions from classic problems to prove NP-hardness.

**Tags:** graph-theory, optimization
> **Comments:**
> **username_1**: Related https://cs.stackexchange.com/questions/84555/the-heaviest-induced-subgraph-problem ; you are looking at an induced subgraph with maximal weight. I tried quick googling around this but only found variants with positive weights. That may still be an entry point for you.  
> **username_0**: Thanks, though I think an induced subgraph requires both ends to be included in the vertex subset. Googling didn't help me either, but stackoverflow suggested a related question immediately, which covers a simple reduction from Independent Set. So I was able to answer my own question.  
> **username_2**: I may be misunderstanding the problem. Without any constraints on $V'$, why would you not let $V' = V$ and cover all edges in the graph?  
> **username_3**: @ChandraChekuri, edge weights can be negative, so that might not be the optimal solution.  
> **username_1**: @tobwin In the definition you give in your post, both end points of the edge are in $V'$ so $(V',E')$ is indeed the subgraph induced by $V'$. Am I missing something?  
> **username_0**: @holf the problem I have in mind requires just one vertex to be selected. Isn't that what I'm saying with $u \in V' \vee v \in V'$?  
> **username_1**: Yes my bad, I did not even parse the $\lor$ and was too focused on having both vertices in $V'$.  

---

## 2 answers

### Answer by username_4 on 2022-11-23. Score: 7

In "Optimization procedures for the bipartite unconstrained 0-1 quadratic programming problem" [Comput. Oper. Res. 51, 2014, pp. 123–129] the authors Abraham Duarte, Manuel Laguna, Rafael Martí, and Jesús Sánchez-Oro write:

"The bipartite unconstrained 0-1 quadratic programming problem (BQP) is a difficult combinatorial problem defined on a complete graph that consists of selecting a subgraph that maximizes the sum of the weights associated with the chosen vertices and the edges that connect them. The problem has appeared under several different names in the literature, including maximum weight induced subgraph, maximum weight biclique, matrix factorization and maximum cut on bipartite graphs."

You didn't say your graph was complete but that doesn't make any significant difference (you might as well add all the missing edges with weight zero).


---

### Answer by username_0 on 2022-11-10. Score: 0

This ["Related" question](https://cstheory.stackexchange.com/questions/6297/maximizing-sum-edge-weights?rq=1) covers a special case that seems to be NP-hard. I'm still interested in a name for the problem, but my main question is answered.

> **Comments:**
> **username_2**: It is not so common to see these kind of problems with negative weights and hence may not have a name in the literature.  

---

