Gotowa bibliografia na temat „Perfect matching polytope”

The perfect matching polytope of a graph G is the convex hull of the incidence vectors of all perfect matchings in G. This paper characterizes claw-free cubic graphs whose 1-skeleton graphs of perfect matching polytopes have diameter 1.

We consider families of symmetric linear programs (LPs) that decide a property of graphs (or other relational structures) in the sense that, for each size of graph, there is an LP defining a polyhedral lift that separates the integer points corresponding to graphs with the property from those corresponding to graphs without the property. We show that this is equivalent, with at most polynomial blow-up in size, to families of symmetric Boolean circuits with threshold gates. In particular, when we consider polynomial-size LPs, the model is equivalent to definability in a non-uniform version of fixed-point logic with counting (FPC). Known upper and lower bounds for FPC apply to the non-uniform version. In particular, this implies that the class of graphs with perfect matchings has polynomial-size symmetric LPs, while we obtain an exponential lower bound for symmetric LPs for the class of Hamiltonian graphs. We compare and contrast this with previous results (Yannakakis 1991), showing that any symmetric LPs for the matching and TSP polytopes have exponential size. As an application, we establish that for random, uniformly distributed graphs, polynomial-size symmetric LPs are as powerful as general Boolean circuits. We illustrate the effect of this on the well-studied planted-clique problem.

Dans cette thèse, nous étudions les polyèdres total dual box-intègraux (box-TDI) associés à plusieurs problèmes et matrices totalement équimodulaires. De plus, nous étudions la complexité de certaines questions fondamentales liées à ces polyèdres. Nous commençons par considérer les matrices totalement équimodulaires, qui sont des matrices telles que, pour chaque sous-ensemble de lignes linéairement indépendantes, toutes les sous-matrices maximales non-singulières ont le même déterminant en valeur absolue. Malgré leurs similitudes avec les matrices totalement unimodulaires, nous mettons en évidence plusieurs différences, même dans le cas des matrices d'incidence et d'adjacence des graphes. Comme on le sait, la matrice d'incidence d'un graphe donné est totalement unimodulaire si et seulement si le graphe est biparti. Cependant, la totale équimodularité d'une matrice d'incidence dépend du fait que nous considérons la représentation sommet-arête ou arête-sommet. Nous fournissons des caractérisations pour les deux cas. En conséquence, nous prouvons que reconnaître si un polyèdre donné est box-TDI est un problème co-NP-complet. La caractérisation de la totale unimodularité ou de la totale équimodularité de la matrice d'adjacence d'un graphe biparti donné reste non résolue, alors que nous avons résolu le problème correspondant dans le cas de la totale équimodularité lorsque le graphe est non-biparti. Dans une dernière partie, nous caractérisons les graphes pour lesquels le polytope des couplages parfaits (PMP) est décrit par des inégalités triviales et des inégalités correspondant à des coupes serrées. Les coupes serrées sont définies comme des coupes qui partagent précisément une arête avec chaque couplage parfait. Nous prouvons ensuite que tout graphe pour lequel le PMP correspondant est box-TDI appartient à cette classe. En conséquence, reconnaître si le PMP est box-TDI est un problème résoluble en temps polynomial. Cependant, nous fournissons plusieurs contre-exemples montrant que cette classe de graphes ne garantit pas la box-TDIness du PMP. Enfin, nous présentons des conditions nécessaires pour un polytope de couverture des arêtes pour être box-TDI et caractérisons quand le polytope des couplages extensibles est box-TDI, qui est l'enveloppe convex des couplages inclus dans un couplage parfait
In this thesis, we study box-totally dual integral (box-TDI) polyhedra associated with severalproblems and totally equimodular matrices. Moreover, we study the complexity of some funda-mental questions related to them.We start by considering totally equimodular matrices, which are matrices such that, forevery subset of linearly independent rows, all nonsingular maximal submatrices have the samedeterminant in absolute value. Despite their similarities with totally unimodular matrices, wehighlight several differences, even in the case of incidence and adjacency matrices of graphs.As is well-known, the incidence matrix of a given graph is totally unimodular if and only if thegraph is bipartite. However, the total equimodularity of an incidence matrix depends on whetherwe consider the vertex-edge or the edge-vertex representation. We provide characterizations forboth cases. As a consequence, we prove that recognizing whether a given polyhedron is box-TDIis a co-NP-complete problem.Characterizing the total unimodularity or total equimodularity of the adjacency matrix of agiven bipartite graph remains unsolved, while we solved the corresponding problem in the case oftotal equimodularity when the graph is nonbipartite.In a later part of this work, we characterize the graphs for which the perfect matching polytope(PMP) is described by trivial inequalities and the inequalities corresponding to tight cuts. Tightcuts are defined as cuts that share precisely one edge with each perfect matching. We thenprove that any graph for which the corresponding PMP is box-TDI belongs to this class. Asa consequence, it turns out that recognizing whether the PMP is box-TDI is a polynomial-timeproblem. However, we provide several counterexamples showing that this class of graphs does notguarantee the box-TDIness of the PMP.Lastly, we present necessary conditions for the box-TDIness of the edge cover polytope andcharacterize the box-TDIness of the extendable matching polytope, which is the convex hull ofthe matchings included in a perfect matching