Enumeration complexity and matroid decomposition
Institution:
Paris 7Disciplines:
Directors:
Abstract EN:
This thesis is made of two parts, on the one hand the study of enumeration algorithms and their complexity and in the other hand the model checking of Monadic second order properties over decomposable matroids. The enumeration is studied first from a structural point of view: natural complexity classes are defined and their relation studied. We also try to explain the effect of ordering in enumeration and of some set operations over the solutions. Then, we present several algorithms to enumerate the monomials of polynomials given either as black boxes or circuits. They can be used to solve more classical combinatoric problems such as the enumeration of spanning hypertrees of a 3-uniform hypergraph. In the second part, we present an alternative tree decomposition of representable matroids of bounded branch-width. It enables to locally express the dependency property and thus to give a linear time algorithm to check MSO properties over these structures. We also obtain a linear delay enumeration algorithm of the objects definable in MSO, such as the circuits of a matroid. This decomposition can easily extended to other classes and even by further abstraction to hypergaphs.
Abstract FR:
Ce travail comporte deux parties principales, d'une part l'étude des algorithmes d'énumération et leur complexité et d'autres part la vérification pour des hypergraphes et des matroïdes décomposés de propriétés exprimés en logique monadique du second ordre. L'énumération est d'abord étudié d'un point de vue structurel : on donne les définitions des classes de complexité les plus naturelles et leur relations sont étudiées. On tente d'expliquer le rôle de l'ordre dans cette problématique ainsi que l'effet d'opérations ensemblistes sur les solutions. Puis on donne une série de résultats sur l'énumération des monômes de polynômes donnés soit comme des boîtes noires, soit comme des circuits. Les algorithmes développés peuvent ensuite être utilisés pour résoudre des problèmes combinatoires plus classiques, tel que l'énumération des hyperarbres couvrants d'un hypergraphe 3-uniforme. Dans la deuxième partie, on donne une représentation arborescente alternative des matroïdes de largeur de branche bornée. Cela permet d'exprimer localement la propriété d'indépendance et ainsi de décider en temps linéaire des propriétés monadiques du second ordre sur ces structures. On obtient également une énumération à délai linéaire des objets définissables en LMSO, par exemple les circuits d'un matroïde. On montre que cette décomposition s'étend facilement à d'autres classes de matroïdes et en poussant l'abstraction plus loin à des hypergraphes décomposables.