Влияние роста упаковочного числа графов на сложность задачи о независимом множестве

В статье изучается влияние предельного роста упаковочного числа графов (как функции от числа вершин) на сложностной статус задачи о независимом множестве. Доказывается, что при некоторых естественных предположениях эта задача полиномиально разрешима тогда и только тогда, когда упаковочное число растет по порядку не быстрее логарифма числа вершин.
Работа выполнена при поддержке РФФИ, коды проектов 10-01-00357-a, 11-01-00107-а и 12-01-00749-а, и ФЦП “Научные и научно-педагогические кадры инновационной России на 2009-2012 гг.” (номера ГК 16.740.11.0310 и 14.В37.21.0393), лаборатории алгоритмов и технологий анализа сетевых структур НИУ ВШЭ, грант правительства РФ, дог. 11.G34.31.0057.