Descomponiendo una función submodular

Dada una función submodular on donde y son disjuntos . Aquí y son submodulares en y respectivamente.Ω = X 1 ∪ X 2 X 1 X 2 f ( S ) = f 1 ( S ∩ X 1 ) + f 2 ( S ∩ X 2 ) f 1 f 2 X 1 X $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$

Aquí son desconocidos y solo se proporciona un acceso de consulta de valor a . Entonces hay un algoritmo de polytime que encuentra . Si hay varias opciones para cualquiera de ellas debería estar bien. f X 1 X $X_1,X_2,f_1,f_2$$f$$X_1$$X_1$

Algunos pensamientos. Si podemos encontrar dos elementos modo que ambos pertenezcan a X 1 o pertenezcan a X 2, entonces podemos fusionarlos y proceder recursivamente. Pero no está claro cómo implementar tal paso.$t_1,t_2$$X_1$$X_2$

Tome un elemento arbitrario . Si f ( e ) = f Ω - e ( e ) entonces e no se ve afectado por el resto de los elementos, por lo que podemos elegir X 1 = { e } y X 2 = Ω - { e } . De lo contrario, dejemos que X sea ​​un subconjunto mínimo de inclusión de Ω - e tal que f ( e ) > f $e \in \Omega$$f(e) = f_{\Omega-e}(e)$$e$$X_1 = \{e\}$$X_2 = \Omega-\{e\}$$X$$\Omega-e$ . Entonces X ∪ { e } debe estar en la misma partición. Si X ∪ { e } = Ω llegamos a la conclusión de que no hay una partición deseada, de lo contrario, reducimos este conjunto en un solo elemento y recurrimos.$f(e) > f_X(e)$$X \cup \{e\}$$X \cup \{e\} = \Omega$