Article,
Exact capacitated domination: On the computational complexity of uniqueness
Affiliations
- [1] Royal Holloway University of London [NORA names: United Kingdom; Europe, Non-EU; OECD];
- [2] University of Johannesburg [NORA names: South Africa; Africa];
- [3] University of Southern Denmark [NORA names: SDU University of Southern Denmark; University; Denmark; Europe, EU; Nordic; OECD]
Abstract
Gerke et al. (2019) introduced a game-theoretic model to study public good provision in social networks when there are constraints on sharing. This model generates a purely graph-theoretic problem termed exact capacitated domination. In the problem we are given a capacitated graph, a graph with a parameter defined on each vertex that is interpreted as the capacity of that vertex. The objective is to find a D P -Nash subgraph: a spanning bipartite subgraph with partite sets D and P , called the D -set and P -set respectively, such that no vertex in P is isolated and that each vertex in D is adjacent to a number of vertices equal to its capacity. We show that whether a capacitated graph has a unique D P -Nash subgraph can be decided in polynomial time. However, we also show that the closely related problem of deciding whether a capacitated graph has a unique D -set is co-NP-complete.