Мне нужно сокращение от «Restricted-3-partition» до «k-graph-partition», которое можно сделать за полиномиальное время, но я абсолютно не представляю, как это начать. Может ли кто-нибудь помочь мне с подходом?
Определение с ограничением на 3 раздела:
Вы получаете набор из n = 3k целых чисел a1, ..., a и значения A, так что A / 4
К графическому разделению объясняется здесь .