Masalah ODD EVEN DELTA

Biarkan menjadi grafik. Biarkan menjadi bilangan bulat. Mari menjadi jumlah tepi diinduksi subgraphs dari memiliki simpul dan ganjil tepi. Mari menjadi jumlah tepi diinduksi subgraphs dari memiliki simpul dan jumlah yang lebih dari tepi. Biarkan . Masalah ODD EVEN DELTA terdiri dalam komputasi , mengingat $G = ( V, E )$ $k \leq |V|$ $O_k$ $G$ $k$ $E_k$ $G$ $k$ $\Delta_k = O_k - E_k$ $\Delta_k$ $G$ dan . $k$

Pertanyaan

Apakah mungkin untuk menghitung dalam waktu polinomial? Algoritme manakah yang paling dikenal untuk menghitungnya? $\Delta_k$

Bagaimana jika adalah 3-reguler? $G$

Bagaimana jika adalah bipartit 3-reguler? $G$

Bagaimana jika adalah planar bipartit 3-reguler? $G$

ds.algorithms graph-theory graph-algorithms counting-complexity Giorgio Camerani
sumber

Apa motivasi anda?

Tyson Williams

@TysonWilliams: Motivasi saya adalah bahwa, jika bagian pertama dari pertanyaan pertama memiliki jawaban yang pasti (bahkan hanya untuk kasus planar 3-reguler bipartit), maka akan ada beberapa konsekuensi menarik yang perlu dijelajahi lebih lanjut. Jika algoritmanya sub-eksponensial, ia masih akan memiliki beberapa konsekuensi (kurang menarik, namun tetap memerlukan lebih banyak eksplorasi).

Giorgio Camerani

Bisakah Anda lebih spesifik? Apa yang Anda maksud dengan "beberapa konsekuensi menarik"? Bagaimana Anda menemukan masalah ini sejak awal?

Tyson Williams

@TysonWilliams: Bisakah kita melanjutkan percakapan ini secara pribadi, melalui email?

Giorgio Camerani

Jawaban:

Masalah ODD EVEN DELTA adalah # P-hard, bahkan pada grafik planar bipartit 3-reguler.

Mari adalah himpunan vertex sampul grafik umum . Kemudian, dengan asumsi tidak memiliki simpul yang terisolasi, persamaan berikut berlaku (lihat artikel di atas untuk buktinya): $\mathcal{C}$ $G$ $G$

| C | = 2^{| V |} - \sum_{k = 2}^{| V |} Δ_{k} \cdot 2^{| V | - k}

$|\mathcal{C}| = 2^{|V|} - \sum_{k = 2}^{|V|} \Delta_k \cdot 2^{|V|-k}$

Penghitungan penutup simpul adalah # P-lengkap bahkan pada grafik planar bipartit 3-reguler, dan dapat dilakukan dengan jumlah panggilan linear ke oracle ODD EVEN DELTA.

Giorgio Camerani
sumber

MEMPERBARUI:

Saya seharusnya menunjukkan bahwa jawaban di bawah ini adalah tentang kasus khusus. Karena kasus ini sulit, masalah untuk umum juga sulit. $k = |V|$ $k$

Kerangka kerja Holant pada dasarnya adalah jumlah eksponensial atas rentang subgraf (yaitu semua simpul hadir dalam subgraf, sehingga jumlahnya lebih dari subset tepi). Sebaliknya, versi pertanyaan saat ini adalah tentang subgraf yang disebabkan oleh tepi.

Versi sebelumnya dari pertanyaan ini berkaitan dengan penghitungan subgraph tertentu tanpa simpul yang terisolasi. Jawaban di bawah ini dengan benar membahas persyaratan ini. Ketika mempertimbangkan kedua subgraf spanning (yaitu kerangka Holant) dan tidak ada simpul yang terisolasi, ini sama dengan mempertimbangkan subgraf tepi yang diinduksi dengansudut. OP pada dasarnya menunjukkan ini dalam pertanyaan ini . $|V|$

Grafik Planar 3-Reguler

Untuk saat ini, saya akan mengabaikan kebutuhan Anda bahwa grafik adalah bipartit. $G$

Misalkan adalah grafik planar 3-reguler. Masalah Anda dapat dinyatakan sebagai masalah Holant planar bipartit $G$

Pl-Holant ([1, 0, - 1] | [0, 1, 1, 1]) .

$\text{Pl-Holant}([1,0,-1]|[0,1,1,1]).$

Biarkan saya jelaskan caranya. Untuk lebih detail daripada yang saya berikan di bawah ini, lihat makalah ini .

Holant adalah jumlah penjumlahan (Boolean) pada edge. Pada simpul ada batasan siapa input adalah tugas untuk tepi insiden mereka. Untuk setiap penugasan ke tepi, kami mengambil produk dari semua batasan dhuwur.

Persyaratan Anda bahwa tidak ada simpul yang terisolasi adalah kendala yang tidak puas pada simpul tertentu jika tidak ada tepi insiden yang dipilih dan puas jika setidaknya satu sisi dipilih. Ini simetris kendala dilambangkan dengan [0,1,1,1], yang output 0 (yaitu tidak puas) ketika jumlah input 1 adalah 0 (yaitu tidak ada tepi insiden di subgraf) dan output 1 (yaitu puas) ketika nomor input 1 adalah 1, 2, atau 3 (yaitu 1, 2, atau 3 tepi insiden dalam subgraph).

$G$ $G$ $n$ $(-1)^n = 1$ $n$ $(-1)^n = -1$

Masalah bipartit Holant ini adalah # P-hard oleh Teorema 6.1 dalam makalah ini . Namun, teorema itu bukan yang paling mudah untuk diterapkan. Sebagai gantinya, pertimbangkan hal berikut.

$T = \begin{bmatrix} -1 & 1 \\ 0 & 1 \end{bmatrix},$

\begin{aligned} Pl-Holant ([1, 0, - 1] | [0, 1, 1, 1]) & = Pl-Holant ([1, 0, - 1] T^{\otimes 2} | (T^{- 1})^{\otimes 3} [0, 1, 1, 1]) \\ = Pl-Holant ([1, - 1, 0] | [1, 0, 0, 1]) . \end{aligned}

$\begin{align*} \text{Pl-Holant}([1,0,-1]|[0,1,1,1]) &= \text{Pl-Holant}([1,0,-1] T^{\otimes 2}|(T^{-1})^{\otimes 3}[0,1,1,1])\\ &= \text{Pl-Holant}([1,-1,0]|[1,0,0,1]). \end{align*}$

Maka mudah untuk melihat bahwa masalah ini adalah # P-hard oleh Theorem 1.1 dalam tulisan ini .

Membatasi Grafik Bipartit

Sama seperti pertanyaan Anda sebelumnya , masalah yang sama terbatas pada grafik bipartit jauh lebih sulit untuk ditangani dan saya percaya itu masih merupakan masalah terbuka. Kami memiliki dugaan tentang kasus-kasus yang dapat ditelusuri (dan saya akan memeriksa untuk melihat apakah masalah Anda adalah salah satunya), tapi saya pikir masalah Anda masih # P-keras bahkan ketika terbatas pada grafik bipartit.

Tyson Williams
sumber

Terima kasih telah mendedikasikan waktu Anda untuk pertanyaan ini dan telah memberikan jawaban yang begitu mendetail. Karena tidak terbiasa dengan kerangka kerja Holant, saya perlu beberapa waktu untuk menguraikannya dan memetabolisme sepenuhnya alasan Anda (tentu saja saya tidak ragu dengan kebenarannya, hanya saja saya ingin memahami setiap langkah, tidak hanya kesimpulannya) . Untuk apa yang menyangkut pembatasan bipartiteness, ya akan sangat bagus jika Anda dapat memeriksa apakah dugaan yang mudah ditelusuri mencakup masalah saya.

Giorgio Camerani