Masalah sulit untuk grafik genus yang lebih tinggi

17

Grafik planar memiliki genus nol. Grafik yang dapat disematkan pada torus memiliki genus paling banyak 1. Pertanyaan saya sederhana:

Apakah ada masalah yang dapat dipecahkan secara polinomi pada grafik planar tetapi NP-hard pada grafik genus satu?
Lebih umum apakah ada masalah yang secara polinomi dapat dipecahkan pada grafik genus g tetapi NP-keras pada grafik genus> g?

cc.complexity-theory ds.algorithms graph-theory planar-graphs Siwa Kintali
sumber

Untuk pertanyaan kedua, apakah Anda ingin masalah menjadi NP-hard untuk grafik genus> = k, di mana k adalah konstanta lebih besar dari g? ATAU apakah Anda hanya ingin masalah menjadi NP-hard untuk grafik yang genusnya tidak kurang dari g (yang setara dengan itu NP-hard untuk grafik umum)?

Robin Kothari

1

Saya mencari masalah NP-Hard untuk grafik genus> = k, di mana k adalah konstanta lebih besar dari g.

Shiva Kintali

16

Ini adalah publisitas karya saya sendiri, tetapi angka silang dan 1-planaritas dapat dipecahkan secara sepele dalam grafik planar tetapi sulit untuk grafik genus satu. Lihat http://arxiv.org/abs/1203.5944

some one
sumber

3

"Sebuah grafik mendekati planar jika dapat diperoleh dari grafik planar dengan menambahkan sebuah tepi. Grafik adalah 1-planar jika memiliki gambar di mana setiap sisi dilintasi oleh paling banyak satu sisi lainnya. Kami menunjukkan bahwa itu adalah NP - Sulit untuk memutuskan apakah grafik near-planar yang diberikan adalah 1-planar. " Saya pasti melewatkan sesuatu. Mengapa tidak semua grafik dekat-planar juga 1-planar?

Tyson Williams

4

Apa yang saya pikir Anda katakan adalah bahwa Anda hanya dapat mengambil planar embedding dan menambahkan tepi kembali. Namun, tepi ekstra itu dapat melintasi lebih dari satu sisi, melanggar 1-planaritas.

G - e

$G-e$

Timothy Sun

@TimothySun Ya. Setiap sisi selain dari akan dilintasi paling banyak satu kali (oleh ), tetapi dapat dilintasi oleh lebih dari satu sisi lainnya, yang tidak diperbolehkan. Terima kasih.

e

$e$

e

$e$

e

$e$

Tyson Williams

4

Jika masalah mainan baik-baik saja:

Misalkan dan biarkan menjadi beberapa grafik genus . Untuk formula-CNF, misalkan menjadi beberapa penyandian sebagai grafik planar ditambah salinan . $g\in\mathbb{N}$ $H$ $g+1$ $\phi$ $G_\phi$ $\phi$ $H$

Mengingat , yang merupakan grafik genus , NP-sulit untuk memutuskan apakah memuaskan. Namun masalah ini menjadi sepele ketika terbatas pada grafik genus . $G_\phi$ $g+1$ $\phi$ $\leq g$

Radu Curticapean
sumber

2

apa masalah ini pada grafik genus

\leq g

$\leq g$

Sasho Nikolov

1

Semua grafik memiliki genus . Dengan demikian, jika Anda membatasi masalah pada grafik genus , Anda selalu dapat menolak.

G_{ϕ}

$G_\phi$

g + 1

$g+1$

g

$g$

Radu Curticapean

ah, itu menjadi sangat sepele, saya mengerti

Sasho Nikolov

2

EDIT (2012-09-05): Komentar Jeff dan Radu benar. Hasil yang dikutip tidak menjawab pertanyaan. Untuk memperluas komentar Radu, berikut adalah algoritma terkait oleh Bravyi yang memberikan algoritme untuk mengontrak tensor matchgate pada grafik dengan genus dengan run-time di mana adalah jumlah minimum tepi yang harus dihapus dari untuk membuatnya planar. $G$ $g$ $T=poly(n) + 2^{2g} O(m^3)$ $m$ $G$

Cai, Lu, dan Xia baru-baru ini membuktikan dikotomi berikut untuk masalah penghitungan #CSP:

Kami membuktikan teorema dikotomi kompleksitas dalam kerangka penghitungan masalah CSP. Fungsi kendala lokal mengambil input Boolean, dan dapat menjadi fungsi simetris bernilai nyata yang sewenang-wenang. Kami membuktikan bahwa, setiap masalah di kelas ini milik tepat tiga kategori:

(1) grafik yang dapat ditelusuri (yaitu, waktu polinomial yang dapat dihitung) pada grafik umum, atau
(2) grafik yang # P-hard pada grafik umum tetapi dapat ditelusur pada grafik planar , atau
(3) grafik yang # P-hard even pada grafik planar.

Kriteria klasifikasi adalah eksplisit.

Martin Schwarz
sumber

2

Ini tidak menjawab pertanyaan. Bisakah kategori (2) dapat dipecah menjadi (2a) yang dapat ditelusur untuk grafik planar tetapi # P-hard untuk grafik toroidal, dan (2b) yang dapat ditelusur untuk grafik gen-gen terikat tetapi # P-hard untuk grafik genus tidak terikat?

Jeffε

3

Kasus (2) terdiri dari masalah yang dapat direduksi menjadi penghitungan kecocokan sempurna dalam grafik planar dengan memperkenalkan gadget planar lokal. Diketahui juga bahwa pencocokan sempurna dapat dihitung dalam waktu polinomial pada grafik genus-terikat. Dengan demikian, semua masalah dalam kasus (2) sebenarnya dapat ditelusuri pada grafik gen-terikat.

Radu Curticapean

2

$g$ $g$ $X_g$ $g$ $g$ $g$ $X_g$ $g$

$\mathcal C$ $\mathcal C$

David Richerby
sumber

Masalah sulit untuk grafik genus yang lebih tinggi

Jawaban: