CSP avec largeur d'hypertree fractionnaire non borné

10

À la SODA 2006, l'article de Martin Grohe et D niel Marx "Résolution des contraintes via des couvertures de bords fractionnaires" ( citation ACM ) a montré que pour la classe des hypergraphes H avec une largeur d'hypertree fractionnée bornée, CSP ( H ) \ in PTIME .a´HHPTIME

Définitions, etc.

Pour une grande vue d'ensemble des décompositions et de la largeur d'arbre standard, voir ici (Merci d'avance, JeffE!).

Soit H un hypergraphe.

Alors pour un hypergraphe H et un mapping γ:E(H)[0,) ,

B(γ)= { vV(H):eV(H),veγ(e)1 }.

De plus, laissez weight ( γ ) = eEγ(e) .

Alors une décomposition fractionnaire en hypertree de H est un triple (T,(Bt)tV(T),(γt)tV(T)) , où:

  • (T,(Bt)tV(T)) est une décomposition arborescente de H , et
  • (γt)tV(T) est une famille de correspondances de E(H) à [0,) st pour chaque tV(T),BtB(γt) .

On dit alors que la largeur de est {poids }.(T,(Bt)tV(T),(γt)tV(T))max(γt),tV(T)

Enfin, la largeur de hyperarborescente fractionnaire de , FHW ( ), est le minimum de la largeur sur toutes les décompositions de hyperarborescente fractionnaires possibles de .HHH

Question

Comme indiqué ci-dessus, si la largeur d'hypertree fractionnaire du graphe sous-jacent d'un CSP est limitée par une constante, alors il existe un algorithme de temps polynomial pour résoudre le CSP. Cependant, il restait un problème ouvert à la fin de l'article lié s'il y avait des familles solubles en temps polynomial d'instances CSP ayant une largeur d'hypertree illimitée. (Je dois également souligner que cette question est complètement résolue dans le cas de la largeur d'arbre bornée par rapport à la limite illimitée ( citation ACM ) sous l'hypothèse que .) Comme il y a un certain temps depuis le premier article lié, en plus, je ne connais pas l'état général de ce sous-domaine, ma question est:FPTW[1]

Sait-on quelque chose sur la (in) tractabilité des CSP sur des graphiques avec une largeur d'hypertree fractionnaire sans limite?
Daniel Apon
la source

Réponses:

8

Vous avez lié à deux articles, tous deux avec des conjectures. Je suppose que vous parlez de la conjecture de Grohe en 2007.

Cette question a reçu une réponse en 2008:

Théorème 5. CSP (C , _) est en NP, mais ni en P ni NP-complet (sauf P = NP). De plus, l'ensemble C peut être décidé en temps polynomial déterministe.00

L'idée est de faire des trous dans les tailles d'instances de CLIQUE, par la même technique de diagonalisation retardée introduite par Ladner pour son théorème. Notez que l'ensemble C contient des cliques arbitrairement grandes, et la largeur d'hypertree fractionnaire d'une -clique est . Il est donc possible d'avoir des CSP de la forme CSP (A, _) qui sont de complexité intermédiaire, où A a une largeur d'hypertree fractionnaire non bornée. Cela répond à la conjecture de Grohe par la négative.0nn/2

Lors de la même conférence, Chen, Thurley et Weyer ont eu un article avec un résultat similaire, mais qui nécessitait des intégrations solides, donc techniquement n'était pas de la bonne forme pour la conjecture.

Enfin, n'importe quelle classe d'instances CSP peut être transformée en une représentation avec une largeur d'hypertree fractionnaire dans le pire des cas. Dans de nombreux cas, cette transformation est de taille polynomiale et peut être effectuée en temps polynomial. Cela signifie qu'il est facile de générer des CSP avec une largeur d'hypertree fractionnaire non bornée, voire une équivalence homomorphique modulo. Ces CSP ne seront pas de la forme CSP (A, _) car les structures cibles sont spéciales, mais elles fournissent une bonne raison pour laquelle les CSP définis en restreignant uniquement les structures source ne sont pas si intéressants: c'est souvent juste trop facile pour masquer la structure arborescente d'une instance CSP en modifiant la représentation afin que la structure source ait une grande largeur. (Ceci est discuté dans le chapitre 7 de ma thèse .)

András Salamon
la source
merci pour la grande réponse. Une question de suivi rapide: Ma lecture de "La complexité de l'homomorphisme et des problèmes de satisfaction des contraintes vus de l'autre côté" est qu'il existe une dichotomie P vs NP-c pour les CSP de la forme CSP (C, _) pour non-hypergraphes d'arité bornée, ai-je raison de le croire? Ou plus précisément - il n'y a pas d'hypothèse / conjecture cachée dans le corollaire 6.1 de cet article que je ne connais pas, n'est-ce pas? Ou encore, la dichotomie est-elle simplement P contre non-P? (Désolé si cela est évident.)
Daniel Apon
2
@Daniel: Cet article ne portait pas tant sur les dichotomies que sur la caractérisation précise des cas à structure restreinte tractable comme ceux de largeur limitée. La largeur limitée était connue pour impliquer traitable, mais la partie clé du papier de Grohe est dans l'autre sens. Une largeur illimitée implique l'intégration de mineurs de grille de taille arbitrairement grande, que l'on peut ensuite utiliser pour coder un problème NP-difficile comme CLIQUE. La conjecture de dichotomie Feder / Vardi pour les CSP est pour les restrictions de type CSP (_, B), qui sont censées être soit en P soit en NP-complet.
András Salamon
@Daniel: Au fait, ce truc n'était certainement pas évident pour moi la première fois que je l'ai lu. Le résumé accrocheur du document de Grohe dans mon commentaire précédent doit beaucoup à Dave Cohen.
András Salamon