Изменения

Это подразумевает, что максимальное независимое множество в <tex> \mathcal{I} = \mathcal{I}_1 \cup \ldots \cup \mathcal{I}_k</tex> мы можем найти за полиномиальное время (жадно наращивать независимое множество в <tex>M = M_1 \cup \ldots \cup M_k</tex>). Cunningham<ref>Alexander Schrijver. Combinatorial Optimization. Polyhedra and Efficiency, Volume A-C, стр.732</ref> разработал алгоритм, которым за <tex>O((n^{(3/2)} + k)mQ + n^{(1/2)}km)</tex> можно найти максимальное независимое множество в <tex> \mathcal{I} = \mathcal{I}_1 \cup \ldots \cup \mathcal{I}_k</tex>, где <tex>n</tex> максимальный размер множества в <tex> \mathcal{I} = \mathcal{I}_1 \cup \ldots \cup \mathcal{I}_k</tex>, <tex>m</tex> размер подмножества и <tex>Q</tex> время, необходимое, чтобы определить принадлежит ли множество <tex> \mathcal{I}_j</tex> для каждого <tex>j</tex>. Более детальное объяснение алгоритма (но не время работы) можно найти в объяснении у C. Greene и T.L. Magnanti<ref>C. Greene, T.L. Magnanti, Some abstract pivot algorithms, SIAM Journal on Applied Mathematics, p.530-539</ref>.