# Tag Info

Accepted

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