Quantifying the contribution of database facts to query answers has been studied as means
of explanation. The Banzhaf value, originally developed in Game Theory, is a natural …

We determine the computational complexity of approximately counting and sampling
independent sets of a given size in bounded-degree graphs. That is, we identify a critical …

Given a graph property Φ, the problem \#\scIndSub(Φ) asks, on input of a graph G and a
positive integer k, to compute the number IndSub(Φ,k→G) of induced subgraphs of size k in …

Hedonic games model cooperative games where agents desire to form coalitions, and only
care about the composition of the coalitions of which they are members. Focusing on various …

In this paper we show that for any graph H of order m and any graph G of order n and
maximum degree Δ Δ one can compute the number of subsets S of V (G) that induces a …

In the stable marriage (SM) problem, there are two sets of agents—traditionally referred to as
men and women—and each agent has a preference list that ranks (a subset of) agents of the …

We study the problems of counting copies and induced copies of a small pattern graph in a
large host graph. Recent work fully classified the complexity of those problems according to …

We show that the number of independent sets in cocomparability graphs can be counted in
linear time, as can counting cliques in comparability graphs. By contrast, counting cliques in …

We consider the task of constructing a cost-effective daily flight schedule with a minimum
number of required aircrafts and a maximum number of balanced flight routes, namely …

We define a theory of parameterized algebraic complexity classes in analogy to
parameterized Boolean counting classes. We define the classes VFPT and VW [t], which …