Décomposition d'une fonction sous-modulaire

Soit une fonction sous-modulaire sur Ω = X 1 ∪ X 2 où X 1 et X 2 sont disjoints et f ( S ) = f 1 ( S ∩ X 1 ) + f 2 ( S ∩ X 2 ) . Ici f 1 et f 2 sont sous-modulaires sur X 1 et X 2 respectivement.$f$$\Omega=X_1\cup X_2$$X_1$$X_2$$f(S)=f_1(S\cap X_1)+f_2(S\cap X_2)$$f_1$$f_2$$X_1$$X_2$

Ici, sont inconnus et seul un accès de requête de valeur à f est donné. Ensuite, existe-t-il un algorithme de polytime qui trouve X 1 . S'il y a plusieurs choix pour X 1, l' un d'eux devrait convenir.$X_1,X_2,f_1,f_2$$f$$X_1$$X_1$

Quelques idées. Si nous pouvons trouver deux éléments tels que les deux appartiennent à X 1 ou appartiennent à X 2, alors nous pouvons les fusionner et procéder récursivement. Mais il n'est pas clair comment mettre en œuvre une telle étape.$t_1,t_2$$X_1$$X_2$

Prenons un élément arbitraire . Si f ( e ) = f Ω - e ( e ) alors e n'est pas affecté par le reste des éléments, nous pouvons donc choisir X 1 = { e } et X 2 = Ω - { e } . Sinon, soit X un sous-ensemble minimal de Ω - e inclus dans l'inclusion tel que f ( e ) > f $e \in \Omega$$f(e) = f_{\Omega-e}(e)$$e$$X_1 = \{e\}$$X_2 = \Omega-\{e\}$$X$$\Omega-e$ . Alors X ∪ { e } devrait être dans la même partition. Si X ∪ { e } = Ω, nous concluons qu'il n'y a pas de partition souhaitée, sinon nous réduisons cet ensemble en un seul élément et reconsidérons.$f(e) > f_X(e)$$X \cup \{e\}$$X \cup \{e\} = \Omega$