8
$\begingroup$

I'm looking to link a problem I'm working on to a known NP-hard problem. I think I can model my problem as a resource constrained shortest path problem. However, the structure of my graph is not completely arbitrary. Thus, it will be useful to know when RCSP becomes hard. Is it hard for a DAG, for a planar DAG, for a DAG with bounded degree? Any help would be greatly appreciated!

$\endgroup$
  • $\begingroup$ Does it matter what the resource constraint is ? for example, is it in the form of a "number of links" constraint ? $\endgroup$ – Suresh Venkat Sep 22 '11 at 4:45
  • 2
    $\begingroup$ I don't know if the actual resource is relevant to the hardness result. However, the resource constraint is of the following form. There are some number (M) of forbidden sets, to which each vertex may belong. The constraints should encode that the satisfying shortest path doesn't pass through all of the vertices in any of these M sets (i.e. if forbidden set S contains k vertices, the shortest path may be adjacent to up to k-1 of them). Thus, each link adjacent to a constrained node holds that node's contribution to all of its forbidden sets and we seek a SP respecting these constraints. $\endgroup$ – nomad Sep 22 '11 at 12:25
  • 1
    $\begingroup$ Flipping through the literature on the problem, I've noticed a few things: 1) possible alternate names: constrained shortest path (CSP), quality of service routing (QoS) 2) the "standard" problem uses a cost on each edge, and a constant bound on the sum of costs on the shortest path 3) the problem is NP-complete on acyclic graphs $\endgroup$ – Daniel Apon Sep 23 '11 at 15:00
  • $\begingroup$ This is not constrained shortest path. CSP has a pseudo-polynomial time solution. $\endgroup$ – Saeed May 2 '14 at 18:49
6
$\begingroup$

I don't know if you're still interested in this (old) question, and if I understood well the resource constraints you gave in the comment; however it seems that your problem (which is slightly different from usual RCSP problems) is NP-complete for planar (undirected or directed or directed acyclic) graphs of max-degree 3.

The easy reduction is from 3-SAT. Given a formula $\varphi$ with $n$ variables $x_1,...x_n$ and $m$ clauses $C_1,...C_m$:

  • add a resource constraint set $M_k^+$ with two vertices for each positive literal $x_k$ in $\varphi$ and a resource constraint set $M_k^-$ with two vertices for each negative literal $\bar{x}_k$ in $\varphi$;
  • start building a graph from a source node $s$ and for each variable $x_i$ split the path in two lines: the upper one traverses one vertex of all the $M_k^-$ that correspond to a negative literal $\bar{x}_k$; the lower one traverses one vertex of all the $M_k^+$ that correspond to a positive literal $x_k$;
  • then for each $C_j$ split the path in 3 lines that traverse in parallel the 3 vertices corresponding to the literals of $C_j$ and that are picked from the corresponding $M_k^+$ or $M_k^-$;
  • finally add a sink node $t$.

A path from $s$ to $t$ exists if and only if the original formula is satisfiable (i.e. without loss of generality you can ask for a path of length $\leq |V|$).

Informally when traversing the variable section $x_i$, if you pick the upper line (true assignment) then you must "use" one of the vertices of all the $M_k^-$ resource constraint sets that also contain a vertex that can be used later to traverse (satisfy) a clause containing $\bar{x}_i$. If you pick the lower line (false assignment) then you must "use" one of the vertices of all the $M_k^+$ resource constraint sets that also contain a vertex that can be used later to traverse (satisfy) a clause containing $x_i$. When traversing each clause at least one of the three vertices must be contained in a $M_k$ that has not be "used" yet (i.e. at least one of them can be used to satisfy the clause).

The following figure should make the reduction clearer. The resource constraint sets $M_k$ are represented with distinct colors (and for every color there are exactly 2 vertices).

enter image description here

$C_1 = x_1 \lor \bar{x}_2 \lor x_3$
$C_2 = x_2 \lor \bar{x}_3 \lor x_4$
$C_3 = \bar{x}_1 \lor x_3 \lor \bar{x}_2$

You can also easily make the graph directed, acyclic and bipartite. Let me know if you need further details (or if I completely misunderstood the problem :-).

As noted by Saaed the problem is fixed-parameter tractable with respect to $k$ (just consider all possible subsets of constrained nodes and for each combination run the shortest path algorithm).

$\endgroup$
  • $\begingroup$ Also it's not bad to mentioning that it's FPT to $k$, just consider all possible subsets of constrained nodes. But what is your graph drawing tool? Do you have a suggestion for good and fast drawing tool in linux? (except graphviz or tikz) $\endgroup$ – Saeed May 2 '14 at 18:08
  • 1
    $\begingroup$ @Saeed: right, I'll edit the question. I use yEd (java app) ... you don't get professional drawings if compared to those produced by tikz (using TikZiT), but you can draw sketches very very fast (it took me ~5mins for the above). $\endgroup$ – Marzio De Biasi May 2 '14 at 18:23
  • $\begingroup$ Thanks ;) Many times I need a tool for fast drawing, I think this is quite fine. $\endgroup$ – Saeed May 2 '14 at 18:27

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.