2
$\begingroup$

Apologies if this question exists somewhere. I'm sure it's been asked, but I don't know how to search for it. This is not a homework question but rather a scientific problem I ran into. If this is a standard CS exercise, just mark it as duplicate and point me where I need to go.

Problem statement: Consider an undirected graph with positive integral values on the nodes and negative integral values on the edges. Find the subset of nodes such that the sum of node and edge values is minimized. An edge is only counted if both of its nodes are part of the subset.

In this image, I have two example graphs and their solutions. Red circles indicate that this node is part of the selected subset. Two examples showing graphs.

Notes:

  • Node values may be >= 0
  • In my specific case, the graph is bipartite: nodes are separated into two sets and edges only exist between the sets (I don't think fact is necessary though to create an algorithm)
  • The resulting subset does not need to be connected. See the right example.
  • It's fine if net-zero nodes are included, also fine if they aren't.

Simple greedy algorithms fail here because if you look at the bottom of the right example. All 3 nodes are required for that subset to become negative. Any two results in a zero/positive score.

$\endgroup$
3
  • 1
    $\begingroup$ Unfortunately the problem is NP-hard on general graphs. Consider a complete graph with weight $-c-1$ on all edges and weight $ck-c$ on all nodes, where $c$ is a constant larger than the number of nodes. Then there is a clique of size $k$ iff there is a solution to your problem whose sum is less than zero. I'm not sure about the situation for bipartite graphs, but perhaps we can relate this to the biclique problem in bipartite graphs. $\endgroup$
    – D.W.
    Commented Nov 18, 2022 at 19:53
  • $\begingroup$ Is it correct to say that if you take the absolute value of the edges instead, you want to find a subset of vertices $S \subseteq V$ that maximizes the sum $\sum_{e \in E(S)} w(e) - \sum_{v \in S}w(v)$, where $E(S)$ are the edges that have both endpoints in S? $\endgroup$
    – Pål GD
    Commented Nov 18, 2022 at 21:59
  • $\begingroup$ If you're after fast algorithms in practice you at least need to tell us what order $n$, $m$, as well as your weights typically are. $\endgroup$
    – Pål GD
    Commented Nov 19, 2022 at 20:35

3 Answers 3

3
$\begingroup$

This problem can be reduced to the maximum flow problem. That is, this problem is as an instance of the closure problem, where we have variables for vertices and edges of the original graph, and has constraints $x_e \implies x_u$ and $x_e \implies v$ for each edge $e = \{u,v\}$.

I don't know this particular problem has a specific name. The parametric version of the densest subgraph problem is essentially the same problem.

$\endgroup$
2
$\begingroup$

The problem is solvable in polynomial time.

Let $G = (V, E)$ be any graph with positive weights $w: V \cup E \to \mathbb{N}$ on both edges and vertices. For a subset $S \subseteq V$ let $E(S)$ denote the set of edges in $G$ with both endpoints in $S$.

For such a set $S$, let $$f(S) = \sum_{e \in E(S)} w(e) - \sum_{v \in S} w(v).$$ The goal is to find a set $S \subseteq V$ that maximises $f(S)$.

Definition. A set function $f: 2^U \to \mathbb{N}$ is supermodular if for every $X$ and $Y$, $$f(X) + f(Y) \leq f(X \cup Y) + f(X \cap Y).$$

Theorem. Maximizing a supermodular function can be done in polynomial time.

Claim. $f$ is supermodular.

Proof of claim. There are three cases to consider. When $X$ and $Y$ are disjoint, when one is a subset of the other, and when they overlap. The two former are straightforward to verify, the latter can be shown by writing out the definitions.

  1. $X \cap Y = \emptyset$. $f(X) + f(Y) \leq f(X \cup Y) + 0$. In this case, $f(X \cup Y)$ can only be at least as large as the two since we count the vertices exactly once, and potentially add some extra edges (the edges between $X$ and $Y$).

  2. $X \subseteq Y$. $f(X \cap Y) = f(X)$, $f(X \cup Y) = f(Y)$, so the sums are equal.

  3. $X$ partially overlaps $Y$. Let's expand the definitions.

    • $f(X) + f(Y) = \sum_{e \in E(X)}w(e) + \sum_{e \in E(Y)}w(e) - \sum_{v \in X \cup Y}w(v) + \sum_{v \in X \cap Y}w(v)$
    • $f(X \cup Y) = \sum_{e \in E(X)}w(e) + \sum_{e \in E(Y)}w(e) + \sum_{e \in E(X, Y)}w(e) - \sum_{v \in X \cup Y}w(v)$
    • $f(X \cap Y) = \sum_{e \in E(X \cap Y)}w(e) - \sum_{v \in X \cap Y} w(v)$
    • Let's cancel out. The supermodular objective is true if and only if $\sum_{e \in E(X)}w(e) + \sum_{e \in E(Y)} \leq \sum_{e \in E(X \cup Y)}w(e) + \sum_{e \in E(X \cap Y)}w(e)$. But this is true because the righthand side can only contain more edges than the left-hand side (namely the ones going from $X$ to $Y$).
$\endgroup$
4
  • $\begingroup$ Great proof. Still looking for a way to actually compute the answer though. $\endgroup$ Commented Nov 19, 2022 at 19:52
  • $\begingroup$ There are concrete algorithms that compute your solution in polynomial time, albeit you should expect $O(n^8)$ or so. There are many fruitful venues you could explore, simple greedy approximation algorithms and randomized algorithms with good expected values. $\endgroup$
    – Pål GD
    Commented Nov 19, 2022 at 20:35
  • $\begingroup$ Actually, perhaps @D.W.'s suggestion is the best and simplest you can get, perhaps throw in some LP (randomized) rounding. $\endgroup$
    – Pål GD
    Commented Nov 19, 2022 at 21:13
  • $\begingroup$ So basically the polynomial algorithmic way would be slower than just using a ILP method? $\endgroup$ Commented Nov 19, 2022 at 22:37
1
$\begingroup$

[My previous answer contained an incorrect claim about NP-hardness.]

I don't know whether there is a polynomial-time algorithm.

If you have to solve this in practice, one possible solution would be to use integer linear programming (ILP). Introduce zero-or-one integer variables $x_v$, where $x_v$ means that node $v$ is selected to be in the subset. Add zero-or-one integer variables $y_{u,v}$ (for each edge $(u,v)$) and linear inequalities to model your problem, as follows:

  • An edge $(u,v)$ is selected iff both its endpoints are selected: $y_{u,v} \ge x_u + x_v - 1$, $y_{u,v} \le x_u$, $y_{u,v} \le x_v$.

Then minimize the following objective function

$$\sum_{v} \text{wt}(v) \, x_v + \sum_{u,v} \text{wt}(u,v) \, y_{u,v}.$$

Use an off-the-shelf ILP solver to solve this ILP instance. If your graphs aren't too large, an ILP solver may be able to find the optimal solution. If your graphs are large, then you can terminate search early and hope it finds a good-enough (even if not optimal) solution.

$\endgroup$
4
  • $\begingroup$ Welp. Assuming you're right, then you certainly have the correct answer here. I'm glad I didn't spend a week trying to figure this out myself. Thanks! $\endgroup$ Commented Nov 18, 2022 at 21:31
  • $\begingroup$ In my actual examples, I'll never have more than about 50 nodes. So I think your pragmatic workaround is probably what I need. $\endgroup$ Commented Nov 18, 2022 at 21:33
  • $\begingroup$ @PålGD, you're right. This answer is wrong. $\endgroup$
    – D.W.
    Commented Nov 18, 2022 at 22:45
  • $\begingroup$ @thepenguin77, unfortunately, as Pål GD points out, my claim about NP-hardness was incorrect. So my answer was correct, and your question stands. I suggest you might want to unaccept this answer. $\endgroup$
    – D.W.
    Commented Nov 18, 2022 at 22:46

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.