New answers tagged np-hard
2
votes
Accepted
Constant value NP-complete vs W[1]-hard
By definition, a parametrized reduction from a parametrized problem $A$ to $B$ needs to satisfy the following properties:
The reduction maps each instance $(x,k)$ of $A$ is mapped to some instance $(...
- 7,138
0
votes
Computing distance to clique in FPT time
I misunderstood what you meant by distance to clique.
Take the complement graph $\overline G$ of $G$. Then what is $D$ called? What is $V \setminus D$ called?
- 14.1k
1
vote
Accepted
Reduction from $2$-Partitioning to (simple) pairwise $2$-Partitioning
I think you took the problem the wrong way, but your idea is good.
Let $A = \{a_1, …, a_n\}$ be an instance of $2$-$\texttt{Partition}$. Let $B = \{(a_1 + 1, 1), …, (a_n+1, 1)\}$. Then $A$ is a ...
- 11.5k
0
votes
Prove the NP-hardness of problem
This problem is called $s$-$t$ $\texttt{NODE CONNECTEDNESS}$ and was proved to be $\#\mathsf{P}$-complete by Valiant in 1979 in The Complexity of Enumeration and Reliability Problems.
As such, it is $\...
- 11.5k
2
votes
Accepted
Is this varient of longest increasing nested sets problem NP-hard？
This problem is polynomial-time solvable.
Suppose we know the last selected $X_\ell$. Then, remove all $Y$s that have a non-empty intersection to $X_\ell$. Now, we don't have to check for the second ...
- 2,105
Top 50 recent answers are included