Гипотеза расширения малого набора

Гипотеза о расширении малых множеств или гипотеза о расширении малых множеств в теории сложности вычислений является недоказанным предположением о вычислительной сложности . В соответствии с гипотезой расширения малого набора предполагается, что с вычислительной точки зрения невозможно отличить определенный класс графов-расширителей, называемый «расширителями малых множеств», от других графов, которые очень далеки от того, чтобы быть расширителями малых множеств. Это предположение подразумевает сложность ряда других вычислительных задач и оптимальность некоторых известных алгоритмов аппроксимации .

Гипотеза расширения малого набора связана с гипотезой уникальных игр , еще одним недоказанным предположением о вычислительной сложности, согласно которому точная аппроксимация ценности определенных игр вычислительно неосуществима. Если гипотеза о расширении малого множества верна, то верна и гипотеза об уникальных играх.

Фон

Расширение по краям множества $X$ вершин в графе $G$ определяется как ${\frac {|\partial X|}{|X|}},$ где вертикальные черточки обозначают количество элементов множества , а $\partial X$ обозначает множество ребер, которые имеют одну конечную точку в $X$ и другая конечная точка в ее дополнении. ^[а] Это число может быть даже нулевым, если $X$ является связной компонентой графа, так как в этом случае нет ребер, соединяющих $X$ в другие части графика. Граф называется регулярным или $d$ -регулярный, когда каждая вершина инцидентна одному и тому же числу ребер, $d$ , степень графа. Для $d$ -регулярный граф, максимально возможное расширение ребра равно $d$ . Это расширение достигается любым подмножеством $X$ что порождает , независимое множество так как в этом случае все ребра, соприкасающиеся с вершинами в $X$ принадлежать $\partial X$ . ^[1]^[2]

Реберное расширение графа с $n$ вершин определяется как минимальное расширение ребра среди его подмножеств не более $n/2$ вершины. ^[б] Вместо этого расширение малого набора определяется как тот же минимум, но только на меньшие подмножества, не более $n/\log _{2}n$ вершины. Неформально, небольшой расширитель множества — это граф, расширение малого множества которого велико. ^[1]^[с]

Заявление

Гипотеза расширения малого набора использует действительное число. $\varepsilon$ в качестве параметра для формализации того, что означает, что небольшое расширение графа является большим или маленьким. Он утверждает, что для каждого $\varepsilon >0$ , NP-трудно отличить $d$ -регулярные графы, по крайней мере, с небольшим расширением множества $(1-\varepsilon )d$ (хорошие небольшие эспандеры), и $d$ -регулярные графы с не более чем небольшим расширением множества $\varepsilon d$ (очень далеко не маленький комплект-расширитель). Здесь степень $d$ это переменная, которая может зависеть от выбора $\varepsilon$ , в отличие от многих приложений расширительных графов, где степень предполагается фиксированной константой. ^[1]^[с]

Последствия

Гипотеза расширения малого набора предполагает NP-трудность некоторых других вычислительных задач. Поскольку это всего лишь гипотеза, это не доказывает, что эти задачи на самом деле являются NP-сложными. Тем не менее, это предполагает, что было бы трудно найти эффективное решение этих проблем, поскольку решение любой из них также решило бы другие проблемы, решение которых до сих пор было неуловимым (включая саму проблему расширения малых множеств). С другой стороны, этот вывод открывает дверь для опровержения гипотезы расширения малых множеств, предлагая другие проблемы, с помощью которых ее можно было бы подвергнуть атаке. ^[1]

В частности, существует сокращение за полиномиальное время от распознавания малых расширителей множеств до проблемы определения приблизительной ценности уникальных игр, показывающее, что гипотеза расширения малых множеств подразумевает гипотезу уникальных игр . ^[1]^[2] Вооз Барак более решительно предположил, что эти две гипотезы эквивалентны. ^[1] Фактически, гипотеза расширения малого множества эквивалентна ограниченной форме гипотезы об уникальных играх, утверждая сложность экземпляров уникальных игр, базовыми графами которых являются расширители небольших множеств. ^[3] С другой стороны, можно быстро решить уникальные экземпляры игр, граф которых «достоверно» является небольшим расширителем множества в том смысле, что их расширение можно проверить с помощью оптимизации суммы квадратов . ^[4]

Другое применение гипотезы расширения малого множества касается вычислительной задачи аппроксимации ширины дерева графов, структурного параметра, тесно связанного с расширением. Для графиков ширины дерева $w$ , лучший коэффициент аппроксимации , известный для алгоритма аппроксимации с полиномиальным временем, равен $O({\sqrt {\log w}})$ . ^[5] Гипотеза о расширении малого множества, если она верна, означает, что не существует алгоритма аппроксимации для этой задачи с постоянным коэффициентом аппроксимации. ^[6] Его также можно использовать для обозначения неаппроксимируемости поиска полного двудольного графа с максимальным количеством ребер (возможно, ограниченным наличием одинакового количества вершин на каждой стороне его двудольного деления) в более крупном графе. ^[7]

Гипотеза расширения малого множества подразумевает оптимальность известных коэффициентов аппроксимации для определенных вариантов задачи покрытия ребер , в которой необходимо выбрать как можно меньше вершин, чтобы покрыть заданное количество ребер в графе. ^[8]

История и частичные результаты

Гипотеза расширения малых множеств была сформулирована и связана с гипотезой об уникальных играх Прасадом Рагхавендрой и Дэвидом Стерером в 2010 году. ^[2] в рамках работы, за которую им была вручена премия Майкла и Шейлы Хелд Национальной академии наук 2018 года . ^[9]

Один из подходов к разрешению гипотезы расширения малых множеств состоит в поиске аппроксимационных алгоритмов расширения ребер небольших наборов вершин, которые были бы достаточно хороши, чтобы различать два класса графов в гипотезе. В этом свете наилучшее известное приближение для разложения по краям подмножеств не более $n/\log n$ вершины в $d$ -регулярный граф, имеет коэффициент аппроксимации $O({\sqrt {\log n\log \log n}})$ . Это недостаточно сильно, чтобы опровергнуть гипотезу; для этого потребуется найти алгоритм с ограниченным коэффициентом аппроксимации. ^[10]

Примечания

^ Это определение соответствует обозначениям, используемым в статье о расширенном графике ; некоторые источники, такие как Raghavendra & Steurer (2010) , вместо этого нормализуют расширение ребра, разделив его на степень графа.
^ Это определение позволяет избежать использования подмножеств, количество вершин которых близко к $n$ , потому что эти подмножества будут иметь небольшое расширение даже в графах, которые в противном случае имеют большое расширение.
^ Перейти обратно: ^а ^б Эта формулировка принадлежит Бараку (2016) , который отмечает, что она исключает некоторые неважные параметры, появляющиеся в других формулировках той же гипотезы, например, в Рагхавендре и Стерере (2010) .

Ссылки

^ Перейти обратно: ^а ^б ^с ^д ^и ^ж Барак, Боаз (2016), «Лекция SOS 6: Подход SOS к опровержению пользовательского контента» (PDF) , конспекты лекций «Доказательства, убеждения и алгоритмы через призму суммы квадратов» , получено 14 марта 2023 г.
^ Перейти обратно: ^а ^б ^с Рагхавендра, Прасад; Стерер, Дэвид (2010), «Расширение графа и гипотеза уникальных игр», Шульман, Леонард Дж. (редактор), Труды 42-го симпозиума ACM по теории вычислений, STOC 2010, Кембридж, Массачусетс, США, 5– 8 июня 2010 г. (PDF) , Ассоциация вычислительной техники, стр. 755–764, doi : 10.1145/1806689.1806792 , S2CID 1601199
^ Рагхавендра, Прасад; Стойрер, Дэвид; Тулсиани, Мадхур (2012), «Редукция между проблемами расширения», Материалы 27-й конференции по вычислительной сложности, CCC 2012, Порту, Португалия, 26–29 июня 2012 г. , Компьютерное общество IEEE, стр. 64–73, arXiv : 1011.2586 , дои : 10.1109/CCC.2012.43
^ Бафна, Митали; Барак, Боаз ; Котари, Правеш К.; Шрамм, Целиль; Стойрер, Дэвид (2021), «Игра в уникальные игры на сертифицированных небольших расширителях», Хуллер, Самир ; Уильямс, Вирджиния Василевска (ред.), STOC '21: 53-й ежегодный симпозиум ACM SIGACT по теории вычислений, виртуальное мероприятие, Италия, 21–25 июня 2021 г. , Ассоциация вычислительной техники, стр. 1629–1642, arXiv : 2006.09969 , дои : 10.1145/3406325.3451099
^ Файги, Уриэль ; Хаджиагайи, Мохаммадтаги ; Ли, Джеймс Р. (2008), «Улучшенные алгоритмы аппроксимации для разделителей вершин минимального веса», SIAM Journal on Computing , 38 (2): 629–657, doi : 10.1137/05064299X , MR 2411037
^ Ву, Ю; Острин, Пер; Питасси, Тонианн ; Лю, Дэвид (2014), «Неприближаемость ширины деревьев, одноразовая галька и связанные с ними проблемы планировки», Журнал исследований искусственного интеллекта , 49 : 569–600, doi : 10.1613/jair.4030 , MR 3195329
^ Мануранси, Пасин (2018), «Неаппроксимируемость задач максимальной биклики, минимальный $k$ -разрез и самый плотный по крайней мере $k$ -подграф из гипотезы расширения малого множества», Алгоритмы , 11 (1): P10:1–P10:22, arXiv : 1705.03581 , doi : 10.3390/a11010010 , MR 3758880
^ Ганди, Раджив; Корцарц, Гай (2015), «О проблемах расширения множеств и гипотеза расширения малых множеств» (PDF) , Discrete Applied Mathematics , 194 : 93–101, doi : 10.1016/j.dam.2015.05.028 , MR 3391764
^ Премия Майкла и Шейлы 2018 года: Прасад Рагхавендра и Дэвид Стерер , Национальная академия наук , получено 23 ноября 2023 г.
^ Бансал, Нихил; Файги, Уриэль ; Краутгамер, Роберт; Макарычев Константин; Нагараджан, Вишванатх; Наор, Джозеф ; Шварц, Рой (2014), «Мин-максное разбиение графа и расширение небольшого набора» (PDF) , SIAM Journal on Computing , 43 (2): 872–904, doi : 10.1137/120873996 , MR 3504685

[1] Это определение соответствует обозначениям, используемым в статье о расширенном графике ; некоторые источники, такие как Raghavendra & Steurer (2010) , вместо этого нормализуют расширение ребра, разделив его на степень графа.

[4] Это определение позволяет избежать использования подмножеств, количество вершин которых близко к $n$ , потому что эти подмножества будут иметь небольшое расширение даже в графах, которые в противном случае имеют большое расширение.

[barak-5] Перейти обратно: ^а ^б Эта формулировка принадлежит Бараку (2016) , который отмечает, что она исключает некоторые неважные параметры, появляющиеся в других формулировках той же гипотезы, например, в Рагхавендре и Стерере (2010) .

[barak-2] Перейти обратно: ^а ^б ^с ^д ^и ^ж Барак, Боаз (2016), «Лекция SOS 6: Подход SOS к опровержению пользовательского контента» (PDF) , конспекты лекций «Доказательства, убеждения и алгоритмы через призму суммы квадратов» , получено 14 марта 2023 г.

[rs-3] Перейти обратно: ^а ^б ^с Рагхавендра, Прасад; Стерер, Дэвид (2010), «Расширение графа и гипотеза уникальных игр», Шульман, Леонард Дж. (редактор), Труды 42-го симпозиума ACM по теории вычислений, STOC 2010, Кембридж, Массачусетс, США, 5– 8 июня 2010 г. (PDF) , Ассоциация вычислительной техники, стр. 755–764, doi : 10.1145/1806689.1806792 , S2CID 1601199

[rst-6] Рагхавендра, Прасад; Стойрер, Дэвид; Тулсиани, Мадхур (2012), «Редукция между проблемами расширения», Материалы 27-й конференции по вычислительной сложности, CCC 2012, Порту, Португалия, 26–29 июня 2012 г. , Компьютерное общество IEEE, стр. 64–73, arXiv : 1011.2586 , дои : 10.1109/CCC.2012.43

[bbk-7] Бафна, Митали; Барак, Боаз ; Котари, Правеш К.; Шрамм, Целиль; Стойрер, Дэвид (2021), «Игра в уникальные игры на сертифицированных небольших расширителях», Хуллер, Самир ; Уильямс, Вирджиния Василевска (ред.), STOC '21: 53-й ежегодный симпозиум ACM SIGACT по теории вычислений, виртуальное мероприятие, Италия, 21–25 июня 2021 г. , Ассоциация вычислительной техники, стр. 1629–1642, arXiv : 2006.09969 , дои : 10.1145/3406325.3451099

[fhl-8] Файги, Уриэль ; Хаджиагайи, Мохаммадтаги ; Ли, Джеймс Р. (2008), «Улучшенные алгоритмы аппроксимации для разделителей вершин минимального веса», SIAM Journal on Computing , 38 (2): 629–657, doi : 10.1137/05064299X , MR 2411037

[wapl-9] Ву, Ю; Острин, Пер; Питасси, Тонианн ; Лю, Дэвид (2014), «Неприближаемость ширины деревьев, одноразовая галька и связанные с ними проблемы планировки», Журнал исследований искусственного интеллекта , 49 : 569–600, doi : 10.1613/jair.4030 , MR 3195329

[manurangsi-10] Мануранси, Пасин (2018), «Неаппроксимируемость задач максимальной биклики, минимальный $k$ -разрез и самый плотный по крайней мере $k$ -подграф из гипотезы расширения малого множества», Алгоритмы , 11 (1): P10:1–P10:22, arXiv : 1705.03581 , doi : 10.3390/a11010010 , MR 3758880

[gs-11] Ганди, Раджив; Корцарц, Гай (2015), «О проблемах расширения множеств и гипотеза расширения малых множеств» (PDF) , Discrete Applied Mathematics , 194 : 93–101, doi : 10.1016/j.dam.2015.05.028 , MR 3391764

[held-12] Премия Майкла и Шейлы 2018 года: Прасад Рагхавендра и Дэвид Стерер , Национальная академия наук , получено 23 ноября 2023 г.

[bfk-13] Бансал, Нихил; Файги, Уриэль ; Краутгамер, Роберт; Макарычев Константин; Нагараджан, Вишванатх; Наор, Джозеф ; Шварц, Рой (2014), «Мин-максное разбиение графа и расширение небольшого набора» (PDF) , SIAM Journal on Computing , 43 (2): 872–904, doi : 10.1137/120873996 , MR 3504685

[а]

[1]

[2]

[б]

[с]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]