ΣP2P na ograniczonych wykresach szerokości drzewa. W rzeczywistości myślę, że te problemy są trudniejsze niż użycie normalnego programowania dynamicznego na wykresach ograniczonej szerokości do ich rozwiązania.
Jeśli problem dotyczy P dla wykresów ograniczonej szerokości, dlaczego mówisz, że jest „trudniejsze niż użycie normalnego DP” na takich wykresach?
Suresh Venkat
Odpowiedzi:
11
Lista Chromatic Number (Czy to prawda, że wykres ma kolor wierzchołków, ilekroć każdy wierzchołek otrzyma listę k dopuszczalnych kolorów?) Jest ΠP.2)-kompletny problem, ale rozwiązany w czasie liniowym na wykresach ograniczonej szerokości:
Jeśli podoba ci się ten wynik, być może interesuje Cię również następujący artykuł: arxiv.org/abs/1110.4077 . Pojawiło się na arXiv w tym tygodniu, a autorzy pokazują, że liczba chromatyczna krawędzi listy i całkowita liczba chromatyczna listy są również możliwe do rozwiązania w czasie liniowym dla wykresów ograniczonej szerokości.
Bart Jansen
13
I think 2-clique-coloring [GT19 in Schaefer and Umans] is an example. The question is whether the given graph can be (improperly) 2-colored in such a way that none of its maximal cliques are monochromatic. For graphs of bounded treewidth, each maximal clique should occur within a single bag of the tree decomposition, so it should work to use the standard dynamic programming approach in which the states of the dynamic program are 2-colorings of the bag that correctly color all maximal cliques within the bag and are consistent with good states of the child bags.
Jest również w P dla TW (<= k) również z tego powodu: kolorystyka k-kliki jest wyrażalna przez MS: „Występuje X_1, ... X_k (Partycja (X_1, ..., X_k) i ForAll X (CliqueMax (X) => not (Exists X_i (Forall x in X (x in X_i))))))
M. kanté
2
wydaje mi się, że masz na myśli ∃X1, ... ,Xk:(IsPartition(X1,…,Xk)∧∀X:(MaxClique(X)⟹¬(∃Xi:∀x∈X:x∈Xi)))
Odpowiedzi:
Lista Chromatic Number (Czy to prawda, że wykres ma kolor wierzchołków, ilekroć każdy wierzchołek otrzyma listę k dopuszczalnych kolorów?) JestΠP.2) -kompletny problem, ale rozwiązany w czasie liniowym na wykresach ograniczonej szerokości:
http://www.ii.uib.no/~daniello/papers/EqColoring.pdf
źródło
I think 2-clique-coloring [GT19 in Schaefer and Umans] is an example. The question is whether the given graph can be (improperly) 2-colored in such a way that none of its maximal cliques are monochromatic. For graphs of bounded treewidth, each maximal clique should occur within a single bag of the tree decomposition, so it should work to use the standard dynamic programming approach in which the states of the dynamic program are 2-colorings of the bag that correctly color all maximal cliques within the bag and are consistent with good states of the child bags.
źródło