CMS C

Question 1

Qu’est-ce que l’hypergraphe d’un réseau de contraintes N = (X, D, C) ?

Answer 1

C’est l’hypergraphe dont les sommets sont les variables du réseaux et les arêtes correspondent à la portée des contraintes

Question 2

Qu’est-ce que CSP({H}, -) où {H} est une famille d’hypergraphes ?

Answer 2

C’est l’ensemble des CSP restreint aux instances dont l’hypergraphe est dans H

Question 3

Propriété de la famille des hypergraphes qui sont des arbres

Answer 3

• Si pour toute variable x, pour toute valeur v ∈ Dom(x) et pour tout voisin y de x, il existe v’ ∈ Dom(y) tel que (x ← v, y ← v’) est cohérent, une solution existe toujours pour le CSP
• Il est polynomial de vérifier la condition précédente
• CSP({H}, -) est polynomial si {H} est la famille des hypergraphes qui sont des arbres

Question 4

Qu’est-ce qu’une décomposition arborescente ?

Answer 4

Soit H un hypergraphe, une décomposition arborescente de H est le couple (T, (B_t)_t∈V(T)) tel que
- T est un arbre
- Tout sac de B_t est un sous-ensemble de sommets de H
- Toute arête de H est entièrement contenue dans au moins un des sacs
- Pout tout sommet de H, les sacs qui le contiennent forment un sous-arbre connexe de T

Question 5

Quelle propriété sur la décomposition arborescente de l’hypergraphe d’un CSP nous permet de savoir si ce dernier est polynomial ?

Answer 5

Soit une instance I de CSP et soit une décomposition arborescente de H(I), s’il est polynomial d’énumérer toutes les affectations possibles pour chaque sac, alors I peut être résolue en temps polynomial

Question 6

Comment résoudre un CSP pour lequel il est possible d’énumérer polynomialement toutes les affectations possibles de chaque sac de la décomposition arborescente ?

Answer 6

• Énumérer les affectations possibles pour chaque sac
• Bottom-up : pour chaque sac en partant des feuilles, supprimer toutes les affectations qui ne peuvent pas être étendues à tous ses enfants
• Renvoyer OUI si et seulement si il y a au moins une affectation restante à la racine

Question 7

Algorithme de résolution par la décomposition arborescente (entrée, sortie, algorithme)

Answer 7

• Entrée : Réseau N, décomposition arborescente de H(N) (T, (B_t)_t∈V(T))
• Sortie : Booléen
• Solve(N, (T, (B_t)_t∈V(T))) :
  
  • Pour tout t ∈ V(T) des feuilles vers la racine :
    
    • S_t = {τ : B_t → D | τ est cohérente}
    • Pour chaque t_c ∈ V(T) enfant de t :
      
      • S_t = {τ ∈ S_t | ∃ τ_c ∈ S_tc, τ ∪ τ_c est cohérent}
  • r = racine(T)
  • Renvoyer S_r != ∅

Question 8

Largeur d’une décomposition arborescente

Answer 8

La largeur de (T, (B_t)_t∈V(T)) est max{|B_t| - 1 | t ∈ V(T)}

Question 9

Largeure arborescente d’un hypergraphe

Answer 9

La largeur arborscente d’un hypergraphe H est la largeur minimale d’une décomposition arborescente de H
(Pour la trouver, il faut construire la décomposition avec les plus petits sacs possible et regarder la taille du plus grand des sacs - 1)

Question 10

Lien entre la largeur arborescente et la complexité d’un CSP

Answer 10

CSP({H}, -) est un temps polynomial si {H} a une largeur arborescente bornée

Question 11

Comme résoudre un CSP à largeur arboresente bornée ?

Answer 11

• En construisant sa décomposition arborescente optimale (polynomiale) puis en appliquant l’algorithme Solve
• En établissant la (k+1) cohérence forte, où k est la largeur arborescente

Question 12

Quel défaut a la largeur arborescente ?

Answer 12

Certains hypergraphes trivialement polynomiaux ont une largeur arborescente non-bornée

Question 13

Qu’est-ce qu’un ensemble de variable k-couvert ?

Answer 13

Un ensemble de variables X’ ⊆ X est k-couvert s’il existe un ensemble de k arêtes e₁, …, e_k telles que X’ ⊆ e₁, …, e_k

Question 14

Nombre d’affectations cohérentes d’un sous-ensemble de variables k-couvert

Answer 14

Si X’ est k-couvert par des contraintes avec au plus t tuples, alors X’ a au plus t^k affectations cohérentes

Question 15

C-width d’une décomposition arborescente

Answer 15

La c-width de (T, (B_t)_t∈V(T)) est le plus petit k tel que chaque sac de B_t est k-couvert

Question 16

Hypertreewidth d’un hypergraphe

Answer 16

La hypertreewidth d’un hypergraphe H est la c-width minimale d’une décomposition arborescente de H

Question 17

Lien entre la hypertreewidth et la complexité d’un CSP

Answer 17

CSP({H}, -) est un temps polynomial si {H} a une hypertreewidth bornée

Question 18

Complexité du calcul d’une décomposition arborescente d’une certainte c-width

Answer 18

Pour k ≥ 2
- NPC de calculer une décomposition arborescente de c-width ≤ k s’il en existe une
- Polynomial de calculer une décomposition arborescente de c-width ≤ 3k ou de conclure que H a une hypertreewidth > k

Question 19

Quel défaut a la hypertreewidth ?

Answer 19

C’est suffisant pour que Solve puisse être appliqué en temps polynomial, mais ce n’est pas entièrement nécessaire

Question 20

Qu’est-ce qu’une couverture d’arêtes fractionnelle d’un hypergraphe ?

Answer 20

Soit H un hypergraphe, une couverture d’arêtes fractionnelle de H est une affectation de poids γ telle que pour tout sommet v, Σ_{e ∈ H tel que v ∈ E} γ(e) ≥ 1

Question 21

Nombre de solutions cohérentes d’un CSP dont l’hypergraphe a une couverture d’arêtes fractionnelle γ

Answer 21

Si I est une instance de CSP et H(I) a une couverture d’arêtes fractionnelle γ de poids total k, I a au plus Π_c∈C |c|^γ(c) ≤ t^k solutions

Question 22

FC-width d’une décomposition arborescente

Answer 22

La fc-width de (T, (B_t)_t∈V(T)) est le plus petit k tel que chaque sac de B_t a une couverture fractionnelle d’arêtes de pois au plus k

Question 23

Fractional hypertreewidth d’un hypergraphe

Answer 23

La fractional hypertreewidth d’un hypergraphe H est la fc-width minimale d’une décomposition arborescente de H

Question 24

Lien entre la fractional hypertreewidth et la complexité d’un CSP

Answer 24

CSP({H}, -) est un temps polynomial si {H} a une fractional hypertreewidth bornée

Question 25

Complexité du calcul d’une décomposition arborescente d’une certainte fc-width

Answer 25

Pour k ≥ 2
- NPC de décider s’il existe une décomposition arborescente de fc-width ≤ k
- Polynomial de calculer une décomposition arborescente de c-width ≤ k³