patternMinor
NP-completeness of Induced disjoint paths
Viewed 0 times
completenesspathsdisjointinduced
Problem
In graph theory, it is well-known to be NP-complete the problem of given a set of $k$ pairs of source-sink, deciding whether there exists $k$ vertex-disjoint paths connecting these pairs.
Our problem is a variant in which the requirement of being vertex-disjoint is replaced by being induced.
A set of $k$ paths is said to be induced if:
Input: A graph $G(V,E)$ and $k$ pairs of source-sink $\{(s_1,t_1),\dots,(s_k,t_k)\}$
Output: YES if there exists (a set of) $k$ induced paths connecting $s_i$ to $t_i$ for every $1\leq i\leq k$, NO otherwise.
Is this problem NP-complete?
Our problem is a variant in which the requirement of being vertex-disjoint is replaced by being induced.
A set of $k$ paths is said to be induced if:
- They are vertex-disjoint.
- Each one is itself an induced path.
- No edge connects two vertices of two different paths.
Input: A graph $G(V,E)$ and $k$ pairs of source-sink $\{(s_1,t_1),\dots,(s_k,t_k)\}$
Output: YES if there exists (a set of) $k$ induced paths connecting $s_i$ to $t_i$ for every $1\leq i\leq k$, NO otherwise.
Is this problem NP-complete?
Solution
Your problem is NP-hard (and so NP-complete), by reduction from 3SAT.
Consider a 3SAT instances with variables $x_1,\ldots,x_n$ and clauses $C_1,\ldots,C_m$.
For each variable $x_i$, there are four vertices $a_i,T_i,F_i,b_i$, connected as follows: $a_i-T_i-b_i$ and $a_i-F_i-b_i$.
For each clause $C_j = \ell_{j,1} \lor \ell_{j,2} \lor \ell_{j,3}$ (where $\ell_{j,1},\ell_{j,2},\ell_{j,3}$ are literals), there are five vertices $c_j,L_{j,1},L_{j,2},L_{j,3},d_j$, connected as follows: $c_j-L_{j,k}-d_j$ (for $k=1,2,3$).
Additionally, if $\ell_{j,k} = x_i$ then we connect $L_{j,k}$ with $F_i$, and if $\ell_{j,k} = \bar{x}_i$ then we connect $L_{j,k}$ with $T_i$.
The source-sink pairs are $(a_i,b_i)$ (for $i=1,\ldots,n$) and $(c_j,d_j)$ (for $j=1,\ldots,m$).
Each $a_i-b_i$ path corresponds to a truth assignment of $x_i$, and each $c_j-d_j$ path corresponds to a choice of a satisfied literal in $C_j$.
Consider a 3SAT instances with variables $x_1,\ldots,x_n$ and clauses $C_1,\ldots,C_m$.
For each variable $x_i$, there are four vertices $a_i,T_i,F_i,b_i$, connected as follows: $a_i-T_i-b_i$ and $a_i-F_i-b_i$.
For each clause $C_j = \ell_{j,1} \lor \ell_{j,2} \lor \ell_{j,3}$ (where $\ell_{j,1},\ell_{j,2},\ell_{j,3}$ are literals), there are five vertices $c_j,L_{j,1},L_{j,2},L_{j,3},d_j$, connected as follows: $c_j-L_{j,k}-d_j$ (for $k=1,2,3$).
Additionally, if $\ell_{j,k} = x_i$ then we connect $L_{j,k}$ with $F_i$, and if $\ell_{j,k} = \bar{x}_i$ then we connect $L_{j,k}$ with $T_i$.
The source-sink pairs are $(a_i,b_i)$ (for $i=1,\ldots,n$) and $(c_j,d_j)$ (for $j=1,\ldots,m$).
Each $a_i-b_i$ path corresponds to a truth assignment of $x_i$, and each $c_j-d_j$ path corresponds to a choice of a satisfied literal in $C_j$.
Context
StackExchange Computer Science Q#109952, answer score: 3
Revisions (0)
No revisions yet.