New answers tagged

2 votes

Find Minimum Transformation Between Multisets of Lists of Cards

Update (or possible correction) to the answer of D.W.. Since we are given the move operations and not the swap operations, we can compute $\pi$ in polynomial time. The problem is known as the ...
Inuyasha Yagami's user avatar
5 votes
Accepted

Find Minimum Transformation Between Multisets of Lists of Cards

I think the variant with sets can be solved using bipartite matching. Build a complete bipartite graph, with one left vertex per set in s0 and one right vertex per set in s1. Also, if there are fewer ...
D.W.'s user avatar
  • 156k
0 votes

Hardness of approximation for Disjoint Group Steiner Tree

As noted in the second paragraph of section 18.2 of these lecture notes, https://www.cs.cmu.edu/afs/cs/academic/class/15854-f05/www/scribe/lec18.pdf, one can actually assume that the groups are ...
NaturalLogZ's user avatar
0 votes
Accepted

Maximum reachable checkers on a checkerboard

One approach would be to express this as an instance of SAT, and use an off-the-shelf SAT solver. See Boolean constraints for a connected component of a graph for a technique for encoding ...
D.W.'s user avatar
  • 156k
0 votes

Optimizing Delivery Routes in a Graph-Based Network to Minimize Maximum Delivery Time

The problem is unlikely to admit any efficient solution since it is NP-Hard even when there is only one delivery person and, for all edges $(u,v)$ in the graph, the distance between $u$ and $v$ is $1$....
Steven's user avatar
  • 28.4k
3 votes
Accepted

Optimal torch placement in voxel games

No, assuming $\mathsf{P} \neq \mathsf{NP}$ there is no efficient algorithm for optimal torch placement, even if the world is just a 2D grid. This can be shown by providing a reduction from the vertex ...
Steven's user avatar
  • 28.4k

Top 50 recent answers are included