Conférenciers Invités
 Stéphane Bessy  Université de Montpellier, LIRMM, France.
 Ricardo Corrêa  ParGO, Universidade Federal Rural do Rio de Janeiro, Brésil.
 Frédéric Havet  COATI, INRIA, I3S (CNRS/Université de NiceSophia Antipolis), France.
 Phillippe Michelon  LIA, Université d'Avignon et des Pays de Vaucluse, France.
 Flavio Miyazawa  Instituto de Computação, Universidade Estadual de Campinas, Brésil.
 Nicolas Nisse  COATI, INRIA, I3S (CNRS/Université de NiceSophia Antipolis), France.
 Jayme Luiz Szwarcfiter  COPPE, Universidade Federal do Rio de Janeiro, Brésil.
 Nicolas Trotignon  Team MC2, LIP, CNRS, École Normale Supérieure de Lyon, France.
Programme scientifique
Lundi 28 mars
09h00 : Plénière  Dijkstra Graphs  Jayme L. Szwarcfiter 
10h00 : Résumés

11h10 : Session de problèmes ouverts 
12h00 : Repas 
14h00 : Groupes de travail 
16h00 : Pause café 
16h15 : Événement social 
Mardi 29 mars
09h00 : Plénière  Recent progress on coloring perfect graphs  Nicolas Trotignon 
10h00 : Résumés

11h30 : Session de problèmes ouverts 
12h00 : Repas 
14h00 : Plénière  On Some Packing Games  Flávio Miyazawa 
15h00 : Groupes de travail 
16h00 : Pause café 
16h30 : Discussions de progrès des problèmes posés 
Mercredi 30 mars
09h00 : Plénière  Solving the classification problem with combinatorial optimization tools  Ricardo Corrêa 
10h00 : Résumés

11h30 : Session de problèmes ouverts 
12h00 : Repas 
14h00 : Plénière  Antistrong digraphs  Stéphane Bessy 
15h00 : Groupes de travail 
16h00 : Pause café 
16h15 : Événement social 
Jeudi 31 mars
09h00 : Plénière  Revisiting Resolution Search  Phillippe Michelon  
10h00 : Résumés  
11h10 : Session de problèmes ouverts  
12h00 : Repas  
14h00 : Plénière  Treedecompositions with metric properties on the bags  Nicolas Nisse  
15h00 : Groupes de travail  
16h00 : Pause café  
16h30 : Discussions de progrès des problèmes posés  
Vendredi 01 avril
09h00 : Plénière  Subdivisions of oriented cycles in digraphs with large chromatic number  F. Havet 
10h00 : Discussions finale de résultats 
12h00 : Repas 
13h00 : Transfert à Fortaleza (Aéroport Pinto Martins) 
Résumés des Plénières
Jayme L. Szwacfiter
Titre: Dijkstra Graphs
Résumé: We revisit a concept that has been, in a way, central in some early stages of computer science, that of structured programming. Basically it consists of a set of rules that an algorithm has to follow, in order to acquire a structure that is desired in many aspects. In spite of the fact that much has been written about structured programming, an im portant issue has been left unanswered: given an arbitrary algorithm, described by its flowchart, decide whether or not it is structured, that is, whether or not it follows the stated principles for structuring. By employing graph theoretic tools and algorithmic techniques, we for mulate an efficient algorithm for answering this question. In order to do so, first we introduce the class of graphs which correspond to the structured algorithms, which were then been named as Dijkstra Graphs. Our recognition problem then became to recognize graphs of this class. Further, we describe an efficient isomorphism algorithm for Dijkstra graphs. Both the recognition and isomorphism algorithms have complexity O(n^2), for graphs with n vertices.
Joint work with Lucila M. Bento, Davidson Boccardo, Raphael C. Machado and Vinicius G. Sá.
Nicolas Trotignon
Titre: Recent progress on coloring perfect graphs
Résumé: Finding a combinatorial algorithm that would color in polytime any input perfect graph is perhaps the most well known open question about perfect graphs. In the last years, several progress have been made in this direction, by different authors. In particular : how to use decompositions (2joins, and in some cases balanced skew partitions), how to improve the known decomposition theorems (in the squarefree case). Results of the following authors (in some case jointly with the speaker) will be presented : Maria Chudnovsky, Aurélie Lagoutte, Irene Lo, Frédéric Maffray, Paul Seymour, Sophie Spirkl, Krisitina Vuskovic.
Flávio Miyazawa
Titre: On Some Packing Games
Résumé: In the classical bin packing problem, we have a list of items, each of them with a specific size, and bins of bounded capacity, and the objective is to obtain a packing of the items into the minimum number of bins. We consider gametheoretic versions of this problem, where each player controls exactly one item and is charged with a cost defined as the ratio between the area of the item and the occupied area of the respective bin. Initially, a set of items is packed in bins and, one at a time, players selfishly move their items from one bin to another, in order to minimize the costs they are charged. In this game, the social cost is the number of used bins, and the optimal social cost is the minimum number of bins needed to pack the given items. We present some known results and ours for variants of one or more dimensions, considering the price of anarchy, coalitions and convergence time to attain Nash equilibrium. Some of the presented results are joint work with C.G. Fernandes, C. E. Ferreira, and Y. Wakabayashi.
Ricardo Corrêa
Titre: Solving the classification problem with combinatorial optimization tools
Résumé: In the last 30 years, the availability of massive amounts of data in electronic form have led to the development of the field of data mining. A central problem in this field is data classification which consists in detecting a pattern in a set of classified data (referred to as samples) in order to predict the classification of unclassified ones. While continuous optimization methods have been widely used to solve the classification problem, the common sense was created that combinatorial optimization methods for this problem are not tractable in practical computational settings. More recently, the significant advances in integer programming tools and the vertiginous increases in computational power have motivated some authors to question this common sense. Investigation conducted by different authors in distinct contexts show that combinatorial approaches to the classification problem has been becoming a promising alternative. In this talk, we give an outline of mixed linear programming and 01 integer programming formulations for the classification problem in cases meeting the following assumptions: (a) there is an underlying pattern to the set of samples that can be expressed by some notion of convex sets; and (b) the data set contains outliers, which are not previously identified in the data set. We focus our attention in two particular cases of convexity. The first one is the natural geometric (or Euclidean) convexity notion, which is used in all studies in the literature (to the best of our knowledge). In this case, it is assumed that the samples are represented by vectors of real numbers in a multidimensional space and it is expected that the underlying pattern is associated with the spatial location of these samples. We give some preliminary computational results to show that this is a promising approach with respect to the quality of the solution. The second case is exploratory, since it has not been studied in the literature. It consists of stating the classification problem in terms of geodesic convexity in graphs, whose motivation is twofold. Firstly, it is of theoretical interest since it concerns the possibility of establishing new problems on graphs. Secondly, it models the underlying pattern by means of a binary relation on the set of samples. Consequently, the samples need not to be formed by numerical values and the classification problem becomes purely combinatorial.
Stéphane Bessy
Titre: Antistrong digraphs
Résumé: An antidirected trail in a digraph is a trail (a walk with no arc repeated) in which the arcs alter nate between forward and backward arcs. An antidirected path is an antidirected trail where no vertex is repeated. We show that it is NPcomplete to decide whether two vertices x, y in a digraph are connected by an antidirected path, while one can decide in linear time whether they are connected by an antidirected trail. Indeed this can be done easily by looking for an (x,y)path in the adjacency bipartite of the input digraph. Motivated by this observation, we say that a digraph is antistrong if its adjacency bipartite is con nected. We study natural algorithmic questions on antistrong digraphs. Some results derive easily from the definition (eg. checking karcantistrongness, or computing the minimum number of arcs to add to be antistrong....), other are more difficult to establish. In particular, we use results from matroid theory to characterize graphs which admit an antistrong orientation and give a polynomial time algorithm for constructing such an orientation when it exists. In this talk, I will present these notions and results and also give some problems and conjectures related to this area.
This is joint work with J.BangJensen, M.Kriesell and B.Jackson
Phillippe Michelon
Titre: Revisiting Resolution Search
Résumé: In 1997, V. Chvatal proposed an alternative method to the classical branchandbound approach for solving Combinatorial Optimization problems, that he named "Resolution Search". So far, Resolution Search has been under used and almost ignored. Among others reasons that can explain this phenomena, there is the efficiency of the Integer and Linear Programming codes that makes difficult the emergence of new methods in a short period of time. Nevertheless, it is somehow unreasonable to only have one method, whose limitations in space and time are known, for solving the numerous and tremendously important combinatorial optimization industrial problems. In this talk, we will revisit the Resolution Search approach and try to point out some research directions that could be of interest. In particular, we will point out that Resolution Search is actually a rich (and exact) method that allows to build bridges between exact and heuristic methods, since it can be seen as a multistart descent method while maintaining a set of (partial) solutions.
Nicolas Nisse
Titre: Treedecompositions with metric properties on the bags
Résumé: Treedecompositions of graphs are a way to study and model topological structure of graphs. Such decompositions have many applications for designing algorithms that allow to efficiently solve difficult (NPhard in general) problems in graphs (e.g., coloring, dominating set, cover...). The classical approach consists in decomposing graphs in small “pieces” (subsets of vertices) that may be organized along the minimal separators of the graph. Another approach is to minimize metric properties of these pieces instead of their size. For instance, minimizing the bags' diameter (resp., radius) correspond to the treelength (resp. treebreadth) We survey some recent results on the computational complexity of these parameters and their relationship with the treewidth of graphs.
This is joint work with D. Coudert, G. Ducoffe and S. Legay
Frédéric Havet
Titre: Subdivisions of oriented cycles in digraphs with large chromatic number
Résumé: An oriented cycle is an orientation of a undirected cycle. We first show that for any oriented cycle C, there are digraphs containing no subdivision of C (as a subdigraph) and arbitrarily large chromatic number. In contrast, we show that for any C is a cycle with two blocks, every strongly connected digraph with sufficiently large chromatic number contains a subdivision of C. We prove a similar result for the antidirected cycle on four vertices (in which two vertices have outdegree 2 and two vertices have indegree 2).
This is joint work with N. Cohen, W. Lochet and N. Nisse.