Colored cut games

In a graph G = ( V, E ) with an edge coloring ℓ: E → C and two distinguished vertices s and t, a colored ( s, t ) -cut is a set C ˜ ⊆ C such that deleting all edges with some color c ∈ C ˜ from G disconnects s and t. Motivated by applications in the design of robust networks, we introduce colored cut games. In these games, an attacker and a defender choose colors to delete and to protect, respectively, in an alternating fashion. The attacker wants to achieve a colored ( s, t ) -cut and the defender wants to prevent this. First, we show that for an unbounded number of alternations, colored cut games are PSPACE-complete even on subcubic graphs. We then show that, even on subcubic graphs, colored cut games with i alternations are complete for classes in the polynomial hierarchy whose level depends on i. To complete the dichotomy, we show that all colored cut games are polynomial-time solvable on graphs with maximum degree at most 2. Next, we show that all colored cut games admit a polynomial kernel for the parameter k + κ r where k denotes the total attacker budget and, for any constant r, κ r is the number of vertex deletions that are necessary to transform G into a graph where the longest path has length at most r. For κ 1, which is the vertex cover number vc of the input graph, the kernel has size O ( vc 2 k 2 ). Moreover, we introduce an algorithm solving the most basic colored cut game, Colored ( s, t ) -Cut, in 2 vc + k n O ( 1 ) time.

Authors

• Nils Morawietz
• Niels Grüttemeier
• Christian Komusiewicz Institute of Computer Science, Friedrich Schiller University Jena, Germany
• Frank Sommer Institute of Logic and Computation, TU Wien, Austria

Keywords

• Labeled cut
• Labeled path
• Network robustness
• Kernelization
• PSPACE
• Polynomial hierarchy