Złożoność czasowa liczenia trójkątów na wykresach płaskich

16

Liczenie trójkątów na ogólnych wykresach można trywialnie wykonać w czasie i myślę, że znacznie szybsze wykonanie jest trudne (mile widziane referencje). Co z grafami płaskimi? Poniższa prosta procedura pokazuje, że można tego dokonać w czasie . Moje pytanie jest dwojakie: $O(n^3)$ $O(n\log{n})$

Jakie jest odniesienie do tej procedury?
Czy czas może być liniowy?

Z algorytmicznego dowodu twierdzenia Liptona-Tarjana o separatorze planarnym możemy, w czasie liniowym w wielkości wykresu, znaleźć podział wierzchołków wykresu na trzy zestawy tak że nie ma żadnych krawędzi z jednym punktem końcowym w i drugi w , ma rozmiar ograniczony przez $A,B,S$ $A$ $B$ $S$ i obamają rozmiary górne ograniczone przez $O(\sqrt{n})$ $A,B$ liczby wierzchołków. Należy zauważyć, że każdy trójkąt wykres leży całkowicie wewnątrz alboalbo całkowicie wewnątrzlub stosuje się co najmniej jeden wierzchołekz dwoma innymi wierzchołkilub obu z nich. Wystarczy zatem zliczyć liczbę trójkątów na wykresie nai sąsiadówna(i podobnie dla). Zauważ, żei jego-sąsiadują indukująpłaski wykresroutera (wspomniany wykres jest podgraphem płaskiego wykresu o średnicy $\frac{2}{3}$ $A$ $B$ $S$ $A \cup S$ $B \cup S$ $S$ $S$ $A$ $B$ $S$ $A$ $k$ $4$ ). Tak więc zliczanie liczby trójkątów na takim wykresie można wykonać bezpośrednio przez programowanie dynamiczne lub przez zastosowanie twierdzenia Courcelle (wiem na pewno, że taka wersja zliczania istnieje w świecie Logspace autorstwa Elberfelda i in. I domyślam się, że ona również istnieje w liniowym świecie czasu), ponieważ tworzenie niekierowanego trójkąta jest właściwością i ponieważ rozkład drzewa o ograniczonej szerokości jest łatwy do uzyskania z osadzonego płaskiego wykresu routera. $\mathsf{MSO}_1$ $k$

W ten sposób zredukowaliśmy problem do pary problemów, z których każdy jest stałą częścią mniejszą kosztem liniowej procedury czasowej.

Zauważ, że procedurę można rozszerzyć, aby znaleźć liczbę wystąpień dowolnego połączonego grafu wewnątrz wykresu wejściowego w czasie . $O(n\log{n})$

reference-request graph-algorithms planar-graphs

— SamiD
źródło

6

Możesz policzyć trójkąty na ogólnych wykresach, biorąc macierz sąsiedztwa

i obliczając

. Zajmuje to czas

, gdzie

jest wykładnikiem mnożenia macierzy.

A

$A$

t r (A^{3}) / 6

$tr(A^3)/6$

n^{ω}

$n^{\omega}$

ω < 2.373

$\omega < 2.373$

— Ryan Williams

@RyanWilliams Oczywiście masz rację! Zaktualizuję pytanie.

— SamiD,

20

Liczbę wystąpień dowolnego stałego wykresu podrzędnego H na wykresie planarnym G można policzyć w czasie O (n), nawet jeśli H jest odłączony. To i kilka powiązanych wyników opisano w artykule Subgraf Isomorphism in Planar Graphs and Related Problems autorstwa Davida Eppsteina z 1999 r .; patrz Twierdzenie 1. Artykuł rzeczywiście używa technik treewidth.

— Bart Jansen
źródło

19

Chociaż odpowiedź Barta Jansena rozwiązuje ogólny przypadek zliczania podgrafów, problem zliczania (lub notowania) wszystkich trójkątów na wykresie planarnym (lub bardziej ogólnie dowolnego wykresu ograniczonej arborności) jest znany z tego, że czas liniowy jest znacznie dłuższy. Widzieć

C. Papadimitriou i M. Yannakakis, Problem kliki dla grafów płaskich, Inform. Proc. Letters 13 (1981), s. 131–133.

i

N. Chiba i T.Nishizeki, Algorytmy arboryczności i listowania podgraficznego, SIAM J. Comput. 14 (1985), s. 210–223.

— David Eppstein
źródło