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,