Temukan simpul mana yang akan dihapus dari grafik untuk mendapatkan komponen terbesar terkecil

Diberikan grafik , cari simpul , yang penghapusan akan menghasilkan grafik dengan komponen terkecil terkecil. $G = (V, E)$$k$$\{v^*_1,\dots,v^*_k\}$

Saya berasumsi untuk besardan besar masalahnya sulit (NP-keras), tapi saya tertarik pada nilai kecil ( ).$n = |V|$$k$$k$$k \in \{1, 2, 3, 4\}$

Untuk , saya pikir mungkin untuk menemukan titik terbaik untuk dihapus dengan melakukan pencarian kedalaman-pertama-tunggal pada grafik (yaitu, memeriksa titik artikulasi).$k = 1$$\{v^*_1\}$

Untuk , dimungkinkan untuk menemukan simpul terbaik dengan melakukan pencarian kedalaman-pertama (masing-masing untuk grafik ). Pendekatan serupa dapat diterapkan dalam kasus .$k = 2$$\{v^*_1, v^*_2\}$$n$$G_i = G / \{v_i\}$$k > 2$

Saya ingin tahu apakah ada solusi yang lebih baik dari itu.

(Terkait: menghitung jumlah simpul minimum tanpa harus menyebutkannya )

Masalah yang Anda gambarkan dikenal sebagai Component Connect Connectivity di bidang langkah-langkah kerentanan grafik . Versi keputusan masalah adalah sebagai berikut:

Konektivitas Pesanan Komponen :

Input: Grafik , bilangan bulat dan$G = (V,E)$$k$$\ell$

Pertanyaan: Apakah ada sekumpulan simpul dengan ukuran paling banyak sehingga ukuran komponen terbesar paling banyak ?$X \subseteq V$$k$$G - X$$\ell$

Masalahnya jelas NP-lengkap karena menggeneralisasi vertex cover; kasus ketika adalah penutup simpul. Oleh karena itu masalahnya tidak dapat diperbaiki dengan parameter yang bisa ditelusur ketika diparameterisasi oleh (kecuali ). Masalahnya juga dikenal sebagai -dekat ketika diparameterisasi oleh . Karenanya, kita harus menggunakan algoritma dengan waktu berjalan eksponensial dalam$\ell=1$$\ell$$FPT = W[1]$$W[1]$$k$$k+\ell$.

Pertanyaan yang sangat menarik. Untuk input$G,k,\ell$, pendekatan brute force adalah:

branching(G,k,l):
    Find a connected set of vertices D of G of size l+1
    if no such D exists:
            return True // no component of size > l
    for v in D:
        if branching(G-v,k-1,l):
            return True
    return False

Algoritma berjalan dalam waktu $(\ell + 1)^k \cdot n^2$.

Perhatikan contoh ya itu $G,k,\ell$ masalah memiliki treewidth, dan memang pathwidth paling banyak $k+\ell$. Ini dapat diamati dengan melihat bahwa mengambil set penghapusan$X$ ukuran paling banyak $k$ menghasilkan grafik $G-X$ di mana setiap komponen yang terhubung memiliki ukuran paling banyak $\ell$. Oleh karena itu, dekomposisi jalur yang valid adalah dengan membuat satu tas untuk masing-masing komponen$G-X$ lalu tambahkan semua $X$untuk setiap tas. Oleh karena itu setiap contoh ya punya$|E(G)| \leq n(k+\ell)$.

Masalah terkait telah dipelajari di masa lalu dengan nama Graph Integrity, atau Vertex Integrity untuk membedakan versi penghapusan titik dan versi penghapusan tepi:

Integritas Vertex :

Input: Grafik$G = (V,E)$, bilangan bulat $p$

Pertanyaan: Apakah ada seperangkat simpul$X \subseteq V$ seperti yang $|X| + \max_{D \in cc(G-X)}|D| \leq p$?

Artinya, jumlah set penghapusan dan ukuran komponen maksimal harus diminimalkan. Masalah ini juga NP-hard. Lihat, misalnya,

• Clark, LH, Entringer, RC, Fellows, MR: Komputasi kompleksitas integritas. J. Combin. Matematika Kombinasikan. Comput 2, 179–191 (1987)
• Fellows, M., Stueckle, S .: Urutan pencelupan, subgraph terlarang dan kompleksitas integritas jaringan. J. Combin. Matematika Kombinasikan. Komputasi 6, 23–32 (1989)