The MaxIS-Shapley Value in Perfect Graphs

We investigate the application of the Shapley value to quantifying the contribution of vertices to the maximum independent set (MaxIS) in perfect graphs. The MaxIS problem in perfect graphs can be computed in polynomial time. Many well-studied families of graphs are perfect, for example, bipartite graphs, chordal graphs, forests, etc. The Shapley value is a widely known numerical measure for assessing the contribution of individuals. We study this measure in the context of MaxIS by redefining corresponding concepts. We show that computing the Shapley value with respect to MaxIS in perfect graphs, bipartite graphs, line graphs of bipartite graphs, chordal graphs is #P-complete. We present parameterized algorithm and polynomial-time algorithm for some special cases: perfect graphs whose vertices have a small number of types, and graphs with maximum degree two. We also propose a fully polynomial-time randomized approximation scheme (FPRAS) for general perfect graphs.