Параметризованная сложность подсчета бикликов

9

В предыдущем вопросе « Параметризованный алгоритм поиска бикликов» я поинтересовался, существуют ли быстрые параметризованные алгоритмы для нахождения -биклика в графе вершин, и узнал, что он открыт, если он равен FPT относительно . То же самое верно и для подсчета в -bicliques, или известно , что это # -Жесткий WRT (или какой -либо другой понятие твердости)?К×КNКК×КW\ [1\]К

Я знаю, что подсчет индуцированных -биклик является жестким # , расширяя простое сокращение для нахождения индуцированного biclique в разделе 4.5 в диссертации Сержа Гасперса .К×КW\ [1\]

Андреас Бьёрклунд
источник

Ответы:

9

Это должно быть #W [1] -hard по стандартному аргументу интерполяции. Вот примерный набросок.

Сначала рассмотрим многоцветную версию задачи о биклике: для данного графа, набор вершин которого разбит на классы , найдите биклик, содержащий ровно одну вершину из каждого набора. В отличие от Biclique, чей статус FPT открыт, эта многоцветная версия известна как W [1] -hard: есть легкое сокращение от клика. Я считаю, что это также должно быть #W [1] -hard.Икс1,...,Икс2К

Для данного графа и разбиения, как указано выше, давайте получим новый граф , заменив каждую вершину независимым набором размера (и заменив каждое ребро между и на biclique). Теперь число биклик в является функцией от переменных . На самом деле, можно видеть, что эта функция является полиномом степени не более а коэффициент члена точно равен количеству разноцветных биклик вгг'ИксяИксяИксяИксJИкся×ИксJК×Кг'2КИкс1,...,Икс2К2КИкс1Икс2Кг . Таким образом, подставляя достаточно много комбинаций значений в переменные и подсчитывая количество биклик в , мы можем оценить этот многочлен в достаточном количестве мест, чтобы восстановить его коэффициенты путем интерполяции.Иксяг'

Даниэль Маркс
источник
Спасибо Даниэль, это имеет смысл! Я также только что обнаружил, что Марк Терли доказывает это #A [1] -hard crm.cat/mthurley/theses/diploma.pdf
Андреас Бьёрклунд,
И экономное сокращение от Кот клика до разноцветного К×К-biclique находится в Приложении B на pages.cs.wisc.edu/~holger/papers/dm12soda.pdf
Андреас Бьёрклунд,