New answers tagged

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