# Playing with boxes: NP-hard? [Graph Theory]

You are playing with boxes on a $$K_{1, n}$$-$$\textbf{subdivision}$$ graph $$G:=(V, E)$$ whose number of vertices is odd, i.e., $$|V| \equiv 1$$ (mod $$2$$) with a given central point $$C$$ such that $$\forall v \in V - \{C\}, deg(v) \leq 2$$. Actually, $$C$$ is the center of the star graph $$G$$. Your goal is to move $$n:= (|V| - 1)/2$$ boxes ($$b_1-b_n$$) from their starting points to their terminal points. For each vertex $$v \in V-\{C\}$$, it is either the starting point $$s_i$$ of a box $$b_i$$ or the terminal point $$t_j$$ of a box $$b_j$$. The central point $$C$$ has $$k$$ vacant places $$S$$ ($$S \cap V = \emptyset$$) that do not collide with any path. Points in $$\{C\} \cup S$$ are neither starting points nor terminal points.

For each step, you choose a box $$i$$ and move it to a place $$p \in S \cup V$$. You will immediately fail this game if there is another box $$b_j \neq b_i$$ standing on your path, e.g., in the initial state of Case 1, if you try to move $$b_1$$ from $$s_1$$ to $$t_1$$ you will fail because $$b_2$$ blocks $$b_1$$ on $$s_2$$. If you fail to move some box, you also fail this game. You win this game iff you successfully move $$\textbf{all}$$ boxes from their starting points to their terminal points. In Case 1, if $$k=0$$, you can move $$b_3$$ from $$s_3$$ to $$t_3$$, $$b_2$$ from $$s_2$$ to $$s_3$$, $$b_1$$ from $$s_1$$ to $$t_1$$, $$b_2$$ from the $$s_3$$ to $$t_2$$. In Case 2, you will also need one vacant point $$vp$$. You can move $$b_1$$ from $$s_1$$ to $$vp$$, $$b_3$$ from $$s_3$$ to $$t_3$$, and $$b_2$$ from $$s_2$$ to $$t_2$$. Then, move $$b_1$$ from $$v_1$$ to $$t_1$$. If $$k=0$$ you will fail this game. In Case 3 you need $$3$$ vacant places $$vp_1$$, $$vp_2$$, $$vp_3$$. Your move sequence could be:

(1) $$b_3$$: $$s_3 \rightarrow vp_1$$; (2) $$b_1$$: $$s_1 \rightarrow vp_2$$; (3) $$b_2$$: $$s_2 \rightarrow vp_3$$; (4) $$b_3$$: $$vp_1 \rightarrow t_3$$; (5) $$b_1$$: $$vp_2 \rightarrow t_1$$; (6) $$b_2$$: $$vp_3 \rightarrow t_2$$. Please note that in Case 4 you only need $$1$$ vacant place $$vp$$. You can use this $$vp$$ to move $$\{b_4, b_5\}$$ to $$\{t_4, t_5\}$$, respectively. Then you have $$4$$ empty places, which are $$C$$, $$vp$$, $$s_4$$ (because $$b_4$$ has been moved to $$t_4$$), $$s_5$$. These $$4$$ places are enough for you to win this game.

$$\textbf{TL; DR}$$: Given the graph $$G$$ and $$k$$ vacant places, if there is a strategy that you can win, print one of your winning strategies, otherwise print $$-1$$.

Below is my idea: I think this problem is NP-hard. You might build a digraph that describes the dependency of boxes. For $$k=0$$ we can use topological sorting and for $$k>0$$, I think it is a feedback vertex set problem (https://en.wikipedia.org/wiki/Feedback_vertex_set), since moving one vertex to the vacant place is equivalent to removing a vertex from the digraph and winning the game seems like breaking all the cycles in the digraph. But I cannot do the reduction. Please help me win this game, or prove this problem is NP-hard (then I will try a greedy strategy).

• I move (not copy) this problem from Math Stackexchange (MSE). Jul 29 at 2:00
• Can you credit the source where you encountered this problem or share the motivation?
– D.W.
Jul 29 at 3:51
• @D.W. Thanks for your comments. First, this problem is originally proposed by me. Second, the motivation for this problem is arranging several trucks to deliver boxes on narrow roads. The players are trucks, not me, I am their coach^_^. Different from the VRP-PD problem, this game does not require the hamiltonicity, i.e. you might visit a vertex arbitrarily many times. However, for the VRP-PD problem boxes do not block the roads while in this problem roads are narrow so boxes would block the roads. Jul 29 at 4:14