3
$\begingroup$

Given a directed Graph and two vertices $S$ and $D$ (source and destination) such that each of its edges has a weight of the form:

$A_i+B_ix_i = V$

where $A_0$ is a non negative integer, $B_0$ is a positive integer, $x_i$ a variable that can take non negative integer values (each variable used only once in the graph).

Find a positive value $V$ such that it there exists a path from $S$ to $D$ in Graph such that $V$ satisfies all edges in that path.

Of course the trivial method would be testing each positive integer value of $V$. But this might take an exponential time. Is there something better we can do to achieve the solution in polynomial time, or that is the best we have ?

$\endgroup$
  • 1
    $\begingroup$ Something is missing here - what happens with the variables $x_i$? Are you looking for a value $V$, an assignment to the variables $x_i$, and an $S$-to-$D$ path such that all constraints along the edges of the path are satisfied? If so, you should update the question to make it clear. Perhaps you want all constraints on all paths to be satisfied? $\endgroup$ – Yuval Filmus Jun 12 '17 at 10:24
  • $\begingroup$ Are you interested in knowing whether a value $V$ exists, or in actually finding it? What if $V$ is very large? $\endgroup$ – Yuval Filmus Jun 12 '17 at 10:26
  • $\begingroup$ The variables $x_i$ is unique for each edge ($i$ being say the edge number). A value $V$ that satisfies one of the paths (all edges in it) from $S$ to $D$ (either finding it or saying one exists would be fine i suppose). The problem is $V$ can be very large, otherwise we can test all its values one at a time. (if you want please go ahead an edit to make it clearer as you please). $\endgroup$ – J.Doe Jun 12 '17 at 10:36
  • $\begingroup$ The first step would be to come up with a criterion for a set of constraints $A_i + B_ix_i = V$ to be jointly satisfiable. By assuming that $V$ is large enough, such a constraint just states that $V \equiv A_i \pmod{B_i}$. Two such constraints are contradictory iff $A_i \not\equiv A_j \pmod{(B_i,B_j)}$. $\endgroup$ – Yuval Filmus Jun 12 '17 at 10:41
  • $\begingroup$ I agree. I think (not sure as of now): a set of constraints $A_i + B_ix_i = V$ will be satisfiable iff there are no two constraints in the set such that: if $B_i$'s have a common factor > 1, and their corresponding $A_i$'s are not equal. $\endgroup$ – J.Doe Jun 12 '17 at 10:48
4
$\begingroup$

Assume first that the $x_i$ can take any arbitrary values. Then the constraint $A_i + B_i x_i = V$ just states that $V \equiv A_i \pmod{B_i}$. Two such constraints are contradictory if $A_i\not\equiv A_j \pmod{(B_i,B_j)}$, where $(B_i,B_j)$ is the GCD of $B_i$ and $B_j$. The Chinese Remainder Theorem should show (after some work) that any set of constraints in which no two are contradictory can be simultaneously satisfied. (Prove or refute!)

The constraint that $x_i \geq 0$ doesn't actually impose any further constraints. Indeed, take a solution $V$ to the original problem. By adding to $V$ a large enough multiply of $\prod_i B_i$, we obtain another solution in which all $x_i$ are non-negative.

This reduces your problem to the following problem:

Given a directed graph and a set of forbidden pairs of edges, does there exist a path from $s$ to $t$ that doesn't contain a forbidden pair of edges?

Unfortunately, this problem is NP-complete, by reduction from SAT. Given $m$ clauses $\varphi_1,\ldots,\varphi_m$, there will be $m+1$ vertices $v_0,\ldots,v_m$. For each literal $\ell \in \varphi_i$, there is a corresponding edge from $v_{i-1}$ to $v_i$. Two complementary literals form a forbidden pair. A legal path from $v_0$ to $v_m$ exists iff the instance is satisfiable.

There are now two options:

  • Either your particular instance has more structure, which you can employ to get a more efficient solution;
  • Or your original problem is also NP-hard.
$\endgroup$
  • $\begingroup$ Path with forbidden pairs. NP Complete reduction from 3SAT. I remeber this one. thanks. $\endgroup$ – J.Doe Jun 12 '17 at 10:55
  • $\begingroup$ You beat me to it! $\endgroup$ – Yuval Filmus Jun 12 '17 at 10:58
  • $\begingroup$ but you did help the reduction. P.S. Why on earth is every interesting problem NPComplete (rhetorical frustration) :) $\endgroup$ – J.Doe Jun 12 '17 at 11:00
1
$\begingroup$

Building on Yuval's answer, your problem is NP-complete. Yuval shows a reduction from your problem to the forbidden-pairs path problem, and from there to SAT. However as Yuval says this doesn't immediately prove that your problem is NP-complete, as the reduction goes the wrong way. I'll show a reduction in the other direction, thus proving that your problem is NP-complete.

Let $\varphi_1,\dots,\varphi_m$ be the clauses of a SAT instance on the variables $u_1,\dots,u_n$. Let $p_1,\dots,p_m$ denote the first $m$ primes. We'll have $m+1$ vertices, $v_0,\dots,v_m$. The edges are as follows:

  • For each positive literal $u_j$ that appears in $\varphi_i$, there will be a corresponding edge from $v_{i-1}$ to $v_i$, labelled with the constraint $V = 1 \pmod{p_j}$.

  • For each negative literal $\neg u_j$ that appears in $\varphi_i$, there will be a corresponding edge from $v_{i-1}$ to $v_i$, labelled with the constraint $V = 0 \pmod{p_j}$.

Now note that if there is a satisfying assignment to the SAT formula, then there is a valid path through this graph: in each clause, we pick one of the literals that is satisfied (there will always be at least one, if this is a satisfying assignment to the SAT formula), and use that to derive a path. The path will be valid, because we can set $V$ to be a value such that $V = u_1 \pmod{p_1}$, ..., $V = u_n \pmod{p_n}$ (the Chinese remainder theorem guarantees such a $V$ will exist), and then all of the edge constraints will be satisfied.

Conversely, if we have a valid path through this graph, then we can read off a satisfying assignment to the SAT formula: use $V \bmod p_j$ as the value of the variable $u_j$ (i.e., set $u_j$ to true if $V = 1 \pmod{p_j}$, or false otherwise), and then the structure of the graph ensures that this will satisfy at least one literal in each clause of the SAT formula.

This completes the reduction.

$\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.