In this thesis, we study the behaviour of Lovasz and Schrijver's lift-and-project operators N and N_0 while being applied recursively to the fractional stable set polytope of a graph. We focus on two related conjectures proposed by Liptak and Tuncel: the N-N_0 Conjecture and Rank Conjecture. First, we look at the algebraic derivation of new valid inequalities by the operators N and N_0. We then present algebraic characterizations of these valid inequalities. Tightly based on our algebraic characterizations, we give an alternate proof of a result of Lovasz and Schrijver, establishing the equivalence of N and N_0 operators on the fractional stable set polytope. Since the above mentioned conjectures involve also the recursive applications of N and N_0 operators, we also study the valid inequalities obtained by these lift-and-project operators after two applications. We show that the N-N_0 Conjecture is false, while the Rank Conjecture is true for all graphs with no more than 8 nodes.

In this thesis, we study the behaviour of Lovasz and Schrijver's lift-and-project operators N and N_0 while being applied recursively to the fractional stable set polytope of a graph. We focus on two related conjectures proposed by Liptak and Tuncel: the N-N_0 Conjecture and Rank Conjecture. First, we look at the algebraic derivation of new valid inequalities by the operators N and N_0. We then present algebraic characterizations of these valid inequalities. Tightly based on our algebraic characterizations, we give an alternate proof of a result of Lovasz and Schrijver, establishing the equivalence of N and N_0 operators on the fractional stable set polytope. Since the above mentioned conjectures involve also the recursive applications of N and N_0 operators, we also study the valid inequalities obtained by these lift-and-project operators after two applications. We show that the N-N_0 Conjecture is false, while the Rank Conjecture is true for all graphs with no more than 8 nodes.

A (convex) polytope P is said to be 2-level if every hyperplane H that is facet-defining for P has a parallel hyperplane H' that contains all the vertices of P which are not contained in H.Two level polytopes appear in different areas of mathematics, in particular in contexts related to discrete geometry and optimization. We study the problem of enumerating all combinatorial types of 2-level polytopes of a fixed dimension d. We describe the first algorithm to achieve this. We ran it to produce the complete database for d <= 8. Our results show that the number of combinatorial types of 2-level d-polytopes is surprisingly small for low dimensions d.We provide an upper bound for the number of combinatorially inequivalent 2-level d-polytopes. We phrase this counting problem in terms of counting some objects called 2-level configurations, that capture the class of "maximal" rank d 0/1-matrices, including (maximal) slack matrices of 2-level cones and 2-level polytopes. We provide a proof that the number of d-dimensional 2-level configurations coming from cones and polytopes, up to linear equivalence, is at most 2^{O(d^2 log d)}.Finally, we prove that the extension complexity of every stable set polytope of a bipartite graph with n nodes is O(n^2 log n) and that there exists an infinite class of bipartite graphs such that, for every n-node graph in this class, its stable set polytope has extension complexity equal to Omega(n log n). / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Cette thèse traite de la coloration de graphe, de la coloration par liste,d'ensembles indépendants de poids maximum et de la théorie structurelle des graphes.Dans un premier temps, nous fournissons un algorithme s'exécutant en temps polynomial pour le problème de la 4-coloration dans des sous-classes de graphe sans $P_6$. Ces algorithmes se basent sur une compréhension précise de la structure de ces classes de graphes, pour laquelle nous donnons une description complète.Deuxièmement, nous étudions une conjecture portant sur la coloration par liste et prouvons que pour tout graphe parfait sans griffe dont la taille de la plus grande clique est bornée par 4, le nombre chromatique est égal au nombre chromatique par liste. Ce résultat est obtenu en utilisant un théorème de décomposition des graphes parfaits sans griffe, une description structurelle des graphes de base de cette décomposition et le célèbre théorème de Galvin.Ensuite, en utilisant la description structurelle élaborée dans le premier chapitre et en renforçant certains aspects de celle-ci, nous fournissons un algorithme s'exécutant en temps polynomial pour le problème d'indépendant de poids maximum dans des sous-classes de graphe sans $P_6$ et sans $P_7$. Dans le dernier chapitre de ce manuscrit, nous infirmons une conjecture datant de 1999 de De Simone et K"orner sur les graphes normaux. Notre preuve est probabiliste et est obtenue en utilisant les graphes aléatoires. / This thesis deals with graph coloring, list-coloring, maximum weightstable set (shortened as MWSS) and structural graph theory.First, we provide polynomial-time algorithms for the 4-coloring problem insubclasses of $P_6$-free graphs. These algorithms rely on a preciseunderstanding of the structure of these classes of graphs for which we give afull description.Secondly, we study the list-coloring conjecture and prove that for anyclaw-free perfect graph with clique number bounded by 4, the chromatic numberand the choice number are equal. This result is obtained by using adecomposition theorem for claw-free perfect graphs, a structural description ofthe basic graphs of this decomposition and by using Galvin's famous theorem.Next by using the structural description given in the first chapter andstrengthening other aspects of this structure, we provide polynomial-timealgorithms for the MWSS problem in subclasses of $P_6$-free and $P_7$-freegraphs.In the last chapter of the manuscript, we disprove a conjecture of De Simoneand K"orner made in 1999 related to normal graphs. Our proof is probabilisticand is obtained by the use of random graphs.

SANTOS, Marcio Costa. Experimentos computacionais com implementações de conjunto por endereçamento direto e o problema de conjunto independente máximo. 2013. 78 f. Dissertação (Mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2013. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-11T19:04:45Z No. of bitstreams: 1 2013_dis_mcsantos.pdf: 1370695 bytes, checksum: f82fbf8bcae3901a15066e6d39ac2720 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-07-20T11:59:49Z (GMT) No. of bitstreams: 1 2013_dis_mcsantos.pdf: 1370695 bytes, checksum: f82fbf8bcae3901a15066e6d39ac2720 (MD5) / Made available in DSpace on 2016-07-20T11:59:49Z (GMT). No. of bitstreams: 1 2013_dis_mcsantos.pdf: 1370695 bytes, checksum: f82fbf8bcae3901a15066e6d39ac2720 (MD5) Previous issue date: 2013 / The use of bit vectors is a usual practice for represent sets by direct addressing with the aim of reduce memory consumed and improve efficiency of applications with the use of bit parallel techniques. In this text, we study implementations for represent sets by direct addressed. The basic structure in this implementations is the bit vector. Besides that basic implementation, we implement two variations also. The first one is a stratification of the bit vector, while the second uses a hash table. The operations linked to the implemented structure are include and remove an element and the union and intersection of two sets. Especial attention is given to the use of bit parallel in this condition. The implementation of the different structures in this work use an base interface and a base abstract class, where the operations are defined and the bit parallel is used. An experimental comparative between this structures is carry out using enumerative algorithms for the maximum stable set problem. Two approaches are used in the implementation of the enumerative algorithms for the maximum stable set problem, both using the bit parallel in the representation of the graph and on the operations with subsets of vertices. The first one is a known branch-and-bound algorithm and the second uses the Russian dolls method. In both cases, the use of bit parallel improve efficiency when the lower bounds are calculated based in a clique cover of the vertices. The results of computational experiments are presented as comparison between the two algorithms and as an assessment of the structures implemented. These results show that the algorithm based on the method Russian Dolls is more efficient regarding runtime and the memory consumed. Furthermore, the experimental results also show that the use stratification and hash tables also allow more efficiency in the case of sparse graphs. / A utilização de vetores de bits é prática corrente na representação de conjuntos por endereçamento direto com o intuito de reduzir o espaço de memória necessário e melhorar o desempenho de aplicações com uso de técnicas de paralelismo em bits. Nesta dissertação, examinamos implementações para representação de conjuntos por endereçamento direto. A estrutura básica nessas implementações é o vetor de bits. No entanto, além dessa estrutura básica, implementamos também duas variações. A primeira delas consiste em uma estratificação de vetores de bits, enquanto a segunda emprega uma tabela de dispersão. As operações associadas às estruturas implementadas são a inclusão ou remoção de um elemento do conjunto e a união ou interseção de dois conjuntos. Especial atenção é dada ao uso de paralelismo em bits nessas operações. As implementações das diferentes estruturas nesta dissertação utilizam uma interface e uma implementação abstrata comuns, nas quais as operações são especificadas e o paralelismo em bits é explorado. A diferença entre as implementações está apenas na estrutura utilizada. Uma comparação experimental é realizada entre as diferentes estruturas utilizando algoritmos enumerativos para o problema de conjunto independente máximo. Duas abordagens são utilizadas na implementação de algoritmos enumerativos para o problema de conjunto independente máximo, ambas explorando o potencial de paralelismo em bits na representação do grafo e na operação sobre subconjuntos de vértices. A primeira delas é um algoritmo do tipo {em branch-and-boound} proposto na literatura e a segunda emprega o método das bonecas russas. Em ambos os casos, o uso de paralelismo em bits proporciona ganhos de eficiência quando empregado no cálculo de limites inferiores baseados em cobertura por cliques. Resultados de experimentos computacionais são apresentados como forma de comparação entre os dois algoritmos e como forma de avaliação das estruturas implementadas. Esses resultados permitem concluir que o algoritmo baseado no método das bonecas russas é mais eficiente quanto ao tempo de execução e quanto ao consumo de memória. Além disso, os resultados experimentais mostram também que o uso de estratificação e tabelas de dispersão permitem ainda maior eficiência no caso de grafos com muito vértices e poucas arestas.

XAVIER, Alinson Santos. Geração de Facetas para Politopos de Conjuntos Independentes. 2011. 141 f. : Dissertação (mestrado) - Universidade Federal do Ceará, Centro de Ciências, Departamento de Computação, Fortaleza-CE, 2011. / Submitted by guaracy araujo (guaraa3355@gmail.com) on 2016-05-23T19:04:42Z No. of bitstreams: 1 2011_dis_asxavier.pdf: 1098827 bytes, checksum: b69a55ab904901d692a7afbf26cfbb04 (MD5) / Approved for entry into archive by guaracy araujo (guaraa3355@gmail.com) on 2016-05-23T19:10:07Z (GMT) No. of bitstreams: 1 2011_dis_asxavier.pdf: 1098827 bytes, checksum: b69a55ab904901d692a7afbf26cfbb04 (MD5) / Made available in DSpace on 2016-05-23T19:10:07Z (GMT). No. of bitstreams: 1 2011_dis_asxavier.pdf: 1098827 bytes, checksum: b69a55ab904901d692a7afbf26cfbb04 (MD5) Previous issue date: 2011 / A stable set of a graph is a set of pairwise non-adjacent vertices. The maximum stable set problem is to find a stable set of maximum cardinality in a given graph. The maximum induced k-partite subgraph problem is to find k stable sets such that their union has maximum cardinality. Besides having applications in various fields, including computer vision, molecular biology and VLSI circuit design, these problems also model other important combinatorial problems, such as set packing and vertex coloring. In the present work, we study the facial structure of the polytopes associated with both problems. First, we describe a new facet generating procedure for the stable set polytope, which unifies and subsumes several previous procedures. Besides generating many well-known facet inducing inequalities, this procedure can also generate new facet-inducing inequalities which have not been previously described. Then, we study the maximum induced k-partite polytope formulated by asymmetric representatives. We describe its simplest facets, show that some of its facets arise from vertex induced subgraphs, and identify two classes of subgraphs which generate facets of the polytope. To reach these main results, we study the affine equivalence between polyhedra, and also develop a new facet generating procedure for general polyhedra which subsumes the many versions of the lifting of variables. / Um conjunto independente de um grafo é um subconjunto de vértices que não contém nenhum par de vértices vizinhos. O problema do maior conjunto independente consiste em encontrar um conjunto independente de cardinalidade máxima. O problema do maior subgrafo induzido k-partido consiste em encontrar k conjuntos independentes cuja união tenha cardinalidade máxima. Além de possuírem aplicação em diversas áreas, como visão computacional, biologia molecular e projeto de circuitos integrados, estes problemas também modelam outros problemas de otimização combinatória, como empacotamento de conjuntos e coloração de vértices. Neste trabalho, estudamos os politopos associados aos dois problemas. Primeiro, descrevemos um novo procedimento de geração de facetas para o politopo de conjuntos independentes, que unifica e generaliza diversos procedimentos anteriores. Além de gerar várias classes de desigualdades indutoras de facetas já conhecidas, este procedimento também gera novas desigualdades que ainda não foram descritas na literatura. Em seguida, estudamos o politopo do subgrafo induzido k-partido associado à formulação por representantes de cor. Identificamos suas facetas mais simples, mostramos que facetas podem ser geradas a partir de subgrafos induzidos, e descrevemos duas classes de subgrafos que geram facetas deste politopo. Para obter os principais resultados desta dissertação, fazemos um estudo da relação de afim-isomorfismo entre poliedros, e desenvolvemos um novo procedimento de conversão de faces em facetas que generaliza as diversas versões do procedimento de levantamento de variáveis.

Conselho Nacional de Desenvolvimento CientÃfico e TecnolÃgico / Um conjunto independente de um grafo à um subconjunto de vÃrtices que nÃo contÃm nenhum par de vÃrtices vizinhos. O problema do maior conjunto independente consiste em encontrar um conjunto independente de cardinalidade mÃxima. O problema do maior subgrafo induzido k-partido consiste em encontrar k conjuntos independentes cuja uniÃo tenha cardinalidade mÃxima. AlÃm de possuÃrem aplicaÃÃo em diversas Ãreas, como visÃo computacional, biologia molecular e projeto de circuitos integrados, estes problemas tambÃm modelam outros problemas de otimizaÃÃo combinatÃria, como empacotamento de conjuntos e coloraÃÃo de vÃrtices. Neste trabalho, estudamos os politopos associados aos dois problemas. Primeiro, descrevemos um novo procedimento de geraÃÃo de facetas para o politopo de conjuntos independentes, que unifica e generaliza diversos procedimentos anteriores. AlÃm de gerar vÃrias classes de desigualdades indutoras de facetas jà conhecidas, este procedimento tambÃm gera novas desigualdades que ainda nÃo foram descritas na literatura. Em seguida, estudamos o politopo do subgrafo induzido k-partido associado à formulaÃÃo por representantes de cor. Identificamos suas facetas mais simples, mostramos que facetas podem ser geradas a partir de subgrafos induzidos, e descrevemos duas classes de subgrafos que geram facetas deste politopo. Para obter os principais resultados desta dissertaÃÃo, fazemos um estudo da relaÃÃo de afim-isomorfismo entre poliedros, e desenvolvemos um novo procedimento de conversÃo de faces em facetas que generaliza as diversas versÃes do procedimento de levantamento de variÃveis. / A stable set of a graph is a set of pairwise non-adjacent vertices. The maximum stable set problem is to find a stable set of maximum cardinality in a given graph. The maximum induced k-partite subgraph problem is to find k stable sets such that their union has maximum cardinality. Besides having applications in various fields, including computer vision, molecular biology and VLSI circuit design, these problems also model other important combinatorial problems, such as set packing and vertex coloring. In the present work, we study the facial structure of the polytopes associated with both problems. First, we describe a new facet generating procedure for the stable set polytope, which unifies and subsumes several previous procedures. Besides generating many well-known facet inducing inequalities, this procedure can also generate new facet-inducing inequalities which have not been previously described. Then, we study the maximum induced k-partite polytope formulated by asymmetric representatives. We describe its simplest facets, show that some of its facets arise from vertex induced subgraphs, and identify two classes of subgraphs which generate facets of the polytope. To reach these main results, we study the affine equivalence between polyhedra, and also develop a new facet generating procedure for general polyhedra which subsumes the many versions of the lifting of variables.

Dans cette thèse, nous étudions trois catégories de problèmes : les d-extensibles, les d-bloqueurs et les d-transversaux.Les d-extensibles de stables optimaux sont des ensembles de sommets d'un graphe G tels que tout stable de cardinal d du sous-graphe induit par un d-extensible peut être étendu à un stable optimal de G à l'aide de sommets qui n'appartiennent pas au d-extensible. Nous étudions les d-extensibles de cardinal maximal de stables dans les graphes bipartis. Nous démontrons quelques propriétés structurelles puis nous déterminons une borne inférieure du cardinal maximal d'un d-extensible. Nous étudions quelques classes de graphes dans lesquelles déterminer un d-extensible optimal de stables est un problème polynomial. Nous nous intéressons ensuite aux d-extensibles de stables dans les arbres. Nous prouvons plusieurs propriétés structurelles, déterminons une autre borne inférieure du cardinal maximal d'un d-extensible et étudions quelques classes d'arbres dans lesquelles déterminer un d-extensible optimal de stables est un problème polynomial.Les d-bloqueurs de stables sont des ensembles de sommets d'un graphe G tels que, si on retire les sommets d'un d-bloqueur, le cardinal maximal d'un stable du graphe induit par les sommets restants est inférieur d'au moins d au cardinal maximal d'un stable du graphe initial. Nous nous intéressons ici aux d-bloqueurs de coût minimal de stables dans les arbres. Après avoir prouvé une caractérisation des d-bloqueurs de stables dans les arbres, nous démontrons que déterminer un d-bloqueur de coût minimal de stable est un problème polynomial dans une classe d'arbres particulière.Soit Pi un problème d'optimisation sur un ensemble d'éléments fini. Un d-transversal de Pi est un ensembles d'éléments tel que l'intersection entre le d-transversal et toute solution optimale au problème Pi est de cardinal supérieur égal à d. Nous proposons ici une approche de génération de contraintes pour déterminer des d-transversaux de cardinal maximal de problèmes modélisés par des programmes mathématiques en variables binaires. Nous étudions deux variantes de cette approche que nous testons sur des instances de graphes générés aléatoirement pour déterminer des d-transversaux de stables optimaux et des d-transversaux de couplages optimaux / In this thesis, we study three types of problems : the d-extensibles sets, the d-blockers and the d-transversals.In a graph G, a d-extensible set of maximum independent sets is a subset of vertices of G such that every stable set of cardinality d in the subgraph restricted to the d-extensible set can be extented to a maximum stable set of G using only vertices that do not belong to the d-extensible set. We study d-extensible sets of mxaimum cardinality of stable sets in bipartite graphs. We show some structural properties and we determine a lower bound of the maximum cardinality of a d-extensible set. We consider some classes of graph where finding an optimum d-extensible set can be done in polynomial time. Then, we study the d-extensibles sets of stable sets in trees. We prove some properties on the structures of the d-extensibles sets and we determine another lower bound of the maximum cardinality of a d-extensible set. Finaly, we study somme classes of tree where a d-extensible sets of maximum cardinality can be done in polynomial time.In a graph G, a d-blocker is a subset of vertices such that, if removed, a maximum stable set of the resulting subgraph is of cardinality at most the cardinality of a maximum stable set of G minus d. We study d-blocker of minimal cost of stable sets in tree.We prove a caracterisation of d-blockers in tree and we study a particular classe of trees where computing a d-blocker of minimal cost of stable sets can be done in polynomial time.Let Pi be an optimisation problem on a finite set of elements. A d-transversal of Pi is a subset of elements such that the intersection between the d-transversal and every optimal solution of Pi contains at lest d elements. We propose an approach to compute d-transversal of any optimisation problem modelised by mathematical program with binary variables. We use a contraints generation approach. We compare two variations of this approach on randomly generated graph by computing d-transversals of stables sets and d-transversals of matching

博奕理論(Game Theory) 由經濟學研究方法所導出: 公設人是理性的, 并以數學演繹 邏輯推演, 而建構出來的決策模型。由於邏輯系統嚴密, 同時大量采用數學語言, 降 低文字語意的模棱, 而使得政治學之研究更有朝向真正科學地步之新契機。無奈的, 這種新發展的政治模型, 在國外雖已進行三十餘年, 國內則尚在起步。本文企圖較有 系統地全面引介這種理論模型, 以便替國內博奕論研究催生。 本文內容偏次, 除了第一章敘述博奕理論之基本知識如理性公設、效用理論及博奕結 構, 第六章對博奕論之優缺及適用性做一總評外, 中間四章完全以討論各種決策法為 主。第二章探討均衡的策略選擇, 包括兩人博奕的單純及混合策略解求法; 第三章穩 定的可能策略組, 則以求解核心(Core)及穩定組(Stable Set)為主; 第四章聯盟間的 合縱連橫, 剖析數量原則(Size Principle)、議價組合(Bargaining Set)及競價解(C ompetitive Solution); 第五章公平的價值分配, 則就談判合解的得失值分配以及各 聯盟實力指標的權力指數進行探討。 在案例研究方面, 本文共列舉五個, 包括民國七十八年天安門學生運動之均衡解、臺 北市空氣污染的囚犯困境分析、民國七十六年民進黨黨主席之爭的核心解及權力指數 分析、西德政黨間的合縱連橫分析以及民國七十九年中正堂學生運動合作解分析。

Le calcul du nombre chromatique et la détermination d'une colo- ration optimale des sommets d'un graphe sont des problèmes NP- difficiles en général. Ils peuvent cependant être résolus en temps po- lynomial dans les graphes parfaits. Par ailleurs, la perfection d'un graphe peut être décidée efficacement. Les graphes parfaits sont caractérisés par la structure de leur poly- tope des stables : les facettes non-triviales sont définies exclusivement par des inégalités de cliques. Réciproquement, une structure similaire des facettes du polytope des stables détermine-t-elle des propriétés combinatoires et algorithmiques intéressantes? Un graphe est h-parfait si les facettes non-triviales de son polytope des stables sont définies par des inégalités de cliques et de circuits impairs. On ne connaît que peu de résultats analogues au cas des graphes parfaits pour la h-perfection, et on ne sait pas si les problèmes sont NP-difficiles. Par exemple, les complexités algorithmiques de la re- connaissance des graphes h-parfaits et du calcul de leur nombre chro- matique sont toujours ouvertes. Par ailleurs, on ne dispose pas de borne sur la différence entre le nombre chromatique et la taille maxi- mum d'une clique d'un graphe h-parfait. Dans cette thèse, nous montrons tout d'abord que les opérations de t-mineurs conservent la h-perfection (ce qui fournit une extension non triviale d'un résultat de Gerards et Shepherd pour la t-perfection). De plus, nous prouvons qu'elles préservent la propriété de décompo- sition entière du polytope des stables. Nous utilisons ce résultat pour répondre négativement à une question de Shepherd sur les graphes h-parfaits 3-colorables. L'étude des graphes minimalement h-imparfaits (relativement aux t-mineurs) est liée à la recherche d'une caractérisation co-NP com- binatoire de la h-perfection. Nous faisons l'inventaire des exemples connus de tels graphes, donnons une description de leur polytope des stables et énonçons plusieurs conjectures à leur propos. D'autre part, nous montrons que le nombre chromatique (pondéré) de certains graphes h-parfaits peut être obtenu efficacement en ar- rondissant sa relaxation fractionnaire à l'entier supérieur. Ce résultat implique notamment un nouveau cas d'une conjecture de Goldberg et Seymour sur la coloration d'arêtes. Enfin, nous présentons un nouveau paramètre de graphe associé aux facettes du polytope des couplages et l'utilisons pour donner un algorithme simple et efficace de reconnaissance des graphes h- parfaits dans la classe des graphes adjoints. / Computing the chromatic number and finding an optimal coloring of a perfect graph can be done efficiently, whereas it is an NP-hard problem in general. Furthermore, testing perfection can be carried- out in polynomial-time. Perfect graphs are characterized by a minimal structure of their sta- ble set polytope: the non-trivial facets are defined by clique-inequalities only. Conversely, does a similar facet-structure for the stable set polytope imply nice combinatorial and algorithmic properties of the graph ? A graph is h-perfect if its stable set polytope is completely de- scribed by non-negativity, clique and odd-circuit inequalities. Statements analogous to the results on perfection are far from being understood for h-perfection, and negative results are missing. For ex- ample, testing h-perfection and determining the chromatic number of an h-perfect graph are unsolved. Besides, no upper bound is known on the gap between the chromatic and clique numbers of an h-perfect graph. Our first main result states that the operations of t-minors keep h- perfection (this is a non-trivial extension of a result of Gerards and Shepherd on t-perfect graphs). We show that it also keeps the Integer Decomposition Property of the stable set polytope, and use this to answer a question of Shepherd on 3-colorable h-perfect graphs in the negative. The study of minimally h-imperfect graphs with respect to t-minors may yield a combinatorial co-NP characterization of h-perfection. We review the currently known examples of such graphs, study their stable set polytope and state several conjectures on their structure. On the other hand, we show that the (weighted) chromatic number of certain h-perfect graphs can be obtained efficiently by rounding-up its fractional relaxation. This is related to conjectures of Goldberg and Seymour on edge-colorings. Finally, we introduce a new parameter on the complexity of the matching polytope and use it to give an efficient and elementary al- gorithm for testing h-perfection in line-graphs.