сложность аппроксимации хроматического числа в графах с ограниченной степенью

12

Я ищу результаты твердости по раскраске вершин графов с ограниченной степенью.

Учитывая граф , мы знаем, что для любого трудно приблизить с множителем если [ 1 ]. Но что, если максимальная степень ограничена ? Существуют ли в этом случае коэффициенты твердости вида (для некоторых )? $G(V,E)$ $\epsilon>0$ $\chi(G)$ $|V|^{1-\epsilon}$ $\textit{NP}=\textit{ZPP}$ $G$ $d$ $d^{1-\epsilon}$ $\epsilon$

Более простой вопрос: трудность аппроксимации числа хроматографических ребер гиперграфа, когда размер их ребер ограничен . Можем ли мы надеяться на соотношение твердости в этом случае? (скажем, для любого ) $d$ $d^{1-\epsilon}$ $\epsilon >0$

Спасибо за внимание!

cc.complexity-theory approximation-hardness graph-colouring hypergraphs bounded-degree afshi7n
источник

3

Вы можете дополнить жесткий экземпляр изолированными вершинами

Сашо Николов

2

Да, но если вы установите конечную границу размера жесткого экземпляра, с которого вы начинаете, он перестает быть жестким.

Дэвид Эппштейн

1

@Sasho Как могут помочь изолированные вершины, если они не увеличивают ни хроматическое число, ни максимальную степень?

afshi7n

2

@DavidEppstein уверен, что этот отступ доказывает только то, что

и

все еще полиномиально связаны. ОП, в этом-то и дело. Вы начинаете с экземпляра с

вершинами (максимальная степень не более

), для которого трудно приблизить

с точностью до

. добавить

изолированных вершин.

остается прежним, а максимальная степень остается

. это множитель, если

. так для любого целого числа

n

$n$

d

$d$

d

$d$

d

$d$

χ

$\chi$

d^{1 - ϵ}

$d^{1-\epsilon}$

n - d

$n - d$

χ

$\chi$

d

$d$

N = d^{O (1)}

$N = d^{O(1)}$

k

$k$ , существуют случаи с максимальной степенью

для которых трудно приблизить

с точностью до

d = n^{1 / k}

$d = n^{1/k}$

χ

$\chi$

d^{1 - ϵ}

$d^{1-\epsilon}$

Сашо Николов

Обновление: NP-трудно приблизить

с коэффициентом

без каких-либо дополнительных предположений.

χ (G)

$\chi(G)$

| V |^{1 - ϵ}

$|V|^{1-\epsilon}$

Кириак Антоний

9

Как указывал Дэвид, в статье Хота «Результаты улучшенной неприемлемости для MaxClique, хроматического числа и приблизительной окраски графа», теорема 1.6, говорится, что NP-трудно окрашивать раскрашиваемый граф с цветами для графики со степенью не более , при достаточно большой постоянной . Другими словами, для графиков степени трудно раскрасить $K$ $2^{\Omega((\log K)^2)}$ $2^{2^{(\log K)^2}}$ $K$ $d$ -цветный график сцветов. $2^{\sqrt{\log\log d}}$ $\log d$

Чтобы получить лучшую оценку степени, вы, вероятно, можете использовать идеи из статьи Тревизана «Результаты не аппроксимируемости для задач оптимизации в случаях ограниченной степени». Ключевое наблюдение заключается в том, что график, полученный в результате редукции FGLSS, представляет собой объединение полных двудольных подграфов, и каждый из них можно заменить двудольным диспергатором, который намного более редок. Подобная идея используется во многих результатах, таких как Чан http://eccc.hpi-web.de/report/2012/110/ , Теорема 1.4 / Приложение D.

Я думаю, что это должно дать вам что-то вроде за $2^{\sqrt{c\log d}}$ $d$ $d^{c}$ $0<c<1$

Граница степени в упомянутой Майклом статье похожа на степень Хота, а именно на экспоненту обоснованности. Конечно, вышеупомянутый подход к спарсификации также улучшает это, но, вероятно, не даст лучшей константы для вашей цели.

sangxia
источник

2^{Ω (\log \log d)}

$2^{\Omega(\log \log d)}$

2^{2^{Ω (\sqrt{\log \log d})}}

$2^{2^{\Omega(\sqrt{\log \log d})}}$

\log d / 2^{\sqrt{\log \log d}}

$\log d / 2^{\sqrt{\log \log d}}$

\log d / (\log \log d)^{3}

$\log d / (\log\log d)^3$

d^{c}

$d^c$

d

$d$

1

d^{c}

$d^c$

8

$3$

$\Delta$ $3$ $\Delta$ $4$

VB Le
источник

8

Существует результат неприемлемости для раскраски графов с ограниченными степенями в документе Khot's FOCS'01 «Улучшенные результаты неприемлемости для MaxClique, хроматического числа и окраски приближенного графика» - он, вероятно, слабее, чем вы хотите, но, по крайней мере, в правильном направлении.

$k$ $k$ $2^{k^{O(\log k)}}$ $\exp((\log k)^2/25)$ $d$ $O(\log d)$

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

\log d

$\log d$

Почему бы не спросить Хот?

Чандра Чекури

1

@chandra Только что отправил электронное письмо и спросил его, спасибо за предложение! Я буду обновлять здесь, если я услышал в ответ.

afshi7n

k^{\log k / 25}

$k^{\log k/25}$

\exp ((k \log k) / 25)

$\exp((k\log k)/25)$

2^{k^{1 / 3}}

$2^{k^{1/3}}$

k^{(\log k) / 25}

$k^{(\log k)/25}$

\exp ((k \log k) / 25)

$\exp((k\log k)/25)$

4

Этот результат может быть полезным:

$\Delta$ $k=$ $\Delta - \sqrt\Delta +1$ $k\ge 3$

Т. Эмден-Вейнерт, С. Хугарди, Б. Крейтер, Одноцветные графы и графы твердости раскраски большого обхвата, Комбин. Вероятно. Вычи. 7 (4) (1998) 375–386

Мухаммед Аль-Туркистани
источник

сложность аппроксимации хроматического числа в графах с ограниченной степенью

Ответы: