New answers tagged

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

Top 50 recent answers are included