论文标题
定期路径查询的沙普利值的复杂性
The Complexity of the Shapley Value for Regular Path Queries
论文作者
论文摘要
路径查询根据连接顶点的路径形成的单词从标记的图中提取顶点元组。我们研究了测量边缘和顶点对路径查询的答案的贡献的计算复杂性，重点介绍了连接性的常规路径查询类别。为了衡量这一贡献，我们采用了合作游戏理论的传统沙普利价值。该值最近在关系数据库查询的背景下进行了研究，并在其他众多域中使用。 我们首先研究边缘的贡献，并表明确切的沙普利价值几乎总是很难计算。具体而言，每当至少一个（非冗余）结合允许三个或更多的单词时，计算边缘的贡献是＃p-hard。在常规路径查询（即无连词）的情况下，如果查询最多只有两个词，则问题是可以解决的。因此，此属性充分表征了问题的障碍。另一方面，如果我们允许近似误差，那么获得有效的方案（FPRAS）对于加法近似是很简单的。然而，很难获得乘法近似。我们确定在结合定期路径查询的情况下，当且仅当所有查询原子都是有限语言时（假设非划分和常规复杂性限制）时，可以在多项式时间内计算边缘的shapley值的乘法近似。我们还研究了希望确定顶点而不是边缘的贡献并确定类似性质的复杂性结果的类似情况。
A path query extracts vertex tuples from a labeled graph, based on the words that are formed by the paths connecting the vertices. We study the computational complexity of measuring the contribution of edges and vertices to an answer to a path query, focusing on the class of conjunctive regular path queries. To measure this contribution, we adopt the traditional Shapley value from cooperative game theory. This value has been recently proposed and studied in the context of relational database queries and has uses in a plethora of other domains. We first study the contribution of edges and show that the exact Shapley value is almost always hard to compute. Specifically, it is #P-hard to calculate the contribution of an edge whenever at least one (non-redundant) conjunct allows for a word of length three or more. In the case of regular path queries (i.e., no conjunction), the problem is tractable if the query has only words of length at most two; hence, this property fully characterizes the tractability of the problem. On the other hand, if we allow for an approximation error, then it is straightforward to obtain an efficient scheme (FPRAS) for an additive approximation. Yet, a multiplicative approximation is harder to obtain. We establish that in the case of conjunctive regular path queries, a multiplicative approximation of the Shapley value of an edge can be computed in polynomial time if and only if all query atoms are finite languages (assuming non-redundancy and conventional complexity limitations). We also study the analogous situation where we wish to determine the contribution of a vertex, rather than an edge, and establish complexity results of similar nature.
