Nondeterministic polynomial time (NP) and NP-completeness are by now widely familiar notions within the general computer science (CS) community. Every CS undergraduate knows many examples of NP-complete problems. In contrast, most computer science professors, if stopped on the street, could not name even a single, complete problem for the next level of the polynomial hierarchy, . ( is the class of languages that can be accepted by an NP machine allowed access to a unit-cost satisfiability subroutine.)
This state of affairs is unfortunate since pinpointing what class a problem is complete for is one central way that the flavor of the problem is revealed and its complexity understood. For example, at their core, NP-complete problems are about polynomially bounded ∃ quantification, and at their core, problems are about a polynomially bounded ∃ ∀ quantifier sequence. Although proving problems complete for levels of the polynomial hierarchy beyond NP (and coNP, the class of languages whose complements are in NP) is indeed often more difficult than proving problems complete for NP (and coNP), it might surprise most people to know that more than 80 natural problems have been classified as complete for higher levels of the polynomial hierarchy (see the compendium [1]).
This paper studies the problem of bribery in multiple-adversary path-disruption games. Very loosely put, this problem involves evaluating whether there exists a bribing action (the buying up of a number of priced nodes in a graph) with at most a certain cost such that one has precluded every possible coalition not involving the bribed nodes from appropriately disrupting the existence of paths between various source-target node pairs. A 2011 paper by two of this paper’s authors implied that this problem was NP-hard and also noted that it belongs to [2]. The interesting paper under review removes this uncertainty about the exact complexity classification of this problem by establishing that the problem is many-one polynomial-time complete for .