Minimum-Risk Maximum Clique Problem

In this work, we consider the minimum-risk maximum clique problem on stochastic graphs. Namely, assuming that each vertex of the graph is associated with a random variable describing a cost or a loss, such that the joint distribution of all variables on the graph is known, the goal is to determine a clique in the graph that has the lowest risk, given a specific risk measure. It is shown that in the developed problem formulation, minimization of risk is facilitated through inclusion of additional vertices in the partial solution, whereby an optimal solution represents a maximal clique in the graph. In particular, two instances of risk-averse maximum clique problems are considered, where risk exposures of a graph's vertices are "isolated" (i.e., not dependent on risk profiles of other vertices) and "neighbor-dependent," or dependent on the risk profiles of adjacent vertices. Numerical experiments on randomly generated Erdos-Renyi demonstrating properties of optimal risk-averse maximum cliques are conducted.