Problème de clique sur les graphes fixes

21

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 kGKnnKn1GkKn3kn/2, cette fonction nécessite des circuits monotones d'une taille d'environ nk .

Mais que se passe-t-il si nous prenons un graphe fixe GKn , et considérons la fonction booléenne monotone CLIQUE(G,k) , qui prend un sous-ensemble S[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 Kn , 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. nGCLIQUE(G,k)nO(logn)
2. Is un problème NP-dur pour une séquence de graphes ( G n : n = 1 , 2 ... ) ? Je suppose que non. CLIQUE(Gn,k)(Gn:n=1,2)

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 aC i | k . Ainsi, si r = p o l y ( n )C1,,CrGCLIQUE(G,k)rki|SaCi|kr=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)Hn=2mH[m]uvest 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 H|uv|HGmmkCLIQUE(m,k)CLIQUE(H,k)mkH"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 .mk(k1)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 v1 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 , kG=(LR,E)xu+xv1(u,v)EGG 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 AGGO(logn)kGAB|A|+|B|>kAet .B

Stasys
la source
plus de réflexions (1) il semble que vous pourriez obtenir un résultat similaire en définissant une fonction de "filtre" qui a le même nombre de variables que les bords et les bords de "filtres" du graphique fixe basé sur les valeurs 0/1 des variables booléennes ... .? cela pourrait diminuer quelque peu l'analyse en raison de la construction du graphe induit qui se déplace des bords aux sommets. (2) une question clé plus simple est intégrée à votre question et mérite à elle seule d'être abordée. quels sont les graphiques avec des cliques maximales exponentielles? l'exemple de hadamard peut ne pas suffire car il est si "grand".
vzn
cherchait quelque chose de vaguement similaire récemment et a traversé ce factoïde intéressant: "Une décomposition de clique gourmande d'un graphique est obtenue en supprimant les cliques maximales d'un graphique un par un jusqu'à ce que le graphique soit vide. Nous avons récemment montré que toute décomposition de clique gourmande de un graphe d'ordre a au mostn n 2 / 4 cliques « . --mcguinnessnn2/4
vzn
@vzn: À votre dernière question. Il y a une construction simple (ne me souviens pas de qui). Prenez copies des "anti-trianges" de sommets disjoints (triplets de sommets sans arêtes entre eux) et placez des arêtes entre tous les sommets de deux anti-tringles. Le nombre de cliques maximales est alors de 2 n / 3 , ce qui est optimal (plus rien n'est possible). n/32n/3
Stasys
@vzn: Sur le résultat McGuinness. Si j'ai bien compris, il décompose tous les bords en un petit nombre de cliques maximales (taille) disjointes. Mais il peut arriver que la clique maximale du sous-graphique induit ne se trouve dans aucun d'entre eux. Pourtant, le résultat semble aller dans la "bonne direction".
Stasys
À propos de la remarque 2 : lorsque vous dites rechercher une clique dans un bipartite, voulez-vous dire un bipartite complet?
MassimoLauria

Réponses:

10

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.GkknΩ(k)

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

MassimoLauria
la source
1
Un très joli résultat! En fait, ma question s'est posée en essayant de montrer le même résultat pour des réfutations de plan de coupe en forme d'arbre (CP) pour le problème (clique). Pour les dérivations arborescentes, nous avons deux (seulement?) Outils: (1) des arguments de complexité de communication et (2) des jeux Player-Delayer de Pudlak et Impagliazzo. La remarque 2 implique que (1) échouera (de manière probante) pour le problème Clique. Y a-t-il une analogie de (2) dans le cas des preuves CP?
Stasys
6

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)

user15669
la source
2

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

vzn
la source
SS