8
$\begingroup$

I encounter this problem recently and I want to know whether it is NP-Complete or solvable in polynomial time:

Given a undirected weighted bipartite graph $G = (V, E)$ where $V$ can be partitioned into two sets $A$ and $B$ and $E$ is a set of edges connecting $A$ and $B$. The weight of an edge $(v, u)$ is denoted as $w(v, u)$. All weights are positive integers.

Do the following sequentially:

  1. Pick a node $v \in A$,
  2. remove all node $u \in B$ for every $(v, u) \in E$ and,
  3. add the weight $w(v, u)$ to the total score for every edges deleted.

The goal is to find the sequence of nodes $v_1, \dots, v_n \in A$ that maximizes the total score.

I have searched for the bank of NP-Complete problems to find something possible can reduce to this problem but I haven't found anything useful yet. Any suggestions would be extremely helpful!

$\endgroup$
  • $\begingroup$ Cross-posted from Stack Overflow, not that I expect this non-research-level question to stay open here: stackoverflow.com/questions/25632686/… $\endgroup$ – David Eisenstat Sep 2 '14 at 22:14
  • 5
    $\begingroup$ David, I don't see why this question is non-research-level. It's probably NP-complete but I don't see any obvious reduction from a standard problem. However, it might be more appropriate for cstheory.stackexchange.com. $\endgroup$ – Timothy Chow Sep 3 '14 at 1:35
  • $\begingroup$ If we relax the problem to allow deleting only some of the neighbours of $v$, not necessarily all of them, it becomes a minimum-cost flow problem which is polynomial. $\endgroup$ – Brendan McKay Sep 3 '14 at 6:53
  • 4
    $\begingroup$ @DimaPasechnik: As I understand it, the order does matter. If you remove a node in step 2, the weights of its incident edges are no longer available for step 3 of subsequent iterations. $\endgroup$ – Emil Jeřábek Sep 3 '14 at 9:58
  • 1
    $\begingroup$ Having said that, the OP should indeed clarify whether the weights can be negative, and also whether they are given in binary or unary. $\endgroup$ – Emil Jeřábek Sep 3 '14 at 10:02
6
$\begingroup$

It's NP-complete (even for 0-1 weights) by a reduction from feedback arc set in directed graphs. Let D be a digraph in which you want to compute a feedback arc set, A be the vertices of D, B be the edges of D, and E be the vertex-edge incidence relation of D. Assign a weight 1 for ab when a is the incoming endpoint of b, and 0 when it is the outgoing endpoint. Then the total weight of an ordering of A is the same as the number of edges of D that are consistent with the ordering.

If you have a minimum feedback arc set of D and reverse those edges, the result will be a directed acyclic graph and a topological ordering of this DAG will be consistent with all edges not in the feedback arc set. Conversely, if you order the vertices of D arbitrarily and look at the set of inconsistently oriented edges, they will be a feedback arc set. So the inconsistently ordered edges for an optimal ordering of (A,B,E) will be exactly a minimum feedback arc set.

$\endgroup$
4
$\begingroup$

The problem is NP-hard. Without loss of generality we shall prove this in the case that all the weights are positive integers. First let us rephrase the problem as follows.

Given an integer-valued matrix, find the reordering of the columns that maximizes the score of the resulting reordered matrix, where the score of a matrix is defined as follows: It is the sum of the scores of the rows, where the score of a row is the value of the leftmost nonzero entry in that row (or zero if the row is all zero, but clearly we may assume that there are no all-zero rows).

To see the equivalence, let the columns correspond to the vertices of $A$ and let the rows correspond to the vertices of $B$; zeros correspond to non-edges and the integers correspond to the edge weights. The following reduction from SAT to (the decision version of) the above problem is due to my colleague Sandy Kutin.

Suppose we are given a SAT instance with $m$ clauses and $n$ variables. Without loss of generality we shall assume that for each variable $x$, one of the clauses in the system is $x\vee\bar x$. We now construct a matrix with $2n+1$ columns and $m+2n$ rows as follows. For each variable $x$ we have two columns, one labeled $x$ and the other labeled $\bar x$. We also have a special column labeled $z$.

For each clause, we create a row; for each literal in the clause, we put the value $2n+2$ in the corresponding column, and we put a 1 in the $z$ column. In the other columns we put zero. This gives us the first $m$ rows. Then for each of the $2n$ literals, we create a row with a 1 in the column corresponding to that literal and a 2 in the $z$ column. Now we ask the question:

Is there a reordering of the columns with score at least $m(2n+2) + 3n$?

If the SAT instance is satisfiable, then the answer is yes: For each literal $x$ that is TRUE, put the $x$ column to the left of the $z$ column and the $\bar x$ column to the right of the $z$ column. Then we score $2n+2$ for each of the first $m$ rows and a total of $3n$ for the remaining $2n$ rows.

Conversely, in order to score as high as $m(2n+2)+3n$, we need to score $2n+2$ for each of the first $m$ rows, since scoring only $1$ for one of those rows sacrifices $2n+1$, which is more than we can make up for using the final $2n$ rows. Therefore for every clause, at least one of the literals in it must have its column to the left of the $z$ columns. To pick up an additional $3n$ from the remaining $2n$ rows, it must be the case that for each literal $x$, either the $x$ or the $\bar x$ column must appear to the right of the $z$ column (they cannot both appear to the right because then we would fail to score $2n+2$ from the $x\vee\bar x$ row). Thus by picking all the literals to the left of the $z$ column, we obtain a satisfying assignment.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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