<p>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 <em>NP-complete for planar (undirected or directed or directed acyclic) graphs of max-degree 3</em>.</p>

<p>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$:</p>

<ul>
<li>add a resource constraint set $M_k^+$ with <em>two vertices</em> for each positive literal $x_k$ in $\varphi$ and a resource constraint set $M_k^-$ with <em>two vertices</em> for each negative literal $\bar{x}_k$ in $\varphi$;</li>
<li>start building a graph from a source node $s$ and for each variable $x_i$ split the path in two <em>lines</em>: 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$;</li>
<li>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^-$;</li>
<li>finally add a sink node $t$.</li>
</ul>

<p>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|$).</p>

<p>Informally when traversing the variable section $x_i$, if you pick the upper line (<em>true</em> 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 (<em>false</em> 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).</p>

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

<p><img src="https://i.sstatic.net/AuuVp.png" alt="enter image description here"></p>

<p>$C_1 = x_1 \lor \bar{x}_2 \lor x_3$<br>
$C_2 = x_2 \lor \bar{x}_3 \lor x_4$<br>
$C_3 = \bar{x}_1 \lor x_3 \lor \bar{x}_2$</p>

<p>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 :-).</p>

<p>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).</p>

CC BY-SA 3.0
2014-05-02T18:08:54.610Z
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)
Saeed
CC BY-SA 3.0
2014-05-02T18:23:18.430Z
@Saeed: right, I'll edit the question. I use [yEd](http://www.yworks.com/en/products_yed_about.html) (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).
Marzio De Biasi
CC BY-SA 3.0
2014-05-02T18:27:25.597Z
Thanks ;) Many times I need a tool for fast drawing, I think this is quite fine.
Saeed
CC BY-SA 3.0
2014-05-02T17:34:37.570Z
2014-05-02T18:31:37.427Z
2014-05-02T18:31:37.427Z
Marzio De Biasi
<p>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!</p>

CC BY-SA 3.0
2011-09-22T04:45:50.383Z
Does it matter what the resource constraint is ? for example, is it in the form of a "number of links" constraint ?
Suresh Venkat
CC BY-SA 3.0
2011-09-22T12:25:01.433Z
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.
nomad
CC BY-SA 3.0
2011-09-23T15:00:18.603Z
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
Daniel Apon
CC BY-SA 3.0
2014-05-02T18:49:38.487Z
This is not constrained shortest path. CSP has a pseudo-polynomial time solution.
Saeed
<cc.complexity-theory><graph-algorithms><np-hardness><optimization>
On which classes of graphs is resource constrained shortest path (RCSP) NP-hard?
nomad
# On which classes of graphs is resource constrained shortest path (RCSP) NP-hard?

(Asked by: username_0 on 2011-09-22)

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!

**Tags:** cc.complexity-theory, graph-algorithms, np-hardness, optimization

> **Comments:**
> **username_1**: Does it matter what the resource constraint is ? for example, is it in the form of a "number of links" constraint ?  
> **username_0**: 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.  
> **username_2**: 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  
> **username_3**: This is not constrained shortest path. CSP has a pseudo-polynomial time solution.  

---

## 1 answers

### Answer by username_4 on 2014-05-02. Score: 6 | Accepted answer

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](https://i.sstatic.net/AuuVp.png)

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

> **Comments:**
> **username_3**: 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)  
> **username_4**: @username_3: right, I'll edit the question. I use [yEd](http://www.yworks.com/en/products_yed_about.html) (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).  
> **username_3**: Thanks ;) Many times I need a tool for fast drawing, I think this is quite fine.  

---

