гипотеза GNRS

Нерешенная задача по математике :

Имеют ли семейства минорно-замкнутых графов вложения с ограниченным искажением? ${\displaystyle \ell _{1}}$

(еще нерешенные проблемы по математике)

В теоретической информатике и метрической геометрии гипотеза GNRS связывает теорию миноров графа , фактор растяжения вложений и отношение аппроксимации задач многопродуктового потока . Она названа в честь Анупама Гупты, Илана Ньюмана, Юрия Рабиновича и Алистера Синклера , которые сформулировали ее в 2004 году. ^[1]

Формулировка

Одна из формулировок гипотезы включает вложения кратчайших расстояний пути взвешенных неориентированных графов в пространства , реальные векторные пространства , в которых расстояние между двумя векторами равно сумме их разностей координат. Если вложение отображает все пары вершин с расстоянием в пары векторов с расстоянием в диапазоне , то его коэффициент растяжения или искажение равно отношению ; изометрия имеет коэффициент растяжения один, а все другие вложения имеют больший коэффициент растяжения. ^[1] ${\displaystyle \ell _{1}}$ ${\displaystyle d}$ ${\displaystyle [cd,Cd]}$ ${\displaystyle C/c}$

Графы, имеющие вложение с не более чем заданным искажением, замкнуты относительно операций миноров графа , операций, которые удаляют вершины или ребра из графа или сжимают некоторые из его ребер. Гипотеза GNRS утверждает, что, наоборот, каждое замкнутое по минорам семейство графов, кроме семейства всех графов, может быть вложено в пространство с ограниченным искажением. То есть искажение графов в семействе ограничено константой, которая зависит от семейства, но не от отдельных графов. Например, планарные графы замкнуты относительно миноров. Следовательно, из гипотезы GNRS следует, что планарные графы имеют ограниченное искажение. ^[1] ${\displaystyle \ell _{1}}$

Альтернативная формулировка включает аналоги теоремы о максимальном потоке и минимальном разрезе для ненаправленных задач многопродуктового потока . Отношение максимального потока к минимальному разрезу в таких задачах известно как разрыв потока-разреза . Наибольший разрыв потока-разреза, который может иметь задача потока на данном графе, равен искажению оптимального вложения графа. ^{[2] [3]} Таким образом, гипотезу GNRS можно перефразировать как утверждение, что замкнутые по минору семейства графов имеют ограниченный разрыв потока-разреза. ^[1] ${\displaystyle \ell _{1}}$

Связанные результаты

Произвольные -вершинные графы (на самом деле, произвольные -точечные метрические пространства ) имеют вложения с искажением . ^[4] Некоторые графы имеют логарифмический разрыв потока-разреза, и в частности это верно для многопродуктового потока с каждой парой вершин, имеющих равный спрос на графе- расширителе ограниченной степени . ^[5] Следовательно, эта логарифмическая граница искажения произвольных графов является жесткой. Плоские графы могут быть вложены с меньшим искажением, . ^[6] ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle \ell _{1}}$ ${\displaystyle O(\log n)}$ ${\displaystyle O({\sqrt {\log n}})}$

Хотя гипотеза GNRS остается нерешенной, было доказано, что для некоторых семейств графов с замкнутыми минорами существуют вложения с ограниченным искажением. К ним относятся последовательно-параллельные графы и графы с ограниченным рангом цепи , ^[1] графы с ограниченной шириной пути , ^[7] 2 -кликовые суммы графов с ограниченным размером, ^[8] и -внешнепланарные графы . ^[9] ${\displaystyle k}$

В отличие от поведения метрических вложений в пространства, каждое конечное метрическое пространство имеет вложения с растяжением, сколь угодно близким к единице по лемме Джонсона–Линденштрауса , и в пространства с растяжением, ровно одно по конструкции плотного охвата . ${\displaystyle \ell _{1}}$ ${\displaystyle \ell _{2}}$ ${\displaystyle \ell _{\infty }}$

Смотрите также

• Частичный куб , класс графов с невзвешенными -вложениями без искажений ${\displaystyle \ell _{1}}$

Ссылки

1. Гупта, Анупам; Ньюман, Илан; Рабинович Юрий; Синклер, Алистер (2004), «Разрезы, деревья и вложения графов», Combinatorica , 24 (2): 233–269, doi : 10.1007/s00493-004-0015-x, MR  2071334 ${\displaystyle \ell _{1}}$
2. Авис, Дэвид ; Деза, Мишель (1991), «Усеченный конус, встраиваемость, сложность и многопродуктовые потоки», Networks , 21 (6): 595–617, doi :10.1002/net.3230210602, MR  1128272 ${\displaystyle L^{1}}$
3. Линиал, Натан ; Лондон, Эран; Рабинович, Юрий (1995), «Геометрия графов и некоторые ее алгоритмические приложения», Combinatorica , 15 (2): 215–245, doi :10.1007/BF01200757, MR  1337355
4. Бургейн, Дж. (1985), «О липшицевом вложении конечных метрических пространств в гильбертово пространство», Israel Journal of Mathematics , 52 (1–2): 46–52, doi :10.1007/BF02776078, MR  0815600
5. Лейтон, Том ; Рао, Сатиш (1999), «Многопродуктовые теоремы о максимальном потоке и минимальном разрезе и их использование при проектировании алгоритмов аппроксимации», Журнал ACM , 46 (6): 787–832, doi : 10.1145/331524.331526 , MR  1753034
6. Рао, Сатиш (1999), «Вложения с малым искажением и сохранением объема для плоских и евклидовых метрик», Труды пятнадцатого ежегодного симпозиума по вычислительной геометрии (SoCG '99) , Нью-Йорк: ACM, стр. 300–306, doi : 10.1145/304893.304983 , ISBN 1-58113-068-6, г-н  1802217
7. Ли, Джеймс Р.; Сидиропулос, Анастасиос (2013), «Ширина пути, деревья и случайные вложения», Combinatorica , 33 (3): 349–374, arXiv : 0910.1409 , doi : 10.1007/s00493-013-2685-8, MR  3144806
8. Ли, Джеймс Р.; Пур, Дэниел Э. (2013), «О гипотезе вложения 2-сумм», Труды Двадцать девятого ежегодного симпозиума по вычислительной геометрии (SoCG '13) , Нью-Йорк: ACM, стр. 197–206, doi :10.1145/2462356.2492436, ISBN 978-1-4503-2031-3, МР  3208212
9. Чекури, Чандра; Гупта, Анупам; Ньюман, Илан; Рабинович Юрий; Синклер, Алистер (2006), «Вложение внешнепланарных графов в », SIAM Journal on Discrete Mathematics , 20 (1): 119–136, doi : 10.1137/S0895480102417379, MR  2257250 ${\displaystyle k}$ ${\displaystyle \ell _{1}}$