Самый большой общий подграф двух максимальных плоских графов

13

Рассмотрим следующую проблему -

С учетом максимальной плоских графов и G 2 , найти граф с максимальным числом ребер таким образом, что существует подграф (не обязательно индуцируется) в обоих и , изоморфная .G1G2GG1G2G

Можно ли это сделать за полиномиальное время? Если да, то как?

Известно, что если и являются общими графами, то проблема является NP-полной (потому что может быть кликой). Также известно, что если и являются деревьями или частичными k-деревьями ограниченной степени, то проблема может быть решена за полиномиальное время. Так что насчет максимального плоского случая? Кто-нибудь знает это? Изоморфизм графов на двух максимальных плоских графах является полиномиальным. Возможно, это как-то помогает?G1G2G1G1G2

Винаяк Патхак
источник
«Изоморфизм графов на двух максимальных плоских графах полиномиален. Возможно, это как-то помогает? По крайней мере, это связано (вы, вероятно, уже знаете это): наличие эффективного алгоритма для определения изоморфизма, безусловно, является необходимым условием существования эффективного алгоритма для нахождения наибольшего общего подграфа.
Цуёси Ито
Да, конечно. И этого, вероятно, недостаточно. Я не слишком уверен, но я думаю, что есть классы графов, для которых изоморфизм полиномиален, но найти самый большой общий подграф нет?
Винаяк Патхак
Кажется, проблема в неполном. G может быть наибольшим общим циклом, и известно, что задача о гамильтоновом цикле N P -полна на максимальных плоских графах. math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/W82a/tech298.pdfNPGNп
Мухаммед Аль-Тюркистани,

Ответы:

5

Он NP-полон, через модифицированную версию редукции, которую Вигдерсон использовал для доказательства того, что гамильтоновость максимальных плоских графов NP-полна.

Тщательное изучение NP-полноты доказательства твердости Вигдерсона в 1982 году для гамильтоновых циклов в максимальных плоских графах ( http://www.math.ias.edu/avi/node/820 ) показывает, что экземпляры, полученные в результате его редукции, обладают свойством существует ребро такое, что либо существует гамильтонов цикл через e, либо вообще не существует гамильтонов цикла. Например, e можно выбрать как один из ребер в одном из M- гаджетов Вигдерсона.еееM

граммграммееграммсЧАСNграмм

(ЧАС,В)ВЧАСсЧАСс2сЧАС

граммеграммс(N+2)с(N-1)3сграммс3сс(N-1)ЧАСВс(N+2)

Дэвид Эппштейн
источник