Les anciens exposés de 2012

Lundi 13 février 2012 à 14h salle A711

Sophie Toulouse, LIPN, Université Paris 13

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

Mathieu Chapelle, LIFO, Université d'Orléans

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

Matthias Mnich, Max-Planck-Institut für Informatik, Saarbrücken

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

Anthony Perez, LIFO, Université d'Orléans

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

Sylvain Guillemot, Iowa State University

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

Yann Strozecki, LRI, Université d'Orsay

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)

Lundi 30 avril 2012 à 14h salle C516

Barnaby Martin, Durham University

Title: Parameterized Proof Complexity

Abstract: The origins of Proof Complexity lie in the program of Cook and Reckow,
who aimed to separate P and NP (actually, coNP and NP) by proving that
no propositional proof system is polynomially bounded. Having failed
to obtain such a general result, students of Proof Complexity have
instead focused on proving that stronger and stronger proof systems
are not polynomially bounded. Such lower bounds are known for systems
such as Resolution and Bounded-depth Frege.
We propose a proof-theoretic approach for gaining evidence that
certain parameterized problems are not fixed-parameter tractable. We
consider proofs that witness that a given propositional CNF formula
cannot be satisfied by a truth assignment that sets at most k
variables to true, considering k as the parameter (we call such a
formula a parameterized contradiction). One could separate the
parameterized complexity classes FPT and W[2] by showing that there is
no fpt-bounded proof system, i.e., that there is no proof system that
admits proofs of size f(k).n^{O(1)} where f is a computable function
and n represents the size of the propositional formula.
We survey results in the area, taking in the parameterized versions of
tree-Resolution, Resolution and bounded-depth Frege.

Lundi 11 juin 2012 à 14h salle A307

Thomas McCormick
, Sauder School of Business, University of British Columbia, et Britta Peis, TU Berlin

Title: Separation of Series Constraints for One-Machine Scheduling with Precedence

Abstract: A 1991 paper by Queyranne and Wang proposed three classes of valid constraints for the convex hull of feasible completion times for schedules on a single machine subject to precedence constraints. These classes are called the parallel constraints, serial constraints, and Z constraints. These constraints have been very useful in many contexts. Queyranne and Wang showed how to separate the parallel constraints, but the complexity of separating the serial and Z constraints has remained open. Here we show that it is NP Hard to separate even a very special subclass of serial constraints. We also develop a fast, parametric way to find an earliest feasible deadline for a subset of jobs, and use it to show that separation is polynomial when the precedence constraints are series-parallel. We also note that there is a compact extended formulation of the problem by Wolsey, and in this context separation of both series and parallel constraints becomes trivial. It is surprising that an NP Hard separation problem can "hide" within an extended formulation where separation is much easier. We further consider the case of two-dimensional precedence constraints, whose underlying problem is solvable in polynomial time. We show how to separate the serial constraints in this case as well. Joint work with A. Ridha Mahjoub, and Y. Kobayashi.

Jeudi 21 juin 2012 à 13h salle A301

Flavia Bonomo, Universidad de Buenos Aires

Title: Bounded coloring of co-comparability graphs and the pickup and delivery
tour combination problem

Abstract: The Double Traveling Salesman Problem with Multiple Stacks is a vehicle
routing problem in which pickups and deliveries must be performed in two
independent networks. The items are stored in stacks and repacking is not
allowed. Given a pickup and a delivery tour, the problem of checking if
there exists a valid distribution of items into s stacks of size h that is
consistent with the given tours, is known as Pickup and Delivery Tour
Combination (PDTC) problem.
In this work, we show that the PDTC problem can be solved in polynomial
time when the number s of stacks is fixed but the size of each stack is
not. We build upon the equivalence between the PDTC problem and the bounded
coloring (BC) problem on permutation graphs: for the latter problem, s is
the number of colors and h is the number of vertices that can get a same
color. We show that the BC problem can be solved in polynomial time when s
is a fixed constant on co-comparability graphs, a superclass of permutation
graphs. To the contrary, the BC problem is known to be hard on permutation
graphs when h > 5 is a fixed constant, but s is unbounded.
This is a joint work with Gianpaolo Oriolo (Università di Roma "Tor
Vergata", Italia) and Sara Mattia (IASI-CNR, Italia).

Lundi 2 juillet 2012 à 14h salle A707

Vadim Lozin, Warwick University

Title: Boundary properties of the satisfiability problems

Abstract: The satisfiability problem is known to be NP-complete in general
and for many restricted instances, such as formulas with at most
3 variables per clause and at most 3 occurrences per variable,
or planar formulas. The latter example refers to graphs representing
satisfiability instances. These are bipartite graphs with vertices
representing clauses and variables, and edges connecting variables
to the clauses containing them.
Finding the strongest possible restrictions under which a problem
remains NP-complete is important for at least two reasons.
First, this can make it easier to establish the NP-completeness
of new problems by allowing easier transformations. Second,
this can help clarify the boundary between tractable and intractable
instances of the problem. In this talk, we address the second issue
and reveal the first boundary property of graphs representing
satisfiability instances.

Lundi 8 octobre 2012 à 14h en salle A707

Florian Sikora, LAMSADE

Titre : Recherche de motifs dans des graphes colorés

Résumé:
Décider si un motif existe dans un graphe coloré sur les sommets est
une tâche importante pour certaines applications en biologie. Une
grande partie de la littérature est dédiée à la recherche de motifs
dans ces graphes lorsqu'une topologie est donnée sur le motif (chemin,
arbre, graphe...).
Plus récemment, Lacroix et al. ont établi un nouveau problème où le motif n'a
pas de topologie mais est simplement un (multi) ensemble de couleurs. On
cherche alors un sous-graphe connexe contenant cet ensemble de
couleurs. On présentera lors de cet exposé des résultats sur la
complexité de ce problème, essentiellement sous l'angle de la
complexité paramétrée.

Lundi 12 novembre 2012 à 14h15 en salle A711

Diodato Ferraioli , LAMSADE

Title: Logit Dynamics for Strategic Games: Mixing time and Metastability

Abstract: Logit Dynamics [Blume, Games and Economic Behavior, 1993] is a randomized best response dynamics for strategic games: at every time step a player is selected uniformly at random and she chooses a new strategy according to a probability distribution biased toward strategies promising higher payoffs. This process defines an ergodic Markov chain over the set of strategy profiles of the game whose unique stationary distribution is the long-term equilibrium concept for the game. In [Auletta+, SPAA, 2011], bounds on the rate of convergence of the logit dynamics to this equilibrium are given. However, there are games for which the convergence time is large (e.g. exponential in the number of players) and thus the stationary distribution loses its appeal as equilibrium concept, and the transient phase of the Markov chain becomes important. In several cases it happens that on a time-scale shorter than convergence time the chain is quasi-stationary, meaning that it stays close to some small set of the state space, while in a time-scale multiple of the mixing time it jumps from one quasi-stationary configuration to another; this phenomenon is usually called metastability. In this talk, a quantitative definition of metastable probability distributions for a Markov chain is given and the metastability of the logit dynamics is analyzed for some classes of games.

Lundi 26 novembre 2012 à 14h15 en salle B117

Aris Pagourtzis, National Technical University of Athens

Title: The Blue-Red Matching problem: approximations, exact solutions, and
applications

Abstract: We will discuss earlier as well as some recent results for the
Blue-Red Matching problem: given a graph with red and blue edges, and a
bound W, find a maximum matching consisting of at most W edges of each
color. We will first prove that Blue-Red Matching is at least as hard as
the well-known Exact Matching problem (Papadimitriou and Yannakakis, 1982),
for which it is still open whether it can be solved in polynomial time.
Next we will present two fast approximation algorithms for Blue-Red
Matching as well as a randomized (RNC) one that solves it exactly whp. We
will finally show the applicability of our results to the problem of
routing and assigning wavelengths to a maximum number of requests in
all-optical rings and discuss open questions and ideas for further
research.
(Based on joint work with Christos Nomikos and Stathis Zachos)

Mercredi 5 decembre 2012 à 14h15 en salle A707

Bernhard von Stengel, London School of Economics

Title: Pathways to Equilibria, Pretty Pictures and Diagrams (PPAD)

Abstract: Existence of an equilibrium in various economic models can
be shown to exist by following a certain combinatorially
defined path, for example of edges of a labeled polytope
similar to the simplex algorithm for linear programming.
In addition, such a path has a direction that defines the
"index" of an equilibrium. Examples include Sperner's
lemma about completely labeled simplices and Nash equilibria
in games. We present a general model of "pivoting systems"
that shows the essence of the path-following and the
directedness argument. We also present a connection of
bimatrix games where the paths are exponentially long with
signed perfect matchings in Euler graphs, and an algorithm
that gives a polynomial-time "shortcut" for these paths.
We also present a concept of orientation for the "Euler
complexes" or "oiks" introduced by Edmonds, which
generalizes the orientability of abstract simplicial
manifolds. Our exposition uses colorful pictures and
examples wherever possible.
(Joint work with Marta Maria Casetti, Julian Merschen and
Laszlo Vegh.)

Mardi 11 decembre 2012 à 14h15 en salle A307

Carola Winzen, LIAFA

Title: Query Complexity and Mathematician's Mastermind

Abstract: After a short introduction into query complexities, we survey old and
new results for a Mathematician's version of the classic 2-player board
game Mastermind. For the game with n positions and k=n colors, we show that the
Codebreaker has a winning strategy that uses only O(n loglog n)
guesses for identifying the secret code. This improves the previously
best known bounds of Chvatal (Combinatorica, 1983), Goodrich
(Information Processing Letters, 2009), and others, which are all of
order n log n. We also present a new variant of the Mastermind game - the Hidden
Permutation problem. We present matching upper and lower bounds for this
problem, both for deterministic and randomized query schemes. The
deterministic query complexity is Theta(n log n), which,
surprisingly, improves to Theta(n log log n) in the randomized setting.
The result on Mastermind is joint work with Benjamin Doerr (Max Planck
Institute for Informatics), Reto Spoehel (MPI Informatics), and Henning
Thomas (ETH Zuerich), and is to appear at SODA 2013. The result on the
Hidden Permutation problem is joint work with Peyman Afshani (MADALGO
Aarhus), Manindra Agrawal (IIT Kanpur), Benjamin Doerr, Kasper Green
Larsen (MADALGO Aarhus), and Kurt Mehlhorn (MPI Informatics).