3
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ Related cs.stackexchange.com/questions/84555/… ; 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. $\endgroup$
    – holf
    Commented Nov 10, 2022 at 22:16
  • 1
    $\begingroup$ 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. $\endgroup$
    – tobwin
    Commented Nov 10, 2022 at 22:48
  • 1
    $\begingroup$ @ChandraChekuri, edge weights can be negative, so that might not be the optimal solution. $\endgroup$
    – D.W.
    Commented Nov 11, 2022 at 2:21
  • 1
    $\begingroup$ @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'$? $\endgroup$
    – tobwin
    Commented Nov 11, 2022 at 7:41
  • 1
    $\begingroup$ Yes my bad, I did not even parse the $\lor$ and was too focused on having both vertices in $V'$. $\endgroup$
    – holf
    Commented Nov 11, 2022 at 7:57

2 Answers 2

7
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ It is not so common to see these kind of problems with negative weights and hence may not have a name in the literature. $\endgroup$ Commented Nov 11, 2022 at 19:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.