Wykres jest akordowy, jeśli nie indukował cykli o długości 4 lub większej. Drzewo klika T z G jest drzewem, w którym wierzchołki drzewa są maksymalne klik z G . Krawędź w T odpowiada minimalnemu separatorowi. Liczba odrębnych drzew kliki może być wykładnicza pod względem liczby wierzchołków na wykresie akordowym.
Zmniejszona klika wykres jest sumą wszystkich drzew klika G . Oznacza to, że ma te same wierzchołki i wszystkie możliwe krawędzie. Jaka jest złożoność obliczania C r ( G ) dla danego G ?
Myślę, że kiedyś widziałem prezentację, w której twierdzono, że można obliczyć w czasie O ( m + n ) bez dowodu. Oznaczałoby to, że jest tak łatwe, jak obliczanie drzewa kliki G . Czy istnieje odniesienie, które to potwierdza, lub daje wolniejszy algorytm do jego obliczania?