Kekerasan CLIQUE berparameter?

Biarkan dan pertimbangkan masalah keputusan $0\le p\le 1$

CLIQUE Input: integer , grafik dengan simpul dan edge Pertanyaan: apakah berisi klik pada sekurang-kurangnya simpul ? $_p$
$s$ $G$ $t$ $\lceil p\binom{t}{2} \rceil$
$G$ $s$

Sebuah instance dari CLIQUE berisi proporsi dari semua kemungkinan edge. Jelas, CLIQUE mudah untuk beberapa nilai . CLIQUE hanya berisi grafik yang benar-benar terputus, dan CLIQUE berisi grafik lengkap. Dalam kedua kasus, CLIQUE dapat diputuskan dalam waktu linier. Di sisi lain, untuk nilai mendekati , CLIQUE adalah NP-hard dengan reduksi dari CLIQUE itu sendiri: pada dasarnya, cukup untuk mengambil persatuan yang terpisah dengan grafik Turán . $_p$ $p$ $_p$ $p$ $_0$ $_1$ $_p$ $p$ $1/2$ $_p$ $T(t,s-1)$

Pertanyaan saya:

Apakah CLIQUE baik dalam PTIME atau NP-complete untuk setiap nilai ? Atau apakah ada nilai yang CLIQUE memiliki kompleksitas menengah (jika P ≠ NP)? $_p$ $p$ $p$ $_p$

Pertanyaan ini muncul dari pertanyaan terkait untuk hypergraph, tetapi tampaknya menarik dengan sendirinya.

cc.complexity-theory np parameterized-complexity clique András Salamon
sumber

pertanyaan menarik!

Suresh Venkat

Apakah bilangan real antara 0 dan 1, atau dapat p menjadi fungsi dari t?

Robin Kothari

@Robin: Saya belum menentukan, keduanya akan menarik.

András Salamon

Jika proporsi tepi adalah batas atas (dan bukan persyaratan hitungan tepat atau batas bawah), maka untuk setiap konstanta masalah ini NP-keras dengan reduksi dari CLIQUE: Tambahkan seperangkat simpul terisolasi yang cukup besar . Apakah persyaratan bahwa tepi angka sama dengan ekspresi yang diberikan? Atau hal jelas apa yang saya lewatkan? :-)

0 < p < 1

$0<p<1$

gphilip

@ gphilip: Seperti yang Anda tunjukkan pengurangannya langsung jika proporsinya hanya batas atas; inilah mengapa pertanyaan ini diungkapkan dalam proporsi yang tepat.

András Salamon

Jawaban:

Saya berasumsi bahwa angka dalam definisi masalah CLIQUE_ppersis sama dengan jumlah tepi dalam grafik, tidak seperti komentar gphilip untuk pertanyaan tersebut. $\left\lceil p \binom{t}{2} \right\rceil$

Masalah CLIQUE _p adalah NP-lengkap untuk konstanta rasional 0 < p <1 dengan reduksi dari masalah CLIQUE yang biasa. (Asumsi bahwa p adalah rasional hanya diperlukan sehingga dapat dihitung dari N dalam polinomial waktu dalam N. ) $\lceil pN \rceil$

Misalkan k ≥3 menjadi bilangan bulat yang memenuhi k ² ≥1 / p dan (1−1 / k ) (1−2 / k )> p . Diberikan grafik G dengan n simpul dan tepi m bersama dengan nilai ambang s , reduksi bekerja sebagai berikut.

Jika s < k , kami menyelesaikan masalah CLIQUE dalam waktu O ( n ^s ) waktu. Jika ada klik ukuran setidaknya s , kami menghasilkan contoh ya tetap. Kalau tidak, kami menghasilkan tanpa contoh tetap.
Jika n < s , kami menghasilkan instance-tetap.
Jika n ≥ s ≥ k , kita tambahkan ke grafik G a ( k −1) di mana setiap set terdiri dari n simpul yang memiliki tepat tepian, dan menghasilkan grafik ini. $\left\lceil p \binom{nk}{2} \right\rceil - m$

Perhatikan bahwa kasus 1 membutuhkan O ( n ^{k -1} ) waktu, yang jumlahnya banyak di n untuk setiap p . Kasus 3 dimungkinkan karena jika n ≥ s ≥ k , maka adalah nonnegatif dan paling banyak jumlah tepi dalamgrafiklengkap (k−1) -kartit K_n_,…,_nseperti ditunjukkan dalam dua klaim berikut. $\left\lceil p \binom{nk}{2} \right\rceil - m$

Klaim 1 . . $\left\lceil p \binom{nk}{2} \right\rceil - m \ge 0$

Bukti . Sejak , cukuplah jika kita membuktikan $m \le \binom{n}{2}$ , atau ekuivalenpnk(nkequival1) ≥n(n−1). Karenap≥ 1 /k², kita memilikipnk(nk−1) ≥n(n−1 /k) ≥n(n−1). QED. $p \binom{nk}{2} \ge \binom{n}{2}$

Klaim 2 . . (Perhatikan bahwa sisi kanan adalah jumlah sisi dalam grafik lengkap (k − 1) -kartit K_n_,…,_n.) $\left\lceil p \binom{nk}{2} \right\rceil - m \lt n^2 \binom{k-1}{2}$

Bukti . Sejak danm≥ 0, cukuplah jika kita membuktikan $\lceil x \rceil \lt x+1$ , atau ekuivalenn²(k−1) (k−2) -pnk(nk−1) - 2 ≥ 0. Karenap<(1−1 /k) (1−2 /k), kami memiliki $p \binom{nk}{2} + 1 \le n^2 \binom{k-1}{2}$

n^{2} (k - 1) (k - 2) - hal n k (n k - 1) - 2

$n^2(k-1)(k-2) - pnk(nk-1) - 2$

\geq n^{2} (k - 1) (k - 2) - n (n - \frac{1}{k}) (k - 1) (k - 2) - 2

$\ge n^2(k-1)(k-2) - n \left( n-\frac{1}{k} \right) (k-1)(k-2) - 2$

QED.

= \frac{n}{k} (k - 1) (k - 2) - 2 \geq (k - 1) (k - 2) - 2 \geq 0.

$= \frac{n}{k} (k-1)(k-2) - 2 \ge (k-1)(k-2) - 2 \ge 0.$

Sunting : Pengurangan dalam Revisi 1 memiliki kesalahan; terkadang diperlukan grafik dengan jumlah tepi negatif (ketika p kecil). Kesalahan ini diperbaiki sekarang.

Tsuyoshi Ito
sumber

ini paling dekat dengan frasa tertentu, jadi terima kasih telah mengatasi ini. Kasus 3 paling dekat dengan apa yang ada dalam pikiran saya. Namun, saya tidak mengikuti perhitungan - dapatkah Anda sedikit memperluas?

András Salamon

@ András Salamon: Selesai.

Tsuyoshi Ito

$p$ $t$ $p$ $\log^4 t$ $s$ $\log^2 t$ $t^{\log^2 t}$

$\log^2 t$

$p$

Boaz Barak
sumber