The Taub Faculty of Computer Science Events and Talks

A path query extracts from the input graph the pairs of vertices that constitute the endpoints of matching paths, that is, paths such that the word obtained from the edge labels belongs to a specified language. We study the computational complexity of measuring the contribution of edges and vertices to an answer of a path query. For that, we adopt the traditional Shapley value from cooperative game theory. This value has recently been suggested and studied as a standard contribution measure for database queries, machine-learning classifiers, and so on. We start by showing that the exact Shapley value is almost always hard to compute. For example, we show that (under conventional complexity assumptions) the Shapley value of an edge can be computed in polynomial time if and only if the path language has only words of length at most two. On the other hand, 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 a regular language, a multiplicative approximation of the Shapley value of an edge can be computed in polynomial time if and only if the path language is finite.