Séminaire d'Optimisation Combinatoire

Lundi 13 février 2012 à 14h salle A711

Titre : Approximation différentielle des problèmes d'optimisation SNP

Abstract: We revisit the class SNPO of the SNP optimization problems under the differential approximation paradigm, focusing on three questions: what is the largest k such that the k-ary boolean Constraint Satisfaction Problems, CSP are DAPX? more generally, how affine and differential approximation preserving reductions do arrange SNPO problems? in a more structural point of view, what differential approximation guarantee can we expect from local optima? We here show that 3-ary boolean CSP are 0,2146-differential approximable. We also show that any (2k)-ary boolean CSP is equivalent to MaxNAE(2k)Sat, and that any (2k+1)-ary CSP is (r/2)-differential approximable, if MaxNAE(2k)Sat is r-differential approximable. We finally review some interesting observations regarding neighborhood structures, notably: on the one hand, 1-bounded local optima are 1/(n+1)-differential approximate for MaxNAE2Sat; on the other hand, given any solution of any k-ary boolean CSP, its k-bounded neighborhood contains a solution that is (1/n^k)-differential approximate. We therefore leave many questions unanswered, in particular: are 4-ary boolean CSP constantly differential approximable? what about (2k)-ary boolean CSP vs. (2k-1)-ary boolean CSP? However, this talk also aims at providing somme clues in order to go further. The talk is based on a joint work with Jean-François Culus and Frédéric Roupin

Lundi 12 mars 2012 à 14h salle B207

Title: Domination-like problems parameterized by tree-width

Abstract: Parameterized complexity allows one to study more precisely the theoretical complexity of computational problems, by considering one or more problem-specific parameters which may be small compared to the whole size of the input. During this talk, we will present some new results on the parameterized complexity of a generalization of domination-like problems when parameterized by the tree-width of the input graph. The best known FPT algorithm only deals with finite or cofinite sets Sigma and rho; we will give an algorithm which extends this result to ultimately periodic sets Sigma and Rho. On the other hand, we will prove that for some (infinitely many) cases of sets Sigma and Rho, the problem [Sigma,Rho]-Domination becomes W[1]-hard when parameterized by tree-width. This latter result is of particular interest, as very few problems are known not to be FPT when parameterized by tree-width.

Mardi 20 mars 2012 à 11h salle B207

Title: Domination when the stars are out

Abstract: Recently, Chudnovsky and Seymour proved a structural characterization of claw-free graphs, in a series of 7 papers over 250 pages. Whereas their proof is existential, we algorithmize the characterization for claw-free graphs by Chudnovsky and Seymour and give an efficient algorithm for decomposing claw-free graphs. Building on this result, we show that several domination problems are fixed-parameter tractable, and even possess polynomial-sized kernels, on claw-free graphs. To complement these results, we establish these problems are not fixed-parameter tractable on the slightly larger class of graphs that exclude K_{1,4} as an induced subgraph. Our results provide a dichotomy for K_{1,L}-free graphs and show that the problems are fixed-parameter tractable if and only if L = 3. The algorithms we obtain generalize and unify several earlier algorithms for problems on claw-free graphs, and turn the existential decomposition by Chudnovsky and Seymour into an efficient constructive decomposition.(Joint work with Danny Hermelin, Erik Jan van Leeuwen and Gerhard Woeginger.)

Lundi 26 mars 2012 à 14h salle A707

Title: Parameterized complexity, kernelization algorithms and Conflict Packing

Abstract: Parameterized complexity is a theoretical framework measuring the difficulty of decision problems according to the size of the instance and some parameter k related to the problem. A parameterized problem is said to be FPT whenever it can be solved in f(k).poly(n) time, where f() is any computable function. Equivalently, a problem P is FPT iff it admits a kernelization algorithm, i.e. a polynomial time algorithm that given an instance (I,k) of P outputs an equivalent instance (I',k') of P such that |I'| <= g(k) and k' <= k. In this talk, I will present a (simple) parameterized algorithm as well as several kernelization algorithms for the Vertex Cover problem. Next, I will present the Conflict Packing technique, introduced in a joint work with Christophe Paul and Stéphan Thomassé and allowing to obtain polynomial kernels for several modification problems. I will describe in particular how this technique can be applied to the Feedback Arc Set in Tournaments problem, obtaining a kernel with at most 4k vertices. To conclude, I will explain how the ideas used on FAST can be applied to several other problems.

Mardi 27 mars 2012 à 14h salle A711

Titre : Algorithmes paramétrés pour le consensus d'arbres phylogénétiques

Abstract: Dans cet exposé, on considère divers problèmes de consensus entre arbres étiquetés aux feuilles. Etant donnée une collection d'arbres étiquetés T1,...,Tk, le problème du superarbre d'accord consiste à rechercher un arbre étiqueté T qui contienne chaque Ti comme sous-arbre. On décrira dans un premier temps des algorithmes polynomiaux résolvant le problème du superarbre d'accord dans le cas d'arbres enracinés. On étudiera ensuite deux relaxations du problème qui permettent de prendre en compte les désaccords entre arbres sources. La première relaxation, appelée Maximum Rooted Triplet Consistency, s'applique au cas où les arbres sources sont des triplets enracinés, c'est-à-dire des arbres enracinés à trois feuilles. Elle consiste à rechercher un plus grand sous-ensemble des triplets qui admette un superarbre d'accord. La seconde relaxation, appelée Maximum Agreement Supertree, s'applique au cas d'arbres sources quelconques. Elle consiste à rechercher un plus grand sous-ensemble des étiquettes pour lesquelles on peut construire un superarbre d'accord. Bien que ces deux relaxations soient NP-difficiles, on verra qu'elles admettent des algorithmes paramétrés efficaces, dûs à [Guillemot, Mnich, 2010] et [Fernandez-Baca, Guillemot, Shutters, Vakati 2012].

Mercredi 28 mars 2012 à 14h salle A707

Titre : Méthodes pour l'énumération

Résumé : Je vais présenter dans cet exposé des problèmes d'énumérations, c'est à dire qu'on veut lister toutes les solutions d'un problème. Le but est de réaliser cette tâche avec un algorithme de complexité la plus faible possible. Dans ce cadre on s'intéresse à la fois au temps total de l'algorithme et au délai entre deux solutions. Je vais présenter quatres méthodes pour attaquer des problèmes d'énumérations. Ces méthodes ont leur intérêt propre et peuvent (et on été) utilisées pour des problèmes classique de décision ou d'optimisation. Il s'agit de : - représentation de problèmes par des formules (techniques combinatoires et logiques) - représentation de problèmes par des polynômes (algorithmes probabilistes) - décomposition de graphes, matroïdes, hypergraphes (algorithmes à complexité paramétré) - approximation à l'aide de polytopes (marche aléatoire)