patternMinor
Edge Constraint satisfaction in a Directed Graph Path?
Viewed 0 times
pathgraphdirectededgeconstraintsatisfaction
Problem
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 ?
$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 ?
Solution
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:
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.
Context
StackExchange Computer Science Q#76681, answer score: 4
Revisions (0)
No revisions yet.