Czy szerokość sugeruje istnienie nieletniego ?

Niech zostanie naprawione, a będzie (połączonym) wykresem. Jeśli się nie mylę, z pracy Bodlaendera [1, Twierdzenie 3.11] wynika, że jeśli szerokość wynosi w przybliżeniu co najmniej , wówczas zawiera gwiazdę jako pomniejszą. $k$ $G$ $G$ $2k^3$ $G$ $K_{1,k}$

Czy możemy zmniejszyć termin ? To znaczy, czy powiedzmy, że szerokość co najmniej już implikuje istnienie mniejszej wartości ? Czy jest gdzieś dowód? $2k^3$ $k$ $K_{1,k}$

[1] Bodlaender, HL (1993). W przypadku mniejszych testów liniowych z wyszukiwaniem w pierwszej kolejności. Journal of Algorytmy, 14 (1), 1-23.

graph-theory treewidth graph-minor Juho
źródło

Luźno powiązany wynik z Demaine i Hajiaghayi : Dla ustalonego wykresu każdy mniejszy od wykres o mniejszej szerokości ma drugorzędny wykres siatki .

H

$H$

H

$H$

w

$w$

Ω (w) \times Ω (w)

$\Omega(w) \times \Omega(w)$

mhum,

@ mhum stała w wykładniczo zależy od, więc bezpośrednie zastosowanie tego spowoduje ograniczenie gorsze niż .

Ω

$\Omega$

| H |

$|H|$

2 k^{3}

$2k^3$

daniello,

@daniello Tak właśnie jest. Stała nie jest zbyt ładna, a specjalizacja w grafach wolnych od również nie jest świetna. Chciałem tylko zwrócić uwagę na niejasny wynik.

H

$H$

mhum,

To prawda, że każdy wykres bez moll ma szerokość co najwyżej . Udowadniamy to poniżej, najpierw kilka definicji: $G$ $K_{1,k}$ $k-1$

Niech jest treewidth z i jako wielkość maksymalna klika w . Wykres jest triangulacją jeśli jest podgraphem a jest akordem (tzn. Nie ma indukowanych cykli na co najmniej wierzchołkach). Triangulacja o jest minimalna triangulacji jeśli ma właściwej subgraph z jest również triangulacja . Podzbiór wierzchołków jest potencjalną maksymalną kliką $tw(G)$ $G$ $\omega(G)$ $G$ $H$ $G$ $G$ $H$ $H$ $4$ $H$ $G$ $H$ $G$ $X$ $G$ Jeżeli istnieje minimalny triangulacji o , tak że jest ilość klika . Jest dobrze wiadomo, że W tym przypadku, minimalna przejmuje wszystkie minimalne triangulacyjnych o . $H$ $G$ $X$ $H$

t w (G) = min_{H} ω (H) - 1

$tw(G) = \min_{H} \omega(H) - 1$

H

$H$

G

$G$

Powyższy wzór sugeruje, że aby udowodnić, że wystarczy udowodnić, że wszystkie potencjalne maksymalne kliki mają rozmiar co najwyżej . Udowadniamy to teraz. Niech będzie potencjalną maksymalną kliką i załóżmy, że . $tw(G) \leq k-1$ $G$ $k$ $X$ $G$ $|X| \geq k+1$

Wykorzystamy następującą charakterystykę potencjalnych maksymalnych klików: zbiór wierzchołków jest potencjalnymi maksymalnymi klikami w jeśli i tylko wtedy, gdy dla każdej pary , niesąsiadujących (wyraźnych) wierzchołków w istnieje ścieżka z do w ze wszystkimi wierzchołkami wewnętrznych zewnątrz z . Charakterystykę tę można znaleźć w artykule Treewidth i Minimum Fill-in: Grouping the Minimal Separators według Bouchitte i Todinca. $X$ $G$ $u$ $v$ $X$ $P_{u,v}$ $u$ $v$ $G$ $X$

Z tej charakterystyki jest łatwo wyprowadzić Mniejszej od . Niech . Dla każdego wierzchołka , albo stanowi krawędź lub jest ścieżka z do z wszystkich wewnętrznych wierzchołków poza . Dla wszystkich , które nie sąsiadują z kurczą się wszystkie wewnętrzne wierzchołki do . W rezultacie otrzymujemy niewielką część w której sąsiaduje z całym , i $K_{1,k}$ $X$ $u \in X$ $v \in X \setminus \{u\}$ $uv$ $G$ $P_{u,v}$ $u$ $v$ $X$ $v \in X$ $u$ $P_{u,v}$ $u$ $G$ $u$ $X$ $|X| \geq k+1$ . Tak więc stopień w tym pomniejszeniu wynosi co najmniej , uzupełniając dowód. $u$ $k$

Daniello
źródło

Dziękuję Daniel! Czy zdarza ci się wiedzieć, czy ten sam argument (lub wynik, naprawdę) został gdzieś opublikowany?

Juho

Nie mam referencji, ale wydaje mi się, że pamiętam, że gdzieś zapisany jest podobny (prawdopodobnie mniej ścisły) argument dla wolnych wykresów . Niestety nie mam bardziej konkretnego wskaźnika.

K_{2, r}

$K_{2,r}$

daniello,

Czy szerokość sugeruje istnienie nieletniego ?

Odpowiedzi: