דלג לתוכן (מקש קיצור 's')
Logo of Technion
Logo of CS Department
אירועים

אירועים

The Complexity of the Shapley Value for Path Queries over Graphs
event speaker icon
מג'ד ח'ליל, הרצאה סמינריונית למגיסטר
event date icon
יום שני, 25.10.2021, 13:30
event location icon
Zoom Lecture: 95634964056
event speaker icon
מנחה:  Prof. Benny Kimelfeld
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.
[בחזרה לאינדקס האירועים]