Polizisten und Räuber auf mehrschichtigen Graphen

Wir verallgemeinern das beliebte Spiel Polizisten und Räuber auf mehrschichtige Graphen, wobei jeder Polizist und der Räuber auf eine einzelne Schicht (oder Kante) beschränkt sind. Wir zeigen, dass die anfängliche Intuition zur optimalen Zuteilung von Polizisten zu Schichten nicht immer korrekt ist, und beweisen, dass die mehrschichtige Polizistenzahl weder von oben noch von unten durch eine steigende Funktion der Polizistenzahlen der einzelnen Schichten beschränkt ist. Wir stellen fest, dass es NP-schwer ist zu entscheiden, ob k Polizisten ausreichen, um den Räuber zu fangen, selbst wenn jede Polizistenschicht ein Baum und eine Menge isolierter Punkte ist. Wir geben jedoch einen Algorithmus in polynomialer Zeit an, um zu bestimmen, ob k Polizisten gewinnen können, wenn die Räuberschicht ein Baum ist. Darüber hinaus untersuchen wir die Frage nach den schlimmsten Fallteilungen eines einfachen Graphen in Schichten: Gegeben sei ein einfacher Graph G, was ist die maximale Anzahl von Polizisten, die erforderlich ist, um einen Räuber in allen mehrschichtigen Graphen zu fangen, bei denen jede Kante von G in mindestens einer Schicht ist und alle Schichten verbunden sind? Für Cliquen, geeignete dichte Zufallsgraphen und Graphen mit begrenzter Baumweite bestimmen wir diesen Parameter bis auf multiplikative Konstanten. Schließlich betrachten wir eine mehrschichtige Variante von Meyniels Vermutung und zeigen die Existenz einer unendlichen Familie von Graphen, deren mehrschichtige Polizistenzahl von unten durch eine Konstante mal n / n beschränkt ist, wobei n die Anzahl der Punkte im Graphen ist.