Complexity of inheritance of $\mathcal{F}$-convexity for restricted games induced by minimum partitions

Abstract

Let $G=(N,E,w)$ be a weighted communication graph (with weight function $w$ on $E$). For every subset $A\subseteq N$, we delete in the subset $E(A)$ of edges with ends in $A$, all edges of minimum weight in $E(A)$. Then the connected components of the corresponding induced subgraph constitute a partition of $A$ that we call $P_{\min }(A)$. For every game $(N,v)$, we define the $P_{\min }$-restricted game $(N,\bar{v})$ by $\bar{v}(A)={\sum }_{F\in P_{\min }(A)}v(F)$ for all $A\subseteq N$. We prove that we can decide in polynomial time if there is inheritance of $\mathcal{F}$-convexity from $(N,v)$ to the $P_{\min }$-restricted game $(N,\bar{v})$ where $\mathcal{F}$-convexity is obtained by restricting convexity to connected subsets.