2026-07-22T11:26:15Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13271 2024-03-06T10:51:59Z ddc:004 open_access

Colored Cut Games Morawietz, Nils Grüttemeier, Niels Komusiewicz, Christian Sommer, Frank Labeled Cut Labeled Path Network Robustness Kernelization PSPACE Polynomial Hierarchy 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nils Morawietz and Niels Grüttemeier and Christian Komusiewicz and Frank Sommer 2020 Is Part Of LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2020.30 urn:nbn:de:0030-drops-132719 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.30 eng https://creativecommons.org/licenses/by/3.0/legalcode