Parametr wykresu prawdopodobnie związany z szerokością

Interesują mnie wykresy $n$ wierzchołków, które można wytworzyć w następujący sposób.

1. Zacznij od dowolnego wykresu $G$ na $k\le n$ wierzchołków. Oznacz wszystkie wierzchołki w $G$ jako nieużywane .
2. Opracowanie nowego wykres dodaje się nowy wierzchołek V , który jest połączony z jedną lub więcej niewykorzystanych wierzchołków G i nie jest połączony z żadnym używane wierzchołków G . Oznacz v jako nieużywane .$G'$$v$$G$$G$$v$
3. Oznacz jeden z wierzchołków w z którym v jest połączony zgodnie z użyciem .$G'$$v$
4. Ustaw na G ′ i powtarzaj od kroku 2, aż G będzie zawierało n wierzchołków.$G$$G'$$G$$n$

Nazwij takie wykresy „wykresami złożoności ” (przeprosiny za niejasną terminologię). Na przykład, jeśli G jest wykresem złożoności 1, G jest ścieżką.$k$$G$$G$

Chciałbym wiedzieć, czy ten proces był wcześniej badany. W szczególności, dla dowolnego , czy NP jest kompletne w celu ustalenia, czy wykres ma złożoność k ?$k$$k$

Problem ten wydaje się nieco podobny do pytania, czy jest częściowe k -tree , czyli ma treewidth k . Wiadomo, że ustalenie, czy G ma szerokość k, jest NP-całkowite. Jednak niektóre wykresy (na przykład gwiazdy) mogą mieć znacznie mniejszą szerokość rozwarcia niż omawiana tutaj miara złożoności.$G$$k$ $k$$G$$k$

4 października 2012 r .: Pytanie zostało przesłane do MathOverflow po tym, jak po tygodniu nie było rozstrzygającej odpowiedzi (choć dzięki za informacje o przepływach przyczynowych).

Chociaż rozmawialiśmy o tym wcześniej osobiście, dodam to w nadziei, że pozwoli to komuś innemu udzielić pełnej odpowiedzi.

W procesie dodawania wierzchołków zdefiniuj funkcję częściową z każdego używanego wierzchołka v , do wierzchołka dodanego, gdy użyto v . Potem okazuje się, że f jest (przyczynową) funkcją przepływu (s. 39), która jest ograniczoną wersją pokrycia ścieżki. Rzeczywiście, twój opis tych wykresów „złożoności k ” (biorąc pod uwagę zestaw wierzchołków, które mają być początkowo nieużywanymi wierzchołkami i końcowymi nieużywanymi wierzchołkami) jest właśnie rozkładem gwiazdy „geometrii” o przepływie przyczynowym (str. 46 powyższego artykułu).$f:V(G) \rightharpoonup V(G)$$v$$v$$f$

Chociaż te „przepływy przyczynowe” badano głównie w kontekście obliczeń kwantowych (opartych na pomiarach) - gdzie są one motywowane pewnymi strukturami obwodów unitarnych - istnieją o nich teoretyczne wyniki, które są całkowicie oddzielone od obliczeń kwantowych:

Punkty końcowe modulo unikatowości : wykresy o „złożoności  ” są dokładnie tymi, dla których istnieją (ewentualnie przecinające się) zbiory S , T ⊆ V ( G ) , oba o wielkości$k$$S,T \subseteq V(G)$$k$ , tak że ma dokładnie jedno pokrycie ścieżki o rozmiarze k, którego ścieżki rozpocznie się S i kończy się w T .$G$$k$$S$$T$

Ekstremalne wykresy : Wykres wierzchołków o „złożoności k ” ma co najwyżej k n - ( k + $n$$k$ krawędzie.$kn - \binom{k+1}{2}$

Korzystając z tych wyników i biorąc pod uwagę kandydującą parę zestawów , określając, czy „podporządkowują” się w ten sposób unikalne pokrycie ścieżki w ten sposób, można ustalić w czasie O ( k 2 n ) ; ale stwierdzenie, czy istnieją takie zestawy punktów końcowych, co stanowi pozorną trudność, a powyższy ekstremalny wynik (który jest jedynie warunkiem koniecznym) wydaje się reprezentować stan techniki pod względem skutecznych kryteriów w celu ustalenia, czy takie zestawy istnieją.$S,T$$O(k^2 n)$

Wszystkie wykresy złożoności mają szerokość ścieżki co najwyżej k . Na każdym kroku zestaw nieużywanych węzłów stanowi separator oddzielający używane węzły od już utworzonych. Tak więc na każdym kroku, gdy dodajesz wierzchołek, możesz utworzyć torbę zawierającą ten wierzchołek oraz wszystkie nieużywane wierzchołki i połączyć torbę na końcu rozkładu ścieżki. To będzie prawidłowy rozkład ścieżki.$k$$k$

Ze względu na „które jest połączone” w punktach 3 i 2 szerokość ścieżki może być znacznie mniejsza niż k . Nie jestem pewien, czy zdecyduję, czy G jest złożonością k , ale, jak mówi Niel, musi istnieć pokrycie ścieżki o rozmiarze k, ale nie tylko pokrycie ścieżki, ścieżki muszą być indukowane. Pomiędzy ścieżkami możemy mieć ten zygzakowaty wzór. Możemy w czasie f ( k ) ⋅ p o l y ( n ) obliczyć optymalny rozkład ścieżki, następnie możemy użyć tego rozkładu do wykonania programowania dynamicznego, jednocześnie śledząc różne segmenty tych $v$$k$$G$$k$$f(k) \cdot poly(n)$$k$ścieżki, do której należą i kolejność segmentów należących do tej samej ścieżki. I dla każdej pary segmentów należących do różnych ścieżek musimy tylko znać pierwszą i ostatnią ścieżkę zygzakowatą.

Dlatego też, że można zadecydować, czy wykres ma złożoność w f ( k ) ⋅ p o, l y ( n ) czasu.$k$$f(k) \cdot poly(n)$