Site

Archives 2010

Mardi 23 mai - Barnaby Martin (Durham University) - The Computational Complexity of Disconnected Cut and 2K2-Partition
14h amphi E005 (amphi Garcia)
Résumé : For a connected graph G=(V,E), a subset U of V is called a disconnected cut if U disconnects the graph and the subgraph induced by U is disconnected as well. We show that the problem to test whether a graph has a disconnected cut is NP-complete. This problem is polynomially equivalent to the following problems: testing if a graph has a 2K2-partition, testing if a graph allows a vertex-surjective homomorphism to the reflexive 4-cycle and testing if a graph has a spanning subgraph that consists of at most two bicliques. Hence, as an immediate consequence, these three decision problems are NP-complete as well. This settles an open problem frequently posed in each of the four settings.

Vendredi 1er avril - Hubie Chen (Universitat Pompeu Fabra, Barcelone) - Constraint Satisfaction and Local-to-Global Consistency
14h Salle du conseil
Résumé : The constraint satisfaction problem (CSP) is a general search problem where the input is a collection of constraints on a set of variables, and the question is to decide whether or not there is an assignment to the variables satisfying all of the constraints. It can be formalized as the problem of deciding whether or not a primitive positive sentence (a sentence using only the existential quantifier and conjunction) holds on a relational structure.

Local-to-global consistency is an attractive and well-studied property for CSP instances: intuitively, this property holds when performing local (bounded-variable) inferences is sufficient to yield an explicit representation of the solution space.

In this talk, I will engage in a discussion of local-to-global consistency on both finite structures and infinite structures (omega-categorical structures), and present algorithmic consequences of this property for both the CSP and the quantified CSP. I will also report on recent work on this property in the context of temporal constraint languages.

The speaker will attempt to give this presentation in a self-contained fashion, without requiring (for example) any prior knowledge of constraint satisfaction nor consistency.


Jeudi 31 mars - James Gate (Durham University) - Descriptive Complexity Of Optimisation Problems.
13h30 amphi E005 (amphi Garcia)
Résumé : Descriptive Complexity is a field that combines computational complexity with finite mode theory. Its main results are concerned with finding logics that characterise complexity classes. A particular logic L is said to characterise a complexity class K when, for every problem P in K there exists a sentence phi in the logic L, s.t. the input structure A is a yes-instance of P iff A models phi; conversely every sentence phi in the logic L represents a problem in the complexity class K. Logics have been found that characterise most key complexity classes, including P, NP, co-NP and NL, but due to the boolean nature of the model-checking statement ``A models phi'' it comes as no surprise that these are all classes of decision problems.

This talk focuses on optimisation problems and looks at ways to characterise classes of them using logical frameworks. The study of the class of NP-optimisation problems has led to the development of such frameworks, mainly motivated by the search for a syntactic characterisation of their approximation properties. We will look at how these frameworks have been translated to the class Popt of P-optimisation problems and show that a previously proposed framework based on a fragment of second-order logic cannot characterise Popt under the assumption that P is different from NP. Following on from this I will discuss our own route of research, which has led to a framework that characterises Popt and is based on inflationary fixed-point operators. A novel feature of this framework is that the optimal cost of a problem is equal to the inductive depth of the outermost inflationary fixed-point operator.


Jeudi 3 mars - Julien David - Génération exhaustive de multiensembles de mots fréquents.
14h amphi E005 (amphi Garcia)
Résumé : On étudie le problème suivant: partant d'un mot w et d'un quorum q, on souhaite engendrer toutes les façons possibles de partitionner w en ensemble de sous-mots fréquents, un sous-mot étant fréquent s'il possède au moins q occurrences dans la partition. Chaque mot étant associé à un nombre d'occurrences, on s'intéresse à des multiensembles de mots plutôt qu'à des ensembles de mots. Par exemple, partant du mot w=cabcba et d'un quorum q=2, le multiensemble (cb,2),(a,2) est une solution. On présentera un algorithme qui engendre l'ensemble des solutions sans redondance et on montrera que, sauf si P=NP, la complexité de ce problème est exponentielle en la taille de la sortie. On donnera un exemple d'une des applications possibles pour cet algorithme.


Jeudi 24 février - Florent Madelaine - Classification de la complexité des problèmes de satisfaction de contraintes et leurs variantes.
15h amphi E005 (amphi Garcia)
Résumé : Les problèmes de satisfaction de contraintes (CSP) sont étudiés sous des noms différents dans de nombreuses communautés. Lorsque les variables sont à valeurs booléennes, on retrouve des variantes du problème SAT. Lorsqu'on a seulement des contraintes binaires, on peut facilement coder des problèmes de coloriage de graphes comme 3-Col. Les CSPs réapparaissent en combinatoire sous le nom de problèmes d'homomorphisme et se reformulent en théorie des bases de données comme inclusion de requêtes conjonctives. Il y a bientôt 20 ans, Feder et Vardi ont conjecturé que tout CSP est soit dans PTime, soit NP- complet : c'est la /conjecture de la dichotomie/. De nombreux résultats supportent cette conjecture : les travaux de Shaeffer sur SAT (cas des CSPs booléens), le résultat de dichotomie par Hell et Nesetril pour les coloriages de graphes ainsi que des résultats récents de Bulatov (3 éléments, et cas conservatif).

Dans cet exposé, je vais introduire CSP ainsi que les méthodes algébriques ayant permis de prouver la conjecture de Feder et Vardi dans des cas particuliers. Enfin je vais montrer comment ces méthodes peuvent être adaptées pour étudier des extensions quantifiées de CSP.


Jeudi 10 février 2011 - Reza Naserasr - Mapping planar graphs into projective cubes.
13h30 amphi E005
Résumé : A projective cube of dimension k, denoted PC(k) is the graph obtained from the Hypercube of dimension k+1 by identifying antipodal vertices. Projective cube of dimension 2k+1 is a bipartite graph, but PC(2k) is a 4-chromatic graph of odd-girth 2k+1.

In this talk we consider the following question:

Given integers l >= k, what is the smallest possible size of a subgraph of H(l,k) of PC(2k) to which every planar graph of odd-girth at least 2l+1 admits a homomorphism?

We show that this question captures several famous theorems and conjectures in the theory of planar graphs. To conclude the talk with a proof we show that PC(4), which is mostly known as the Clebsch graph, is the smallest triangle-free graph to which every triangle free planar graph admits a homomorphism.


Jeudi 4 novembre 2010 -Extending results from perfect graphs to their generalizations - Annegret Wagler (LIMOS, Clermont II).
14h salle A002
Résumé :Perfect graphs have been extensively studied and turned out to be an interesting and important class of graphs with a rich structure. Most notably, the in general hard to compute graph parameters stability, clique and chromatic number can be determined in polynomial time if the graph is perfect. A canonical question is whether these properties of perfect graphs extend to their generalizations. We present some affirmative results regarding the polynomial time computability of graph parameters for superclasses of perfect graphs: certain classes of rank-perfect and circular-perfect graphs.


Jeudi 14 octobre 2010 -Plongements isométriques de graphes dans les hypercubes - Laurent Beaudou (LIMOS, Clermont II).
14h salle du conseil
Résumé : Lors de ce séminaire, je commencerai par me présenter (en tant que néo-recruté) avant d'aborder un des principaux axes de ma thèse : les plongements isométriques dans les hypercubes. Un graphe H admet un plongement isométrique dans un graphe G s'il existe une application f : V(H) -> V(G) telle que pour toute paire de sommets u,v de H, on a d_H(u,v) = d_G(f(u),f(v)). Alors les propriétés de la métrique de G passent par hérédité à H. Parmi les métriques intéressantes, la métrique l_1 se dégage et son représentant graphique est l'hypercube. Nous aborderons diverses questions qui gravitent autour de ce domaine.


Exposés

edit SideBar

Blix theme adapted by David Gilbert, powered by PmWiki