# Tag Info

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

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