New answers tagged np-hardness
3
votes
Accepted
Balls in monochromatic bins
It is NP-hard, by reduction from multiway number partitioning: given an instance of multiway number partitioning, i.e., a multiset $S$ and a target $T$ and a positive integer $k$ so that $S$ sums to $...
- 11.1k
8
votes
Is it NP-hard to find an order on a set of strings so that the concatenation is a given string?
The problem is NP-hard already for $\Sigma = \{a, b\}$. (Of course, it is in PTIME if $|\Sigma| = 1$.) The reduction is from distinct-input 3-partition which is strongly NP-hard, i.e., intractable ...
- 8,223
4
votes
Accepted
Complexity of Exact Cover problem if containing a Set Cover means there is an Exact Cover
It's also NP-hard, because Set Cover on sets of constant size is NP-hard, and given an instance of Set Cover with constant-size sets, you can add all the (polynomially many) subsets of the given sets, ...
- 9,475
1
vote
NP-hardness: (planar) directed feedback vertex set problem with bounded degree
Thanks to Prof. @Yixin Cao's construction of the reduction, I think I have found a way to show that Planar-DFVS remains $\textsf{NP}$-hard when $(\Delta_{in}, \Delta_{out}) = (2, 2)$.
We use the ...
- 397
1
vote
Is the feedback vertex set problem on planar bounded degree graphs hard?
Here are the two gadgets Speckenmeyer used in his Ph.D. thesis. We can start from planar graphs with maximum degree six, by a reduction from the vertex cover problem on cubic planar graphs. (Actually, ...
- 2,560
1
vote
NP-hardness: (planar) directed feedback vertex set problem with bounded degree
Warning: this does not completely solve your question because the gadget is not planar. But since I could not find a proof of this, I think it might be worth posting.
Speckenmeyer proved that the ...
- 2,560
5
votes
NP-complete problems on posets?
Let $P$ be a poset and $L$ a linear extension of $P$. We say $(x,y)$ is a jump in $L$ if $x$ and $y$ are uncomparable in $P$ and there is no $z$ such that $x \leq_L z \leq_L y$. Given a poset $P$ and ...
- 1,785
Top 50 recent answers are included