License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2020.30
URN: urn:nbn:de:0030-drops-132719
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13271/
Morawietz, Nils ;
Grüttemeier, Niels ;
Komusiewicz, Christian ;
Sommer, Frank
Colored Cut Games
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 - Entry
@InProceedings{morawietz_et_al:LIPIcs:2020:13271,
author = {Nils Morawietz and Niels Gr{\"u}ttemeier and Christian Komusiewicz and Frank Sommer},
title = {{Colored Cut Games}},
booktitle = {40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)},
pages = {30:1--30:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-174-0},
ISSN = {1868-8969},
year = {2020},
volume = {182},
editor = {Nitin Saxena and Sunil Simon},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/13271},
URN = {urn:nbn:de:0030-drops-132719},
doi = {10.4230/LIPIcs.FSTTCS.2020.30},
annote = {Keywords: Labeled Cut, Labeled Path, Network Robustness, Kernelization, PSPACE, Polynomial Hierarchy}
}
|
Keywords: |
|
Labeled Cut, Labeled Path, Network Robustness, Kernelization, PSPACE, Polynomial Hierarchy |
|
Collection: |
|
40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
04.12.2020 |
