pith. sign in

arxiv: 2605.17572 · v1 · pith:REIP5GICnew · submitted 2026-05-17 · 💻 cs.CC · cs.GT

Modelling Network Resilience: The Complexity of Some Graph Division Games

Grzegorz Gutowski , Konstanty Junosza-Szaniawski , Antonio Lauerbach , Alexander Wolff This is my paper

Pith reviewed 2026-05-19 22:22 UTC · model grok-4.3

classification 💻 cs.CC cs.GT
keywords graph gamesnetwork resiliencecontroller placementNP-completenessSigmaP2-completenessinterval graphsbounded treewidth
0
0 comments X

The pith

Deciding optimal controller placement to maximize reachable surviving vertices after deletions is NP-complete or ΣP2-complete.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies a two-player game on an undirected graph motivated by software-defined network controller placement. One player places a fixed number of controllers on vertices while the other deletes a fixed number of vertices; the first player's score equals the total number of remaining vertices that remain connected to at least one controller. The authors prove that computing the best guaranteed score or deciding whether it meets a given threshold is NP-complete or ΣP2-complete for the natural variants of move order and strategy type. These hardness results show that exact optimal placement cannot be computed efficiently on arbitrary networks under the connectivity-based resilience measure. The same problems admit polynomial-time algorithms when the input graph is an interval graph or has bounded treewidth.

Core claim

We show that the natural problems of computing optimal controller placements or game values in this defender-attacker model are NP-complete or ΣP2-complete, depending on whether players move sequentially or simultaneously and whether they employ pure or mixed strategies. These hardness results apply to the problems of deciding if the defender can guarantee a score of at least a given threshold. For graphs that are interval graphs or have bounded treewidth, the problems admit polynomial-time solutions.

What carries the argument

The defender-attacker zero-sum game on an undirected graph in which the defender selects a limited set of controller vertices and the attacker deletes a limited set of vertices, with the defender's payoff defined as the total number of surviving vertices reachable from any remaining controller.

If this is right

  • Exact optimal controller placement cannot be computed in polynomial time for general networks under most game variants.
  • Polynomial-time exact solutions exist for interval graphs, covering certain linear or path-like network topologies.
  • Polynomial-time exact solutions exist for graphs of bounded treewidth, covering many recursively structured or series-parallel networks.
  • The precise complexity class depends on move ordering and whether strategies are pure or mixed.
  • Heuristic or approximation methods are necessary for controller placement on large real-world networks.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Alternative resilience metrics such as maximum flow or edge-connectivity could be studied to obtain tractable optimization problems.
  • The same game formulation might apply directly to sensor placement or facility location under adversarial vertex failures.
  • The dynamic-programming techniques for bounded treewidth might extend to graphs with small treewidth plus a small number of extra vertices.
  • Parameterized algorithms with the number of controllers or deletions as the parameter could still be useful even when the problem is hard in the classical sense.

Load-bearing premise

The resilience quality is captured exactly by the count of vertices reachable from controllers in the undirected residual graph after deletions.

What would settle it

A polynomial-time algorithm that computes the defender's optimal pure-strategy score in the simultaneous-move variant on arbitrary graphs.

read the original abstract

Motivated by the controller placement problems in software-defined networks and the fair division principles of classical "cake cutting", we investigate the following two-player zero-sum game. In our model, a defender places a limited number of controllers on graph vertices, while an attacker deletes a limited number of vertices. The defender score is the total number of surviving vertices reachable from any remaining controller. We formalize the computational problems associated with various game dynamics (defender plays first; attacker plays first; players play simultaneously; pure or mixed strategies). We show that these natural problems are $\mathsf{NP}$-complete or $\Sigma^\mathsf{P}_2$-complete, depending on the specific variant. These hardness results provide limitations for optimal controller placement algorithms under different notions of quality of a solution. Finally, we present structural insights that yield efficient algorithms for restricted graph classes (namely interval graphs and graphs of bounded treewidth).

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The paper introduces a two-player zero-sum game on undirected graphs motivated by controller placement in software-defined networks. A defender places at most k controllers while an attacker deletes at most m vertices; the defender's score equals the number of surviving vertices reachable from any remaining controller under ordinary undirected connectivity. The authors formalize decision problems for four game dynamics (defender-first, attacker-first, simultaneous pure strategies, and mixed strategies) and prove that the first two are NP-complete while the latter two are ΣP₂-complete. They additionally give polynomial-time algorithms for the problems restricted to interval graphs and graphs of bounded treewidth.

Significance. If the results hold, the hardness theorems establish that exact optimal controller placement is intractable under the stated resilience metric, supplying concrete complexity barriers that any practical algorithm must circumvent via approximation or heuristics. The tractability results for interval graphs and bounded-treewidth graphs are a clear strength, identifying structured network topologies where optimal solutions can be computed efficiently. The work usefully combines standard complexity reductions with graph-algorithmic techniques and supplies both negative and positive results.

major comments (1)
  1. [§3.2] §3.2 (attacker-first variant): the ΣP₂-completeness reduction must ensure that the constructed graph's reachability score after deletions exactly encodes the quantified Boolean formula without spurious surviving components; a concrete verification that no auxiliary vertices remain reachable independently of the formula would strengthen the argument.
minor comments (2)
  1. [Introduction] The modeling section assumes undirected connectivity; a short paragraph explaining why this matches the intended SDN resilience notion (or noting it as an abstraction) would clarify the scope of the hardness claims relative to directed or capacity-constrained variants.
  2. [§5] In the bounded-treewidth algorithm, the dependence on treewidth w should be stated explicitly (e.g., 2^{O(w)} n) rather than left implicit in the O(n) claim.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading of the manuscript, the positive overall assessment, and the recommendation for minor revision. The single major comment is addressed below; we agree that an explicit verification paragraph will strengthen the presentation of the reduction without altering its correctness.

read point-by-point responses

  1. Referee: [§3.2] §3.2 (attacker-first variant): the ΣP₂-completeness reduction must ensure that the constructed graph's reachability score after deletions exactly encodes the quantified Boolean formula without spurious surviving components; a concrete verification that no auxiliary vertices remain reachable independently of the formula would strengthen the argument.

    Authors: We agree that an explicit verification step improves clarity. In the reduction of Section 3.2, every auxiliary vertex is attached via edges that are only traversable when the corresponding literal or clause is satisfied under the quantified assignment; the construction ensures that any surviving component not encoding a satisfying assignment is disconnected from all controllers by the deletion pattern. To address the referee's point directly, the revised manuscript will include a short dedicated paragraph immediately after the reduction that enumerates the possible auxiliary components and shows, case by case, that none can remain reachable independently of the QBF outcome. This addition is purely expository and does not change the proof. revision: yes

Circularity Check

0 steps flagged

No circularity; hardness via standard reductions from known problems

full rationale

The paper defines a reachability-based game score explicitly, then proves NP-completeness and ΣP2-completeness for placement/attack variants via polynomial reductions from established hard problems (e.g., standard graph problems or SAT variants). These reductions are independent of the paper's own inputs or prior self-citations; the central claims rest on conventional complexity-theoretic techniques rather than self-definition, fitted parameters renamed as predictions, or load-bearing self-citation chains. The derivation is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on standard graph-theoretic definitions of undirected graphs, vertex connectivity, and reachability, plus standard complexity classes; no free parameters, ad-hoc axioms, or new invented entities are introduced beyond the game rules themselves.

axioms (1)
  • standard math Undirected graphs with standard reachability via paths.
    The defender score is defined using reachable vertices after deletions.

pith-pipeline@v0.9.0 · 5691 in / 1249 out tokens · 45095 ms · 2026-05-19T22:22:01.301852+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

12 extracted references · 12 canonical work pages

  1. [1]

    Cambridge University Press, 2009.doi:10.1017/CBO9780511804090

    1 Sanjeev Arora and Boaz Barak.Computational Complexity: A Modern Approach. Cambridge University Press, 2009.doi:10.1017/CBO9780511804090. 2 Md. Faizul Bari, Arup Raton Roy, Shihabur Rahman Chowdhury, Qi Zhang, Mohamed Faten Zhani, Reaz Ahmed, and Raouf Boutaba. Dynamic controller provisioning in software defined networks. In9th International Conference o...

    work page doi:10.1017/cbo9780511804090 2009

  2. [2]

    Finding good approximate vertex and edge partitions is NP-hard.Information Processing Letters, 42(3):153–159, 1992.doi:10.1016/0020-0190(92) 90140-Q

    14 Thang Nguyen Bui and Curt Jones. Finding good approximate vertex and edge partitions is NP-hard.Information Processing Letters, 42(3):153–159, 1992.doi:10.1016/0020-0190(92) 90140-Q. 15 Jean Cardinal and Gwenaël Joret. Hitting all maximal independent sets of a bipartite graph. Algorithmica, 72(2):359–368, 2015.doi:10.1007/s00453-013-9847-3. 16 Steven C...

    work page doi:10.1016/0020-0190(92 1992

  3. [3]

    Fomin and Lukasz Kowalik and Daniel Lokshtanov and D

    doi:10.1007/978-3-319-21275-3. 16 The Complexity of Some Graph Division Games 19 Tamal Das, Vignesh Sridharan, and Mohan Gurusamy. A survey on controller placement in SDN.IEEE Communications Surveys & Tutorials, 22(1):472–503, 2020.doi:10.1109/COMST. 2019.2935453. 20 Aris Deligkas, Eduard Eiben, Robert Ganian, Thekla Hamm, and Sebastian Ordyniak. The para...

    work page doi:10.1007/978-3-319-21275-3 2020

  4. [4]

    31 Ayumi Igarashi and Dominik Peters

    doi:10.1109/ACCESS.2020.3047210. 31 Ayumi Igarashi and Dominik Peters. Pareto-optimal allocation of indivisible goods with connectivity constraints. In33rd AAAI Conference on Artificial Intelligence (AAAI), pages 2045–2052, 2019.doi:10.1609/aaai.v33i01.33012045. 32 Konstanty Junosza-Szaniawski and Dariusz Nogalski. Game-theoretic approach to attack planni...

    work page doi:10.1109/access.2020.3047210 2020

  5. [5]

    39 Michał Pióro, Mariusz Mycek, Artur Tomaszewski, Konstanty Junosza-Szaniawski, and Dariusz Nogalski

    URL:http://www.aaai.org/Library/ICML/2003/ icml03-071.php. 39 Michał Pióro, Mariusz Mycek, Artur Tomaszewski, Konstanty Junosza-Szaniawski, and Dariusz Nogalski. Finding optimal mixed strategies in a matrix game between the attacker and the network operator. In13th International Workshop on Resilient Networks Design and Modeling (RNDM), pages 1–8, 2023.do...

    work page doi:10.1109/rndm59149.2023.10293051 2003

  6. [6]

    42 Jack Robertson and William Webb.Cake-Cutting Algorithms: Be Fair if You Can

    doi: 10.1007/BF00288964. 42 Jack Robertson and William Webb.Cake-Cutting Algorithms: Be Fair if You Can. A. K. Peters, 1998.doi:10.1201/9781439863855. 43 John Michael Robson.N by N checkers is EXPTIME-complete.SIAM Journal on Computing, 13(2):252–267, 1984.doi:10.1137/0213018. 44 Vladislav Rutenburg. Complexity of generalized graph coloring. In12th Sympos...

    work page doi:10.1007/bf00288964 1998

  7. [7]

    49 Thomas J

    URL:https://ovid.cs.depaul.edu/documents/phcom.pdf. 49 Thomas J. Schaefer. On the complexity of some two-person perfect-information games.Journal of Computer and System Sciences, 16(2):185–225, 1978.doi:10.1016/0022-0000(78)90045-4. 50 Rodney Sebopelo and Bassey Isong. An integrated framework for controllers placement and security in software-defined netw...

    work page doi:10.1016/0022-0000(78)90045-4 1978

  8. [8]

    52Hugo Steinhaus

    doi:10.1002/nem.2018. 52Hugo Steinhaus. The problem of fair division.Econometrica, 16:101–104,

    work page doi:10.1002/nem.2018 2018

  9. [9]

    Stockmeyer

    53 Larry J. Stockmeyer. The polynomial-time hierarchy.Theoretical Computer Science, 3(1):1–22, 1976.doi:10.1016/0304-3975(76)90061-X. 54 Walter Stromquist. Envy-free cake divisions cannot be found by finite protocols.The Electronic Journal of Combinatorics, 15(1):#R11, 2008.doi:10.37236/735. 55 Warut Suksompong. Constraints in fair division.ACM SIGecom Ex...

    work page doi:10.1016/0304-3975(76)90061-x 1976

  10. [10]

    56 Ehsan Tohidi, Saeedeh Parsaeefard, Mohammad Ali Maddah-Ali, Babak Hossein Khalaj, and Alberto Leon-Garcia

    doi:10.1145/3505156.3505162. 56 Ehsan Tohidi, Saeedeh Parsaeefard, Mohammad Ali Maddah-Ali, Babak Hossein Khalaj, and Alberto Leon-Garcia. Near-optimal robust virtual controller placement in 5G software defined networks.IEEE Transactions on Network Science and Engineering, 8(2):1687–1697,

    work page doi:10.1145/3505156.3505162

  11. [11]

    57 Artur Tomaszewski, Michał Pióro, and Mariusz Mycek

    doi:10.1109/TNSE.2021.3068975. 57 Artur Tomaszewski, Michał Pióro, and Mariusz Mycek. Max-min optimization of controller placements vs. min-max optimization of attacks on nodes in service networks. In10th 18 The Complexity of Some Graph Division Games International Network Optimization Conference (INOC), pages 69–74, 2022.doi:10.48786/ inoc.2022.13. 58 So...

    work page doi:10.1109/tnse.2021.3068975 2021

  12. [12]

    doi:10.1109/LCOMM.2014.2332341

    work page doi:10.1109/lcomm.2014.2332341 2014