Exact capacitated domination: On the computational complexity of uniqueness

Gregory Z. Gutin*, Philip R. Neary, Anders Yeo

*Kontaktforfatter

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

10 Downloads (Pure)

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 DP-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 DP-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.

OriginalsprogEngelsk
TidsskriftDiscrete Applied Mathematics
Vol/bind332
Sider (fra-til)155-169
ISSN0166-218X
DOI
StatusUdgivet - 15. jun. 2023

Bibliografisk note

Funding Information:
Anders Yeo’s research was partially supported by grant DFF-7014-00037B of Independent Research Fund Denmark .

Publisher Copyright:
© 2023 The Author(s)

Fingeraftryk

Dyk ned i forskningsemnerne om 'Exact capacitated domination: On the computational complexity of uniqueness'. Sammen danner de et unikt fingeraftryk.

Citationsformater