Problème de clique sur les graphes fixes

Comme nous le savons, la fonction $k$ -clique $CLIQUE(n,k)$ prend un sous-graphe ( couvrant ) d'un graphe sommet complet , et les sorties si contient une -clique . Les variables dans ce cas correspondent aux arêtes de K n . On sait (Razborov, Alon-Boppana) que, pour 3 ≤ k ≤ n / 2 n K n 1 G k$G\subseteq K_n$$n$$K_n$$1$$G$$k$$K_n$$3\leq k\leq n/2$, cette fonction nécessite des circuits monotones d'une taille d'environ $n^k$ .

Mais que se passe-t-il si nous prenons un graphe fixe $G\subseteq K_n$ , et considérons la fonction booléenne monotone $CLIQUE(G,k)$ , qui prend un sous-ensemble $S\subseteq [n]$ de sommets, et génère $1$ si quelques $k$ sommets en $S$ former une clique dans $G$ . Les variables dans ce cas correspondent à des sommets de $K_n$ , et la fonction est juste la fonction clique standard mais limitée à l' étenduesous - graphes d'un fixe graphe .$G$

1. Existe- t-il des graphes -vertex G pour lesquels C L I Q U E ( G , k ) nécessite des circuits monotones de taille supérieure à n O ( log n ) ? Je suppose que non. $n$$G$$CLIQUE(G,k)$$n^{O(\log n)}$

2. Is un problème NP-dur pour une séquence de graphes ( G n : n = 1 , 2 ... ) ? Je suppose que non. $CLIQUE(G_n,k)$$(G_n\colon n=1,2\ldots)$

Notez que si sont toutes des cliques maximales dans G , alors C L I Q U E ( G , k ) peut être calculé comme un OU de r fonctions seuil- k , dont le i- ème teste si | S a ∩ C i | ≥ k . Ainsi, si r = p o l y ( n $C_1,\ldots,C_r$$G$$CLIQUE(G,k)$$r$$k$$i$$|S_a\cap C_i|\geq k$$r=poly(n)$, alors tout le circuit est de taille polynomiale. Mais qu'en est-il des graphiques avec un nombre exponentiel de cliques maximales? (Une clique est maximale si aucun sommet ne peut y être ajouté.)

Il est possible "d'incorporer" dans C L I Q U E ( H , k ) pour un graphe H particulier sur n = 2 m sommets. En particulier, Bollobas et Thomason (1981) ont montré que, si H est un graphe de Hadamard dont les sommets sont des sous-ensembles de [ m ] , et que deux sommets u et v sont adjacents ssi $CLIQUE(m,k)$$CLIQUE(H,k)$$H$$n=2^m$$H$$[m]$$u$$v$est pair, alors H contient une copie isomorphe de chaque graphe G sur m sommets. Peut-on combiner ce fait avec la limite inférieure de Razborov (d’environ m k ) pour C L I Q U E ( m , k ) pour conclure que C L I Q U E ( H , k ) nécessite des circuits monotones d’une taille d’environ m k ? Un problème potentiel ici est que, même si le graphique$|u\cap v|$$H$$G$$m$$m^k$$CLIQUE(m,k)$$CLIQUE(H,k)$$m^k$$H$"contient" tous les graphes -vertex, ces graphes ne sont pas sur le même ensemble de sommets. Et l'argument de Razborov exige que les entrées positives et négatives ( k -cliques et compléments de graphes complets ( k - 1 ) -parties) soient des graphes sur le même ensemble de sommets. De plus, toutes les entrées positives ( k -cliques) ne sont que des copies isomorphes d'une même k -clique fixe .$m$$k$$(k-1)$$k$ $k$

3. Des idées? Quelqu'un a-t-il vu ce type de problèmes pris en considération? Je veux dire, les problèmes de décision pour les sous-graphiques d'un graphique fixe . Ou, disons, le problème SAT pour les sous-CNF d'un CNF fixe (satisfaisable) (obtenu en supprimant certains littéraux)?

Motivation: des problèmes de ce type sont liés à la complexité des algorithmes d'optimisation combinatoire. Mais ils semblent être intéressants en soi. Pourquoi devrions-nous rechercher des algorithmes efficaces sur tous les graphiques? En réalité, nous nous intéressons généralement aux propriétés de petits morceaux d'un (grand) graphe (réseau de rues dans un pays, ou facebook, etc.).

Remarque 1: Si le graphe est bipartite , alors la matrice d'incidence sommet-bord des inégalités x u + x v ≤ 1 pour tous ( u , v ) ∉ E est totalement unimodulaire, et un peut résoudre le problème de clique sur les sous-graphes induits de G via une programmation linéaire. Ainsi, pour les graphes bipartis G , C L I Q U E ( G , $G=(L\cup R,E)$$x_u+x_v\leq 1$$(u,v)\not\in E$$G$$G$ possèdeun petit circuit (quoique non monotone). $CLIQUE(G,k)$

Remarque 2: Une indication, que dans le cas des graphes bipartites , la réponse à la question 1 "devrait" effectivement être NON est que le jeu monotone de Karchmer-Wigderson suivant sur G n'a besoin que de O ( log n ) bits de communication. Que k soit le plus grand nombre de sommets dans un sous - graphe biparti complet de G . Alice obtient un ensemble A de nœuds rouges, Bob un ensemble B de nœuds bleus tels que | A | + | B | > k . Le but est de trouver un non-bord entre $G$$G$$O(\log n)$$k$$G$$A$$B$$|A|+|B|>k$$A$et .$B$

Nous avons fait quelques recherches sur le problème de prouver dans une résolution arborescente si un graphe fixe a une clique de taille k (où k est généralement petit). En particulier, nous avons découvert que des réfutations de taille n Ω ( k ) sont nécessaires pour une grande classe de graphes.$G$$k$$k$$n^{\Omega(k)}$

Vous pouvez trouver le document Complexity Parameterized of DPLL Search Procedures sur ce lien .

Je pense que ce document peut répondre à vos questions: http://arxiv.org/abs/1204.6484

L'article définit des familles de problèmes NP durs 3SAT, de sorte que la structure de la formule est fixe pour chaque n, et l'entrée est la polarité de la formule.

En utilisant la réduction standard de 3SAT à CLIQUE (chaque clause 3CNF définit un ensemble de 8 affectations possibles (ou 7 affectations satisfaisantes), avec des arêtes entre les affectations non conflictuelles), il existe un graphique tel qu'après avoir supprimé un sommet pour chaque clause, il est NP difficile à trouver la clique maximale (ou même à approximer sa taille, en utilisant des produits graphiques ou des produits graphiques dérandomisés)

en ce qui concerne le troisième trimestre, il existe des travaux empiriques sur le «réseau principal» et les «portes dérobées» possibles des problèmes SAT. l'épine dorsale est l'ensemble des littéraux qui sont vrais dans chaque affectation satisfaisante. Une porte dérobée sur un problème SAT est un ensemble (espérons-le petit) de variables qui fournissent un «raccourci» pour résoudre le problème. ces deux structures seraient probablement utiles et / ou essentielles pour comprendre ce que vous appelez des "sous-CNF" ou CNF avec certaines variables supprimées. mais aussi DP, l'algorithme de davis putnam peut être considéré comme explorant systématiquement de nombreux "sous-CNF" du CNF pour le résoudre.

[1] Backbones and Backdoors in Satisfiability par Kilby et al