411. On the complexity of finding central configurations of the graph-generalized (n^2 − 1)-puzzle
Invited abstract in session WB-20: Complexity and Approximation, stream Combinatorial Optimization.
Wednesday, 10:30-12:00Room: Esther Simpson 2.11
Authors (first author is the speaker)
| 1. | Martijn van Ee
|
| Faculty of Military Sciences, Den Helder, Netherlands Defence Academy |
Abstract
In the graph-generalized (n^2 −1)-puzzle, we are given a graph and a set of tokens. In a configuration, each token is assigned to a vertex in the graph, and only one token can be placed on a vertex. We can transform a configuration into another by making moves, where in a move we slide a token along an edge to an unoccupied vertex. The distance between two configurations is defined as the length of the shortest sequence of moves to obtain one from the other. We consider the problem of finding central configurations for the graph-generalized (n^2 − 1)-puzzle. Here, we are given a set of K configurations, called scenarios. In Median Configuration, the goal is to find a configuration that minimizes the total distance from this configuration to each of the scenarios. In Center Configuration, the goal is to find a configuration that minimizes the maximum distance from this configuration to any of the scenarios. We show that finding the median configuration is NP-hard when K = 3, and that finding the center configuration is NP-hard when K = 2. We observe that the complexity heavily relies on the complexity of computing the shortest transformation between two configurations. Hence, we consider two special cases and a problem variant in which we can compute these shortest transformations in polynomial time. We identify several cases that are polynomially time solvable, and cases that are NP-hard.
Keywords
- Complexity and Approximation
- Combinatorial Optimization
- Graphs and Networks
Status: accepted
Back to the list of papers