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
Related Tags
np-hard × 770complexity-theory × 380
np-complete × 309
np × 156
reductions × 147
algorithms × 127
graphs × 111
optimization × 78
decision-problem × 58
approximation × 38
satisfiability × 37
time-complexity × 35
polynomial-time × 24
traveling-salesman × 23
p-vs-np × 20
polynomial-time-reductions × 20
3-sat × 19
partitions × 18
set-cover × 18
knapsack-problems × 16
subset-sum × 14
dynamic-programming × 13
combinatorics × 13
complexity-classes × 13
scheduling × 12