Complexity of inheritance of ℱ-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 s u b s e t e q 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_{m i n} (A)

. For every game

(N, v)

, we define the

P_{m i n}

-restricted game

by

for all

A s u b s e t e q N

. We prove that we can decide in polynomial time if there is inheritance of

m a t h c a l F

-convexity from

(N, v)

to the

P_{m i n}

-restricted game

where

m a t h c a l F

-convexity is obtained by restricting convexity to connected subsets.