论文标题
精确的电容统治：关于唯一性的计算复杂性
Exact capacitated domination: on the computational complexity of uniqueness
论文作者
论文摘要
在本文中，我们考虑了从算法的角度来考虑当地的服务提取分配问题，名为精确的电容统治。这个问题旨在为公共商品提供的游戏理论模型找到解决方案（NASH平衡）。在问题中，我们给出了一个电容图，该图在每个顶点上定义的参数，该图被解释为该顶点的容量。目的是找到一个DP-NASH子图：分别称为D和P的跨越两分子图，称为D-set和p集，因此P中没有PERTEX隔离，并且D中的每个顶点与d中的每个顶点都与许多与其容量相等的角度相邻。我们表明，电容图是否具有独特的DP-NASH子图，可以在多项式时间内确定。但是，我们还表明，确定电容图是否具有唯一的D-SET的问题是Co-NP完整的问题。
In this paper we consider a local service-requirement assignment problem named exact capacitated domination from an algorithmic point of view. This problem aims to find a solution (a Nash equilibrium) to a game-theoretic model of public good provision. 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 nearby problem of deciding whether a capacitated graph has a unique D-set is co-NP-complete.
