Graphes et hypergraphes : complexités algorithmique et algébrique
Institution:
École normale supérieure (Lyon ; 1987-2009)Disciplines:
Directors:
Abstract EN:
The work done during this thesis comes within the scope of hierarchical graph decomposition, and algorithmic and algebraic complexity. The study of branchwidth lead us to look at a problem of hypergraph partitioning. This problem is parameterized by two integers k and l where k is the total number of colors and l is the maximum number of colors a hyperedge is allowed to see. This problem shows surprising variations of complexity. Indeed, for k and l fixed, it is: NP-complete when l>1 and polynomial when l=1 on hypergraphs; NP-complete when l=1 and linear when l>1 on hypergraphs with disjoint hyperedges. This inversion of complexity is partly explained by the weak NP-completeness of the problem when l=1 and the variation in the size of an instance. We also studied the links between hierarchical decompositions and algebraic complexity in collaboration with Uffe Flarup and Pascal Koiran. More precisely, we are interested in classes of complexity from Valiant's model. In this framework, we express polynomials with weighted graph covers such as directed cycle covers, hamiltonian circuits, or perfect matchings. All these covers are related to the permanent and hamiltonian polynomials that are both VNP-complete in Valiant's model (VNP is an algebraic analog to NP). Our work gave us a characterization of the complexity of families of polynomials generated by these covers on particular graph classes. We show notably that on graphs with bounded pathwidth or treewidth the generated polynomials are in fact the whole class of arithmetic formulas. Other results linking classes of graphs and classes of complexity have been obtained.
Abstract FR:
Les travaux effectués pendant cette thèse s'inscrivent dans le cadre des décompositions hiérarchiques de graphes et des complexités algorithmique et algébrique. L'étude de la largeur de branche de graphes nous a conduit à étudier un problème de partitionnement d'hypergraphes. La variante de partitionnement d'hypergraphes en question est paramétrée par deux entiers k et l où k est le nombre total de couleurs et l le nombre maximum de couleurs qu'une hyperarête est autorisée à voir. Ce problème présente des variations de complexité surprenantes puisqu'il est, pour l et k fixés, NP-complet quand l>1 et polynomial quand l=1, sur les hypergraphes ; NP-complet quand l=1 et linéaire quand l>1, sur les hypergraphes avec hyperarêtes disjointes. Cette inversion de complexité s'explique en partie par la NP-complétude faible du problème quand l=1 et la variation dans la taille d'une instance. Nous avons aussi étudié les liens entre décompositions hiérarchiques et complexité algébrique en collaboration avec Uffe Flarup et Pascal Koiran. Plus précisément, nous nous intéressons aux classes de complexité du modèle de Valiant. Dans ce cadre, nous exprimons des polynômes avec des couvertures de graphes pondérés, telles que les couvertures par circuits disjoints, par circuit hamiltonien ou les couplages parfaits qui sont liées au permanent et à l'hamiltonien qui sont tous deux VNP-complets dans le modèle de Valiant (VNP est une analogue algébrique de NP). Nos travaux ont permis de caractériser la complexité des familles de polynômes engendrées par ces couvertures sur certaines classes de graphes. Nous avons notamment montré que sur les graphes de largeur linéaire ou arborescente bornée, les familles de polynômes engendrées sont égales aux formules arithmétiques. D'autres résultats liant des classes de graphes et de complexité ont été obtenus.