3
$\begingroup$

Given the following graph:

enter image description here

With the assumptions below:

  • A node on the left is linked to several nodes on the right
  • Nodes on the right are paired together: one is black, one is white
  • Each pair of nodes on the right can be swapped (black becomes white and white becomes black)
  • A node on the left is green if linked to only white or only black; red if linked to two colors.

The idea is to minimize the amount of red nodes, by flipping some black and white nodes. What is the best algorithm to do that?

(I think this problem has something to do with some sort of cycle detection? This problem is probably well-known on some equivalent form.)

Of course it will be often impossible to make all nodes green; here node V can never be (it is linked to B0 and B1). Some cycles also make all green impossible.

Extra question — same as above, but with a weight associated to each edge. Minimize the sum (for each node) of absolutes delta between white and black (difference between the sums of weights for white and black for each left node).


Where does this problem comes from?

A transit network is composed of stops, routes and trips.

  • Each trip belongs to one route
  • Each trip has one natural direction (0 or 1, inbound/outbound)
  • Each trip goes through a list of stops.
  • The direction of all trips within a route is arbitrary; so it is possible to invert the direction of all trips of a given route (but all trips together).

If all trips passing through a stop do have the same direction (all 0 or all 1) we can compute a "natural" direction for the stop. Otherwise we cannot. The idea is to flip route trips direction to minimize the number of stops where we cannot compute this "natural" direction.

Here the nodes on the left are stops, pair of nodes on the right routes, with black/white all trips for each route direction.

$\endgroup$
  • $\begingroup$ Why could an extra question called "bonus question"? What is the bonus? Take a moment to reflect. It seems only a question with bounty offered might be considered "a question with bonus". I know this phrase is used quite often in many situations. This is the situation it does not apply at all. Have you ever heard a news-reporter saying "here is a bonus question for you, President." in a new conference? Just say, "extra question". (By the way, you must have known that one question per a post is the most welcomed style, while pointing out related questions should be nice, of course.) $\endgroup$ – Apass.Jack Nov 22 '18 at 16:15
  • $\begingroup$ Welcome to Computer Science! Your question is very well-written. What progress have your made? Which approaches have you tried? $\endgroup$ – Apass.Jack Nov 22 '18 at 16:20
  • $\begingroup$ I haven't thought it through in detail, but cs.stackexchange.com/q/98157/1960 seems similar enough that the same idea might work. $\endgroup$ – Peter Taylor Nov 22 '18 at 18:21
  • $\begingroup$ @PeterTaylor Indeed Manber's graph partitionning looks promising, by adapting it a bit. So I guess this a NP-problem then... I was hoping not. (I can have a rather large numbers of nodes.) $\endgroup$ – Laurent Grégoire Nov 22 '18 at 18:53
  • 2
    $\begingroup$ Also, FWIW, I have no problem with the phrase "bonus question". It seems to me like a very mildly humorous way of asking a second, related question :) $\endgroup$ – j_random_hacker Nov 22 '18 at 22:52
1
$\begingroup$

You can reduce MAX-2-SAT to your problem. Therefore, your problem is NP-complete.

In MAX-2-SAT we have $n$ boolean variables $x_1, \dots, x_n$ and $m$ clauses of the form $a\vee b$ where $a$ and $b$ are $x_i$ or $\bar{x_i}$ (its complement). The goal is to assign $0$, and $1$ values to $x_i$'s such that the number of true clauses is maximized. This problem is NP-complete. For an arbitrary instance of MAX-2-SAT, we build an instance of your problems as follows. Hence, your problem is also NP-complete, i.e., kind of no chance for a polynomial-time algorithm for all cases.

We put $n+m$ pair of nodes ($x_i$ and $\bar{x_i}$ for $1\leq i\leq n$, and $y_k$ and $\bar{y_k}$ for $1\leq k\leq m$) on the right side and $3m$ node on the left (three nodes $v_{k,1}, v_{k,2}, v_{k,3}$ for $k$'th clause where $1\leq k\leq m$). Let $(x_i\vee x_j)$ be the $k$'th clause in our instance (other cases are similar). We put three nodes $v_{k,1}, v_{k,2}, v_{k,3}$ in the left side of our graph. We then connect

  • $v_{k,1}$ to $x_i$ and $x_j$,
  • $v_{k,2}$ to $x_i$, $\bar{x_j}$, and $y_k$,
  • $v_{k,3}$ to $\bar{x_i}$, $x_j$, and $y_k$.

At most one of the $v_{k,1}, v_{k,2}, v_{k,3}$ can gets a green color. Moreover, this happens if and only if the clause gets a true value. Therefore, the maximum number of green nodes in the instance of your problem is equal to the solution to MAX-2-SAT.

Your bonus problem is harder than the original version and is also NP-complete.

$\endgroup$
  • $\begingroup$ Well, if the first case is NP-complete, I guess the weighted one should also be, as the first case is a special case of the second where all $w=1$? $\endgroup$ – Laurent Grégoire Nov 23 '18 at 10:03
  • $\begingroup$ You are right. I noted this in the last sentence. $\endgroup$ – Mohemnist Nov 23 '18 at 18:37

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.