Каковы основные трудности перехода от графов к гиперграфам?

10

Есть много примеров в комбинаторике и информатике, где мы можем проанализировать теоретико-графическую проблему, но для ее гиперграфа у нас отсутствуют инструменты. Как вы думаете, почему проблемы с 3-равномерными гиперграфами часто становятся намного сложнее, чем с 2-равномерными графами? Каковы основные трудности?

Одна из проблем заключается в том, что у нас пока нет удовлетворительного понимания теории спектральных гиперграфов. Пожалуйста, не стесняйтесь пролить больше света на эту проблему. Но я также ищу другие причины, которые делают гиперграфы более сложными объектами.

Арнаб
источник
Интересно, в какой степени это связано с недавней дискуссией об изменении сложности геометрических задач, переходящих из 2D в 3D ( cstheory.stackexchange.com/questions/5251/… ). Причина, по которой я говорю это, заключается в том, что вы можете связать ребра в 2-равномерном графе с местоположениями на двумерной решетке, тогда как 3-равномерный гиперграф будет иметь гиперграницы, соответствующие местоположениям в 3d-решетке.
Джо Фицсимонс
@Joe Fitzsimons: хорошая мысль. Но концепции и методы, которые естественны для (гипер) графа, такие как подграфы, раскраски, разбиения и т. Д., Могут не быть такими естественными в геометрической обстановке. Кроме того, я согласен с вами в том, что во многих областях происходит переход "два-три".
Арнаб
2
Ваш вопрос сложный, поскольку удовлетворительный ответ решит проблему P против NP. Обратите внимание, что идеальное сопоставление легко для 2-равномерных графов, в то время как это трудно для 3-однородных гиперграфов.
Мухаммед Аль-Туркистани
Является ли гиперграф хорошо определенной концепцией? (Во-первых, этот сайт орфографии не знает об этом :-) Это отношение фиксированной или переменной арности?
Тегири Ненаши
Хорошо, после посещения Википедии, я вижу, что это на самом деле не отношение, а семейство наборов. Относится ли господствующая математика к этому понятию «гиперграфа» серьезно?
Тегири Ненаши

Ответы:

8

В этом вопросе я понимаю, что «сложность» относится не к «сложным вычислениям», а к «трудным для изучения».

Графические проблемы легче (по крайней мере для меня) изучить, поскольку некоторые концепции оказываются эквивалентными. Другими словами, если вы хотите обобщить вопросы для графиков на вопросы для гиперграфов, вам нужно обратить внимание на «правильное» обобщение, чтобы получить желаемое следствие.

Например, рассмотрим дерево. Для графов граф - это дерево, если он связан и не содержит циклов. Это эквивалентно соединению и наличию n-1 ребер (где n - количество вершин), а также эквивалентно отсутствию цикла и наличию n-1 ребер. Однако для 3-равномерных гиперграфов, скажем, 3-равномерный гиперграф является деревом, если он связан и не содержит циклов. Но это не эквивалентно соединению и наличию гиперчетов n-1, а также отсутствию цикла и наличию гипер-граней n-1.

Я слышал, что основная трудность доказательства леммы регулярности для равномерных гиперграфов состояла в том, чтобы придумать правильные определения регулярности и связанных понятий.

Если вы хотите рассмотреть «теорию спектральных гиперграфов», вы можете попытаться заглянуть в тензоры или в гомологии, если вы увидите k-равномерный гиперграф как (k-1) -мерный симплициальный комплекс, из которого естественным образом возникает линейная алгебра. Я не знаю, какое «правильное» обобщение для вашей цели, или возможно, что ни то, ни другое не верно.

Ёсио Окамото
источник
7

Я думаю, что это в значительной степени связано с «мистической силой двойственности» Лоулера (наблюдение, что многие параметризованные задачи находятся в P для param = 2 и NP-полные для param≥3). Граф - это вещь, которая соединяет 2 набора вершин, а гиперграф - это вещь, которая соединяет k наборов вершин для k≥3.

Так, например, 2-SAT находится в P и является по существу проблемой графа, тогда как 3-SAT является проблемой на 3-равномерных гиперграфах и является NP-полной.

Дэвид Эппштейн
источник
1
Чтобы быть более точным, я хотел спросить, можно ли определить некоторые фундаментальные причины, почему теоретико-графические методы не работают. Например, у нас на самом деле нет линейно-алгебраических методов для гиперграфов, потому что тензорный ранг не совсем понятен (например, его сложно вычислить с помощью NP).
Арнаб
1
Цель моего ответа была не столько в том, что «эти проблемы трудно решить компьютерам», а в том, что существует сильная корреляция между P / NPC и наличием / отсутствием хороших математических характеристик. Так что проблемы становятся сложнее изучать в тандеме с их становлением NPC.
Дэвид Эппштейн
7
В этом контексте недавно опубликованный вопрос cstheory.stackexchange.com/questions/14950/… довольно интересен: распознавание линейных графиков 2-гиперграфов, то есть линейных графиков (мульти) графов, находится в P, тогда как распознавание линейных графиков 3-гиперграфы кажутся открытой проблемой. Отметим также, что проблема характеризации 3-гиперграфов (запрещенными индуцированными подграфами) все еще остается открытой, в то время как линейные графы (мульти) графов допускают несколько таких характеризаций.
ВБ Ле
5

Другая причина состоит в том, что у нас гораздо больше знаний о бинарных отношениях, чем о любых других n-арных отношениях для n больше 2.

Естественно, мы рассматриваем бинарные отношения между объектами, такие как смежность, непустое пересечение, эквивалентность и т. Д. Таким образом, мы можем определить графы в терминах бинарных отношений и даже определить граф на основе некоторого бинарного отношения на другом графе. (Например, линейные графики, клики, разложения деревьев ...)

Но что касается других российских отношений, мы не очень понимаем. Например, требуется некоторое время, чтобы придумать интересное троичное соотношение; (Ладно, частично из-за моего невежества) свойства слабее, а инструменты гораздо меньше при изучении троичных отношений. (Как мы определяем симметричные или транзитивные троичные отношения? Оба они являются одними из самых важных отношений, которые можно изучить.)

Но все же я не знаю, почему это происходит между бинарными и троичными отношениями. Возможно, как сказала туркистанина, этот вопрос сложен и может быть связан с пониманием проблемы P / NP.

Сянь-Чжи Чан 張顯 之
источник
[Несмотря на цилиндрические и полиадические алгебры], для n-арных отношений не существует убедительной алгебры. Дискуссия может быть даже снижена до уровня, когда можно утверждать, что позиционная или именованная перспектива соотносятся с атрибутами отношений.
Тегири Ненаши
2

Сначала я собирался ответить на неправильный вопрос: «Какой пример проблем гораздо сложнее в гиперграфах, чем в графах». Я был особенно впечатлен различием в работе с проблемой максимального соответствия на графах, а также с гиперграфами (набором попарно непересекающихся ребер), которые очень легко могут моделировать раскраску, максимальное независимое множество, максимальное клик ...

Тогда я заметил, что это был не твой вопрос: «Каковы основные трудности между ними?».

Ну, на это я бы ответил, что до сих пор я не видел много общих точек между графиками и гиперграфами. За исключением самого названия. И то, что многие люди пытаются «распространить» результаты с первого на другое.

У меня была возможность пролистать страницы «Гиперграфов» Берге и «Систем множеств» Боллобаса: они содержат много вкусных результатов, и те, которые я нашел наиболее интересными, мало что могли сказать о графиках. Например, теорема Бараньи (в книге Юкны есть хорошее доказательство).

Я не знаю многих из них, но сейчас я думаю о проблеме с гиперграфами, и все, что я могу сказать по этому поводу, - это то, что я не чувствую, чтобы где-то вокруг скрывался график. Возможно, мы думаем о них как о «трудных», потому что мы просто пытаемся изучить их с помощью неправильных инструментов. Я не ожидаю, что проблемы с графами, над которыми я работаю, сразу исчезнут, если использовать теорию чисел (хотя иногда это случается).

Ох, и что-то еще. Возможно, им труднее учиться, потому что они комбинаторно намного ... больше ?!

«попробуй их все и посмотри, как это работает» - иногда хорошая идея для графиков, но с гиперграфами один быстро смиряется с числами. :-)

Натанн Коэн
источник