3

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.

tobwin
  • 31
  • 3
  • 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 Nov 10 '22 at 22:16
  • 1
    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 Nov 10 '22 at 22:48
  • 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 Nov 11 '22 at 01:55
  • 1
    @ChandraChekuri, edge weights can be negative, so that might not be the optimal solution. – D.W. Nov 11 '22 at 02:21
  • @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 Nov 11 '22 at 06:27
  • 1
    @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 Nov 11 '22 at 07:41
  • 1
    Yes my bad, I did not even parse the $\lor$ and was too focused on having both vertices in $V'$. – holf Nov 11 '22 at 07:57

2 Answers2

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).

David Eppstein
  • 50,990
  • 3
  • 170
  • 278
0

This "Related" question 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.

tobwin
  • 31
  • 3