  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.
