Independent Sets in Graphs

• Instructors: Édouard Bonnet, Jean-Florent Raymond, Stéphan Thomassé, Nicolas Trotignon and Rémi Watrigant

• Prerequisites: basic notions in graph theory, algorithms, complexity theory, linear algebra and discrete probability.

• Objective: From its very close relationship to SAT, the maximum independent set problem (i.e. finding the maximum size α(G) of a set of pairwise non connected vertices in a graph G) is certainly the most popular computational question in graph algorithms. This very simple notion is also a deeply studied parameter from a structural point of view. It is indeed the starting point of several fields in combinatorics (like Ramsey theory) and combinatorial optimisation (perfect graphs for instance). In this course independent sets will be the common thread to discuss these related topics. This course will survey the main aspects of characterizing structurally and (efficiently) computing maximum independent sets and will provide (a fraction of) the necessary set of tools needed for this journey

• Course outline:
  
  1) Independent sets from the combinatorial point of view.
  

  • Extremal combinatorics is certainly the first field in which maximum independent sets is widely studied, with Turan and Ramsey theorem. The main idea here is to study how α(G) is influenced by other parameters such as the clique number or the number of edges. This domain was extremely influencial in the development of discrete probabilities. We will review some probabilistic techniques.
  • From the optimization point of view, a question arose when considering for which graphs maximum independent set could be well characterized. It appeared that bipartite graphs, their complements, their line graphs and complements are well-behaved, and Berge proposed its celebrated class of perfect graphs encompassing all of these properties. From a polyhedral point of view, the polytope of independent sets of a perfect graph is characterized by the so-called clique constraints, and from the structural point of view, perfect graphs avoid odd induced cycles and their complements. Remarkably, the converse holds and is known as "The strong perfect graph theorem". In this part some tools of polyhedral methods and graph decompositions (à la Berge) will be explored.
  • As independent sets are too complex in the general case, we will restrict ourselves to specific classes of graphs (closed w.r.t. induced subgraphs), or equivalently graphs avoiding some specific substructures. One of the most classical restriction one can impose on graphs concerns its cycles (think of bipartite graphs for instance as avoiding odd cycles). Remarkably, computing alpha is easy (or at least easier) when forbidding disjoint cycles (with or without parity constraints). The tools here are surprisingly diverse, like Erdos-Posa property, but also width-parameters such as tree-width. A particularly nice feature here is that geometrical problems can often be translated into restricted graph classes and solved in this context.
  
  2) Independent sets from the computational point of view.
  
  
  • The computation of alpha is hard to approximate (PCP theorem) for general graphs. We will restrict ourselves to classes in which either we can reach an exact solution, or at least get some fixed constant approximation or some PTAS. We will also investigate the parameterized complexity landscape of computing α. We will review here a very large diversity of algorithm paradigms, even though dynamic programming will certainly be our best pick.
  • Linear and semi-definite optimization are also very useful tools in this field. Using SDP for instance, the independence number of a perfect graph can be computed by the Lovasz theta function, computed on its edge-complement (and no known combinatorial algorithm is known). Furthermore, SDP is the main tool for the Shannon capacity of a graph G (that is the asymptotic independence number of the powers of G).

• Validation: There will be a written final exam and either a homework assignment or an oral presentation of a research article.

• Bibliography: