kekerasan mendekati angka kromatik dalam grafik dengan derajat terikat

12

Saya mencari hasil kekerasan pada pewarnaan vertex grafik dengan derajat terikat.

Diberikan grafik , kita tahu bahwa untuk , sulit untuk mendekati dalam faktor kecuali [ 1 ]. Tetapi bagaimana jika tingkat maksimum dibatasi oleh ? Apakah ada rasio kekerasan dalam bentuk (untuk beberapa ) dalam kasus ini? $G(V,E)$ $\epsilon>0$ $\chi(G)$ $|V|^{1-\epsilon}$ $\textit{NP}=\textit{ZPP}$ $G$ $d$ $d^{1-\epsilon}$ $\epsilon$

Pertanyaan yang lebih mudah adalah: Kekerasan mendekati jumlah-kromatik-angka hypergraphs ketika ukuran tepi mereka dibatasi oleh . Bisakah kita berharap untuk rasio kekerasan dalam kasus ini? (katakanlah, untuk ) $d$ $d^{1-\epsilon}$ $\epsilon >0$

Terima kasih atas perhatian anda!

cc.complexity-theory approximation-hardness graph-colouring hypergraphs bounded-degree afshi7n
sumber

3

Anda dapat membuat contoh yang sulit dengan simpul terisolasi

Sasho Nikolov

2

Ya, tetapi jika Anda meletakkan batas yang terbatas pada ukuran instance keras yang Anda mulai, itu berhenti menjadi sulit.

David Eppstein

1

@ Sasho Bagaimana simpul terisolasi dapat membantu ketika mereka tidak meningkatkan nomor berwarna atau tingkat maksimum?

afshi7n

2

@ Davidvidppstein yakin, padding ini hanya membuktikan sesuatu jika

dan

masih berhubungan secara polinomi. OP, itu sebenarnya intinya. Anda mulai dengan sebuah contoh dengan

simpul (jadi max tingkat paling

) yang sulit untuk perkiraan

ke dalam

. tambahkan

simpul yang terisolasi.

tetap sama dan derajat maksimal tetap

. ini adalah polytime jika

. jadi untuk bilangan bulat apa pun

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$ , ada contoh dengan derajat maksimum

yang sulit diperkirakan

hingga dalam

d = n^{1 / k}

$d = n^{1/k}$

χ

$\chi$

d^{1 - ϵ}

$d^{1-\epsilon}$

Sasho Nikolov

Pembaruan: Ini NP-sulit untuk mendekati

dalam faktor

tanpa asumsi tambahan.

χ (G)

$\chi(G)$

| V |^{1 - ϵ}

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

Cyriac Antony

9

Seperti yang ditunjukkan David, makalah Khot, "Peningkatan Hasil yang Tidak Dapat Diperkirakan untuk MaxClique, Nomor Kromatik dan Perkiraan Grafik Berwarna", Teorema 1.6, mengatakan bahwa NP-sulit untuk mewarnai grafik -warna dengan warna untuk grafik dengan derajat paling banyak , untuk konstanta cukup besar . Dengan kata lain, untuk grafik derajat , sulit untuk mewarnai $K$ $2^{\Omega((\log K)^2)}$ $2^{2^{(\log K)^2}}$ $K$ $d$ -warna grafik denganwarna. $2^{\sqrt{\log\log d}}$ $\log d$

Untuk mendapatkan batas gelar yang lebih baik, Anda mungkin dapat menggunakan ide dari makalah Trevisan "Hasil yang tidak dapat diperkirakan untuk masalah optimisasi pada instance derajat terbatas". Pengamatan utama adalah bahwa grafik yang dihasilkan oleh pengurangan FGLSS adalah gabungan subgraph bipartit lengkap, dan seseorang dapat mengganti masing-masing dengan disperser bipartit yang jauh lebih jarang. Gagasan serupa digunakan dalam banyak hasil seperti Chan http://eccc.hpi-web.de/report/2012/110/ , Teorema 1.4 / Lampiran D.

Saya pikir ini harus memberi Anda sesuatu untuk $2^{\sqrt{c\log d}}$ $d$ $d^{c}$ $0<c<1$

Tingkat yang terikat dalam makalah yang disebutkan Michael mirip dengan Khot, yaitu eksponensial dari kasus kesehatan. Tentu saja pendekatan sparsifikasi di atas juga meningkatkan ini, tetapi mungkin tidak akan memberikan konstanta yang lebih baik untuk tujuan Anda.

sangxia
sumber

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
sumber

8

Ada hasil yang tidak dapat diperkirakan untuk mewarnai grafik derajat terbatas dalam makalah FOCS'01 Khot, "Peningkatan Hasil yang Tidak Dapat Diduga untuk MaxClique, Angka Kromatik dan Pewarnaan Grafik Perkiraan" - mungkin lebih lemah dari yang Anda inginkan, tetapi setidaknya itu berada di arah yang benar.

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

David Eppstein
sumber

\log d

$\log d$

Kenapa tidak bertanya Khot?

Chandra Chekuri

1

@chandra Baru saja mengirim email dan bertanya kepadanya, terima kasih atas sarannya! Saya akan memperbarui di sini jika saya mendengar kembali.

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

Hasil ini mungkin bermanfaat:

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

T. Emden-Weinert, S. Hougardy, B. Kreuter, grafik unik berwarna dan kekerasan grafik pewarnaan dari ketebalan besar, Combin. Mungkin. Komputasi. 7 (4) (1998) 375-386

Mohammad Al-Turkistany
sumber

kekerasan mendekati angka kromatik dalam grafik dengan derajat terikat

Jawaban: