Czy jest jakiś problem w

16

$\mathsf{\Sigma^P_2}$ $\mathsf{P}$ 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.

cc.complexity-theory graph-theory treewidth

— Saeed
źródło

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

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 $\Pi_2^P$ -kompletny problem, ale rozwiązany w czasie liniowym na wykresach ograniczonej szerokości:

http://www.ii.uib.no/~daniello/papers/EqColoring.pdf

— Daniel Marks
źródło

3

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.

— David Eppstein
źródło

1

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

\exists X_{1}, \dots, X_{k} : (IsPartition (X_{1}, \dots, X_{k}) \land \forall X : (MaxClique (X) ⟹ \neg (\exists X_{i} : \forall x \in X : x \in X_{i})))

$\exists X_1, \dots, X_k: (\text{IsPartition}(X_1, \dots, X_k) \land \forall X: (\text{MaxClique}(X) \implies \lnot(\exists X_i: \forall x\in X: x\in X_i)))$

— Jeffε