Colored Cut Games

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



PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2020.30.pdf
  • Filesize: 0.54 MB
  • 17 pages

Document Identifiers

Author Details

Nils Morawietz
  • Philipps-Universität Marburg, Fachbereich Mathematik und Informatik, Germany
Niels Grüttemeier
  • Philipps-Universität Marburg, Fachbereich Mathematik und Informatik, Germany
Christian Komusiewicz
  • Philipps-Universität Marburg, Fachbereich Mathematik und Informatik, Germany
Frank Sommer
  • Philipps-Universität Marburg, Fachbereich Mathematik und Informatik, Germany

Acknowledgements

Some of the results of this work are also contained in the first author’s Master thesis [Nils Morawietz, 2019].

Cite AsGet BibTex

Nils Morawietz, Niels Grüttemeier, Christian Komusiewicz, and Frank Sommer. Colored Cut Games. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, pp. 30:1-30:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.FSTTCS.2020.30

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Problems, reductions and completeness
Keywords
  • Labeled Cut
  • Labeled Path
  • Network Robustness
  • Kernelization
  • PSPACE
  • Polynomial Hierarchy

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. Journal of the ACM, 42(4):844-856, 1995. Google Scholar
  2. Sanjeev Arora and Boaz Barak. Computational Complexity - A Modern Approach. Cambridge University Press, 2009. Google Scholar
  3. Mordechai Ben-Ari. Mathematical Logic for Computer Science, 3rd Edition. Springer, 2012. Google Scholar
  4. Augusto Bordini, Fábio Protti, Thiago Gouveia da Silva, and Gilberto Farias de Sousa Filho. New algorithms for the minimum coloring cut problem. International Transactions in Operational Research, 26(5):1868-1883, 2019. Google Scholar
  5. John Bruno and Louis Weinberg. A constructive graph-theoretic solution of the Shannon switching game. IEEE Transactions on Circuit Theory, 17(1):74-81, 1970. Google Scholar
  6. Stephen M. Chase. An implemented graph algorithm for winning Shannon switching games. Communications of the ACM, 15(4):253-256, 1972. Google Scholar
  7. David Coudert, Pallab Datta, Stephane Perennes, Hervé Rivano, and Marie-Emilie Voge. Shared risk resource group complexity and approximability issues. Parallel Processing Letters, 17(2):169-184, 2007. Google Scholar
  8. David Coudert, Stéphane Pérennes, Hervé Rivano, and Marie-Emilie Voge. Combinatorial optimization in networks with shared risk link groups. Discrete Mathematics & Theoretical Computer Science, 18(3), 2016. Google Scholar
  9. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  10. Holger Dell and Dieter van Melkebeek. Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. Journal of the ACM, 61(4):23:1-23:27, 2014. Google Scholar
  11. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. Google Scholar
  12. Jack Edmonds and Richard M. Karp. Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM, 19(2):248-264, 1972. Google Scholar
  13. Paul Erdös and Richard Rado. Intersection theorems for systems of sets. Journal of the London Mathematical Society, 1(1):85-90, 1960. Google Scholar
  14. Seyed Rasoul Etesami and Tamer Basar. Dynamic games in cyber-physical security: An overview. Dynamic Games and Applications, 9(4):884-913, 2019. Google Scholar
  15. Michael R. Fellows, Jiong Guo, and Iyad A. Kanj. The parameterized complexity of some minimum label problems. Journal of Computer and System Sciences, 76(8):727-740, 2010. Google Scholar
  16. Jörg Flum and Martin Grohe. Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2006. Google Scholar
  17. L. R. Ford and D. R. Fulkerson. Maximal flow through a network. Canadian Journal of Mathematics, 8:399–404, 1956. Google Scholar
  18. Sulamita Klein, Luerbio Faria, Ignasi Sau, Rubens Sucupira, and Uéverton Souza. On colored edge cuts in graphs. In Proceedings of the 1st Encontro de Teoria da Computaçao (ETC '16), Sociedade Brasileira de Computaçao, pages 780-783. CSBC, 2016. Google Scholar
  19. Xiannuan Liang and Yang Xiao. Game theory for network security. IEEE Communications Surveys & Tutorials, 15(1):472-486, 2013. Google Scholar
  20. Jelena Mirkovic, Peter Reiher, Christos Papadopoulos, Alefiya Hussain, Marla Shepard, Michael Berg, and Robert Jung. Testing a collaborative ddos defense in a red team/blue team exercise. IEEE Transactions on Computers, 57(8):1098-1112, 2008. Google Scholar
  21. Nils Morawietz. Computational complexity of network robustness in edge-colored graphs. Master’s thesis, Philipps-Universität Marburg, 2019. Google Scholar
  22. Nils Morawietz, Niels Grüttemeier, Christian Komusiewicz, and Frank Sommer. Refined parameterizations for computing colored cuts in edge-colored graphs. In Proceedings of the 46th International Conference on Current Trends in Theory and Practice of Informatics, (SOFSEM '20), volume 12011 of LNCS, pages 248-259. Springer, 2020. Google Scholar
  23. Jaroslav Nesetril and Patrice Ossona de Mendez. Tree-depth, subgraph coloring and homomorphism bounds. European Journal of Combinatorics, 27(6):1022-1041, 2006. Google Scholar
  24. Rolf Niedermeier. Invitation to Fixed-Parameter Algorithms. Oxford University Press, 2006. Google Scholar
  25. Sankardas Roy, Charles Ellis, Sajjan G. Shiva, Dipankar Dasgupta, Vivek Shandilya, and Qishi Wu. A survey of game theory as applied to network security. In Proceedings of the 43rd Hawaii International International Conference on Systems Science (HICSS '10), pages 1-10. IEEE Computer Society, 2010. Google Scholar
  26. Thomas J. Schaefer. On the complexity of some two-person perfect-information games. Journal of Computer and System Sciences, 16(2):185-225, 1978. Google Scholar
  27. Rubens André Sucupira. Problemas de cortes de arestas maximos e mínimos em grafos. PhD thesis, Universidade Federal do Rio de Janeiro, 2017. Google Scholar
  28. Yongge Wang and Yvo Desmedt. Edge-colored graphs with applications to homogeneous faults. Information Processing Letters, 111(13):634-641, 2011. Google Scholar
  29. Shengli Yuan, Saket Varma, and Jason P. Jue. Minimum-color path problems for reliability in mesh networks. In Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM '05), pages 2658-2669, 2005. Google Scholar
  30. Rico Zenklusen. Matching interdiction. Discrete Applied Mathematics, 158(15):1676-1690, 2010. Google Scholar
  31. Peng Zhang and Bin Fu. The label cut problem with respect to path length and label frequency. Theoretical Computer Science, 648:72-83, 2016. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail