Colored Cut Games

Nils Morawietz, Niels Grüttemeier, Christian Komusiewicz, Frank Sommer

TL;DR

This paper introduces "colored cut games," a new class of computational problems modeling network security scenarios where an attacker tries to disconnect two points by deleting colored edges, and a defender tries to prevent this by protecting colors. The authors establish the complexity of these games, showing they are PSPACE-complete in general but solvable in polynomial time on simple graphs, and provide a polynomial kernelization for parameterized versions.

What Problem Does This Paper Address?

The paper tackles the problem of network robustness in scenarios where network links have associated "colors," and the failure of a color affects all links of that color. Specifically, they define a "colored (s,t)-cut" as a set of colors whose removal disconnects two designated vertices, s and t. This is motivated by real-world applications where the failure of one component (e.g., a specific technology or resource) can cascade and disable multiple network links. The core problem is to understand the computational complexity of games where an attacker aims to achieve such a colored cut by choosing colors to delete, while a defender tries to prevent it by choosing colors to protect, in an alternating fashion. This introduces a game-theoretic element to classic cut problems.

Methods

The authors employ a combination of techniques from computational complexity theory, parameterized complexity, and graph algorithms.

  • Complexity Analysis: They establish PSPACE-completeness for the most general version of the colored cut games (unbounded alternations) by reducing from the PSPACE-complete COMPETITIVE HITTING SET problem. They also analyze the complexity for a bounded number of alternations, showing it relates to levels of the polynomial hierarchy.
  • Parameterized Complexity: A significant contribution is the development of polynomial kernelizations for colored cut games. This involves reducing an instance of a game to a smaller, equivalent instance based on parameters like the attacker's budget (k) and structural graph properties like the r-lp-deletion number (κ_r), which is related to vertex cover. They leverage techniques like the Sunflower Lemma for this.
  • Algorithmic Techniques: They design specific algorithms for solving colored cut games, including an FPT algorithm for COLORED (s,t)-CUT parameterized by vertex cover and attacker budget.
  • Graph Transformations: To prove hardness results on restricted graph classes (e.g., bipartite planar graphs), they use graph transformations to construct "colored-cut-equivalent" graphs that preserve the game's outcome but have simpler structures.

Datasets

Not discussed in the paper. The paper focuses on theoretical complexity and algorithmic analysis of abstract graph problems, rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Game-Theoretic Robustness: The paper elegantly frames network robustness not just as finding a minimal cut, but as a strategic game between an attacker and defender, reflecting real-world security and resilience challenges.
  • PSPACE-Completeness for General Games: The finding that even simple colored cut games with unbounded turns are PSPACE-complete is significant, indicating their inherent computational difficulty.
  • Dichotomy for Bounded Turns: The complexity of colored cut games with a fixed number of turns is shown to be tightly linked to the polynomial hierarchy, providing a nuanced understanding of how the number of interactions affects difficulty.
  • Polynomial Solvability on Simple Graphs: The result that games are polynomial-time solvable on graphs with maximum degree at most two offers a practical boundary for efficient solutions.
  • Powerful Kernelization for Parameterized Problems: The development of polynomial kernels for parameters like attacker budget combined with structural graph properties (e.g., vertex cover, r-lp-deletion number) is a major theoretical achievement, suggesting that these games can be efficiently solved for certain types of instances, even if they are hard in general.
  • Colored-Cut-Equivalence: The introduction of this concept provides a formal tool for reasoning about the equivalence of different game instances, crucial for reductions and kernelization proofs.

Key Results

  • Unbounded Alternations: Colored cut games are PSPACE-complete, even on planar graphs with unit budgets.
  • Bounded Alternations: For a constant number i of alternations, the games are complete for classes within the polynomial hierarchy, with complexity increasing with i.
  • Low-Degree Graphs: All colored cut games are polynomial-time solvable on graphs with maximum degree at most two.
  • Parameterized Kernelization: Polynomial kernels exist for colored cut games parameterized by the attacker budget k and the r-lp-deletion number κ_r. Specifically, for r=1 (vertex cover vc), a kernel with O(vc²k²) edges is obtained.
  • Efficient Algorithm for Basic Game: COLORED (s,t)-CUT can be solved in 2^{vc + k}n^{𝒪(1)} time.

Limitations and Future Work

  • Hardness for Specific Games: The paper notes that while they prove PSPACE-hardness for the general case, they do not know if the corresponding HITTING SET games (which are used in reductions) are hard for specific levels of the polynomial hierarchy. This leaves open whether the hardness for constant-round colored cut games is rooted in the game structure itself or in the construction of exponential path sets.
  • Kernel Size for Treedepth: While a kernelization result is provided for treedepth-r modulators, the resulting kernel size is doubly exponential in r, limiting its practical applicability for larger r.
  • Open Questions on Hitting Set Reductions: The authors pose whether the collection of color sets of (s,t)-paths, C(H), can be computed efficiently (in |C(H)|·|H|⁰⁽¹⁾ time), which would be beneficial for understanding reductions from colored cut games to HITTING SET.
  • Future Directions: The paper suggests exploring further efficient reductions and investigating the complexity of related problems.

Summary updated

Abstract

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 a family of problems called colored cut games. In these games, an attacker and a defender choose colors to delete and to protect, respectively, in an alternating fashion. It is the goal of the attacker to achieve a colored (s,t)-cut and the goal of the defender to prevent this. First, we show that for an unbounded number of alternations, colored cut games are PSPACE-complete. We then show that, even on subcubic graphs, colored cut games with a constant number i of 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 degree at most two. Finally, 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. In the case of r = 1, κ₁ is the vertex cover number vc of the input graph and we obtain a kernel with 𝒪(vc²k²) edges. Moreover, we introduce an algorithm solving the most basic colored cut game, Colored (s,t)-Cut, in 2^{vc + k}n^{𝒪(1)} time.
BibTeX
@inproceedings{morawietz2020colored,
  author = {Nils Morawietz and Niels Grüttemeier and Christian Komusiewicz and Frank Sommer},
  title = {{Colored Cut Games}},
  booktitle = {FSTTCS},
  year = {2020},
  doi = {10.4230/lipics.fsttcs.2020.30},
}
Figure