Guest post by Yohann Benchetrit.<\/p>\n
The topic of this post is to introduce a new parameter $\\beta$ measuring the complexity of the facets of the matching polytope of a graph, which also extends to binary matroids. We give\u00a0a simple efficient algorithm deciding whether a binary matroid satisfies $\\beta\\leq 1$. This is the first non-trivial case after bipartiteness, which is equivalent to $\\beta=0$. The results presented here are joint work with Andr\u00e1s Seb\u0151, and appeared in [1].<\/p>\n
The matching polytope of a graph plays an important role in Graph Theory and Combinatorial Optimization. The methods involved in the study of its structure and properties initiated many relations between polyhedra, min-max theorems and polynomial-time algorithms.<\/p>\n
A matching<\/em> of a graph is a set of pairwise non-incident edges. The incidence vector of a matching $M$ of a graph $G$ is the 0-1 vector $\\chi^{M}$ of $\\mathbb{R}^{E(G)}$ defined for every $e\\in E(G)$ by: $\\chi^{M}(e)=1$ if and only if $e\\in M$. The matching polytope<\/em> of $G$, denoted by $\\mathsf{MATCH}(G)$, is the convex hull of the incidence vectors of the matchings of $G$. As a polyhedron, it is the set of solutions of a finite number of linear inequalities over $\\mathbb{R}^{E(G)}$. Basically, information on the inequalities describing this polytope is useful as it allows applying linear programming tools (for example the duality theorem, the Ellipsoid method, etc.).<\/p>\n The following result, due to Edmonds and Pulleyblank [5], gives a complete description of the matching polytope using linear inequalities. A graph $H$ is factor-critical<\/em> if for every $v\\in V(H)$, the graph obtained from $H$ by deleting $v$ and every edge incident to $v$ has a perfect matching (a matching covering every vertex).<\/p>\n Theorem 1. \u00a0<\/strong>For every graph $G$: Furthermore, Edmonds [4]\u00a0shows that each inequality associated with a 2-connected factor-critical induced subgraph $H$ appears in every description of $ \\mathsf{MATCH}(G)$.<\/p>\n An ear-decomposition<\/em> of a graph $G$ is a sequence $(P_0,\\ldots,P_k)$ of a circuit $P_0$ and paths (with two distinct ends) $P_1,\\ldots,P_k$ of $G$ such that $E(G)=E(P_0)\\cup\\ldots\\cup E(P_k)$ and for every $i\\in\\left\\{ Theorem 2. \u00a0<\/strong>A graph is 2-connected and factor-critical if and only if it has an odd ear-decomposition.<\/p>\n It follows from Menger’s theorem that a graph admits an ear-decomposition if and only if it is 2-connected. In addition, all ear-decompositions of a 2-connected graph $G$ have the same number $|E(G)|-|V(G)|+1$ of ears (indeed, deleting a single edge from each ear of an arbitrary ear-decomposition yields a spanning tree), hence the number of ears<\/em> of $G$ is well-defined.<\/p>\n This and Lov\u00e1sz’s result suggest the following measure of complexity of the matching polytope:<\/p>\n Definition 3. \u00a0<\/strong>For each graph $G$, let $\\beta(G)$ denote the largest number of ears of a 2-connected factor-critical subgraph of $G$.<\/p>\n For example, $\\beta(G)=0$ if and only if $G$ is a bipartite graph, and $\\beta(G)\\leq 1$ if and only if $G$ does not contain three pairwise internally-disjoint paths with the same ends, such that exactly two of them have an odd number of edges.<\/p>\n The Parity Minor Algorithm [6]\u00a0implies that for each fixed $k$, determining whether a graph $G$ satisfies $\\beta(G)\\geq k$ can be done in polynomial-time. \u00a0However, the proof in [6]\u00a0is built upon elaborate techniques of the Graph Minor Project, and is oriented towards generality. This suggests searching for more adapted algorithms. In this direction, Bruhn and Schaudt [2]\u00a0provided a direct solution to test $\\beta\\leq 1$ efficiently for graphs with maximum degree 3.<\/p>\n In the rest of this post, we extend $\\beta$ to binary matroids and characterize those which satisfy $\\beta\\leq 1$. As a consequence, we obtain an elementary polynomial-time algorithm for testing whether a binary matroid $M$ satisfies $\\beta(M)\\leq 1$ or finding an obstruction, only using ear-decompositions and basic computations in the cycle space (mod 2). This completely avoids Graph Minors and implies a rather simple algorithm deciding $\\beta\\leq 1$ in graphs, with no restriction on the degree.<\/p>\n Also, applying our result to the co-graphic case yields an unexpected consequence: determining whether a graph has two odd bonds meeting on an even number of edges can be carried out efficiently.<\/p>\n Our motivation in studying $\\beta$ comes from the recognition problem for $h$-perfect graphs. A graph is $h$-perfect<\/em> if the convex hull of the incidence vectors of its stable sets (sets of pairwise non-adjacent vertices) is completely described by non-negativity and rank-inequalities of cliques and odd circuits. \u00a0The class of $h$-perfect graphs are a\u00a0superclass of perfect graphs, and share a number of similar properties with the latter (see the second volume of Schrijver’s Combinatorial Optimization for further details).<\/p>\n Whereas perfection can be checked in polynomial-time, it is still open whether the same holds for $h$-perfection. Testing the $h$-perfection of a line graph $L(G)$ is essentially equivalent to checking $\\beta(G)\\leq 1$, and thus our results on $\\beta$ directly imply a simple algorithm recognizing $h$-perfect line graphs.<\/p>\n An ear-decomposition<\/em> of a matroid $M$ is a sequence $(C_1,\\ldots,C_k)$ of circuits of $M$ such that: $C_1\\cup \\ldots \\cup C_k=E(M)$ and for each $i\\in\\left\\{2,\\ldots,k \\right\\}$, $C_i$ meets both $\\cup_{j<i}C_j$ and its complement, and $C_i\\setminus (\\cup_{j<i}C_j)\\neq\\emptyset$ is a circuit of the contraction $M\/(\\cup_{j<i}C_j)$. The ear-decomposition is odd<\/em> if the sets $C_i\\setminus (\\cup_{j<i}C_j)$ (the ears<\/em>) all have odd cardinality (for $i\\in\\left\\{1,\\ldots,k\\right\\}$).<\/p>\n A matroid is factor-critical<\/em> if it has an odd ear-decomposition. \u00a0It is easy to check that a matroid has an ear-decomposition if and only if it is connected, and that all the ear-decompositions of a connected binary matroid have the same number $|E(M)|-\\mathsf{rk}(M)$ of ears. Hence, for each binary matroid $M$,\u00a0 we may define $\\beta(M)$ as the largest number of ears of a factor-critical restriction of $M$. It is straightforward to check that the values of $\\beta$ for a graph and its circuit matroid are equal.<\/p>\n For algorithmic considerations, we assume\u00a0that binary matroids are given by a linear representation or an independence oracle; complexity refers to the number of required calls to this oracle.<\/p>\n The first important observation is the following (see [1]\u00a0for a proof).<\/p>\n Lemma 4. \u00a0<\/strong>A connected binary matroid $M$ satisfies $\\beta(M)\\geq 2$ if and only if it has two odd circuits which meet in an even number of elements. \u00a0Furthermore, a factor-critical restriction of $M$ with two ears can be constructed from two such odd circuits in polynomial-time.<\/p>\n This states that we have to check the parity of the intersection of every pair of odd circuits of $M$ to certify that $\\beta(M)\\leq 1$. In fact, we need only to check it for pairs of a certain basis of the cycle space of $M$.<\/p>\n A cycle<\/em> of a matroid is a union of disjoint circuits, and it is odd<\/em> if it has odd cardinality. \u00a0The set of (incidence vectors of) cycles of a binary matroid $M$ is a subspace of $\\mathbb{F}_2^{E(M)}$ (this characterizes binary matroids), called the cycle space<\/em> of $M$ and denoted by $\\mathcal{C}(M)$. Clearly, $\\mathcal{C}(M)$ is spanned by the circuits of $M$ and $\\dim \\mathcal{C}(M)=|E(M)|-\\mathsf{rk}(M)$ (consider the set of fundamental circuits of a basis). A set $S$ of cycles of $M$ is a cycle basis<\/em> of $M$ if the incidence vectors of the elements of $S$ form a basis of $\\mathcal{C}(M)$. We now prove the main ingredient of our characterization. The fact that we have only circuits in the basis obtained is crucial.<\/p>\n Lemma 5. \u00a0<\/strong>Each connected non-bipartite binary matroid has an odd cycle basis formed by circuits only. It can be constructed in polynomial time.<\/p>\n Proof.<\/em> Let $M$ be a connected and non-bipartite binary matroid. Let $M_p$ be the binary matroid obtained by adding successively an all-0 column and an all-1 line to a matrix representation of $M$, and let $p$ be the new element of $M_p$. Now, consider an ear-decomposition $\\left\\{C_1,\\ldots,C_k \\right\\}$ of $M_p$ such that all the $C_i$ contain $p$. It is easy to check that $\\left\\{C_1\\setminus \\left\\{p\\right\\},\\ldots,C_k\\setminus \\left\\{p\\right\\}\\right\\}$ is an odd cycle basis of $M$, formed by circuits only. $\\blacksquare$<\/p>\n The following statement is a direct consequence of the well-known fact that, for two subsets $S_1,S_2$ of a set $S$: the sum of the incidence vectors of $S_1$ and $S_2$ in $\\mathbb{F}_2^{S}$ is the incidence vector of $S_1\\Delta S_2$ and their product is the parity of $ |S_1\\cap S_2|$ (with respect to the standard bilinear form on $\\mathbb{F}_2^{S}$).<\/p>\n Lemma 6.\u00a0<\/strong>If a binary matroid has a totally odd cycle basis, then all its odd cycles pairwise-intersect in an odd number of elements.<\/p>\n We can\u00a0finally prove our characterization.<\/p>\n Theorem 7. \u00a0<\/strong>Let $M$ be a connected non-bipartite binary matroid. The following statements are equivalent.<\/p>\n Proof. \u00a0<\/em>We first prove that $ (1)\\Rightarrow (2) $. Since $\\beta(M)\\leq 1$ and as $M$ is connected and non-bipartite, Lemma 5 shows that $M$ has an odd cycle basis $B$ whose elements are circuits. Lemma 4\u00a0implies that the elements of $B$ pairwise-intersect in an odd number of elements. That is, $B$ is totally odd.<\/p>\n The implication $ (2)\\Rightarrow (3) $ straightforwardly follows from Lemma\u00a06.<\/p>\n We finally prove $ (3)\\Rightarrow (1) $. Suppose that each odd cycle basis of $M$ is totally odd. \u00a0Since $M$ is connected and non-bipartite, Lemma 5\u00a0shows that $M$ has an odd cycle basis $B$. Since $B$ is totally odd, Lemma 6 implies that all odd cycles, and in particular all odd circuits of $M$, pairwise-intersect in an odd number of elements. By Lemma 4, we get $\\beta(M)\\leq 1$. $\\blacksquare$<\/p>\n Now, testing whether a connected non-bipartite binary matroid $M$ satisfies $\\beta(M)\\leq 1$ can be done as follows: build an odd cycle basis $B$ of $M$ formed by circuits only (with Lemma 5), and compute the parities of the intersections of pairs of elements of $B$; there is only a polynomial number of such pairs, since $|B|=\\dim \\mathcal{C}(M)=|E(M)|-\\mathsf{rk}(M)$. Clearly, a binary matroid $M$ satisfies $\\beta(M)\\leq 1$ if and only if every non-bipartite block of $M$ satisfies this condition. The blocks of $M$ can be easily found in polynomial-time, and hence we need only one more subroutine to finish the algorithm: deciding in polynomial-time whether a connected binary matroid is bipartite. This can be carried out using the following straightforward proposition, which generalizes the bipartiteness test of graphs.<\/p>\n Proposition 8. \u00a0<\/strong>Let $M$ be a connected binary matroid. The following statements are equivalent.<\/p>\n Hence, testing bipartiteness only requires building a cycle basis formed by circuits (from the fundamental circuits of a basis of $M$, for example) and checking whether all its circuits are even. If so, the matroid is bipartite and otherwise we find\u00a0an odd circuit.<\/p>\n $\\beta$ can be used as a parameter to separate on, for properties of the matching polytope (for example, the integer decomposition property [1]). \u00a0The complexity of computing $\\beta$ for graphs is apparently not known.<\/p>\n Clearly, the property $\\beta(G)\\geq k$ is in $\\mathsf{NP}$ (as factor-criticality can be tested using a maximum-matching algorithm), but we do not know if it belongs to $\\mathsf{co}$-$\\mathsf{NP}$. Also, it is not clear whether the Parity Minor algorithm can be circumvented to check efficiently, for fixed $k\\geq 3$, whether a graph $G$ satisfies $\\beta(G)\\geq k$.<\/p>\n For binary matroids, the situation is even less clear: results of Szegedy and Szegedy [9] show that testing whether a binary matroid is factor-critical can be done in randomized polynomial-time, but a deterministic algorithm is still missing, even for co-graphic matroids. Finally, it is not clear whether $\\beta\\leq 1$ can be decided efficiently for other interesting classes of matroids (our approach does not directly extend to anything else).<\/p>\n [1] Y. Benchetrit and A. Seb\u0151. Ear-decompositions and the complexity of the matching polytope.<\/em>\u00a0arXiv preprint, 2015.<\/p>\n [2] H. Bruhn and O. Schaudt. Claw-free t-perfect graphs can be recognised in polynomial time.\u00a0<\/em>In Jon Lee and Jens Vygen, editors, IPCO, volume 8494 of LNCS, pages 404\u2013415. 2014.<\/p>\n [3] C. Coullard and L. Hellerstein. Independence and port oracles for matroids, with an appli<\/em>cation to computational learning theory.<\/em> Combinatorica, 16(2):189\u2013208, 1996.<\/p>\n [4] J. Edmonds. Maximum matching and a polyhedron with 0, 1 vertices.<\/em> J. of Res. the Nat.\u00a0Bureau of Standards, 69 B:125\u2013130, 1965.<\/p>\n [5] J. Edmonds and W. Pulleyblank. Facets of 1-matching polyhedra.<\/em> In Hypergraph Seminar\u00a0of Columbus, 1974.<\/p>\n [6] K. Kawarabayashi, B. Reed, and P. Wollan. The graph minor algorithm with parity condi<\/em>tions.<\/em> In FOCS, 2011 IEEE 52nd Annual Symposium, pages 27\u201336. IEEE, 2011.<\/p>\n [7] L. Lov\u00e1sz. A note on factor-critical graphs.<\/em> Studia Sci. Math. Hungar., 7:279\u2013280, 1972.<\/p>\n [8] James Oxley. Matroid Theory.<\/em> 1992.<\/p>\n [9] B. Szegedy and C. Szegedy. Symplectic spaces and ear-decomposition of matroids.<\/em> Combinatorica, 26(3):353\u2013377, 2006.<\/p>\n","protected":false},"excerpt":{"rendered":" Guest post by Yohann Benchetrit. Introduction The topic of this post is to introduce a new parameter $\\beta$ measuring the complexity of the facets of the matching polytope of a graph, which also extends to binary matroids. We give\u00a0a simple … Continue reading
\n\\begin{equation*}\\label{fonda-eqn-MATCH}
\n\\mathsf{MATCH}(G):=\\left\\{x\\in\\mathbb{R}^{E(G)}\\colon\\begin{array}{cc}
\nx\\geq 0, & \\\\
\n\\displaystyle \\sum_{\\text{e incident to $v$}}x_e\\leq 1 & \\forall v\\in V(G), \\\\
\n\\displaystyle \\sum_{e\\in E(H)}x_e\\leq \\frac{|V(H)|-1}{2} & \\text{$\\forall H$ 2-connected factor-critical } \\\\
\n& \\text{induced subgraph of $G$}
\n\\end{array}\\right\\}.
\n\\end{equation*}<\/p>\n
\n1,\\ldots,k\\right\\}$, $P_i$ meets $P_0\\cup\\ldots\\cup P_{i-1}$ exactly on its two ends; the $P_i$ are the ears<\/em> of the decomposition (notice that we do not allow an ear to attach on a single vertex). The decomposition is odd<\/em> if all ears have an odd number of edges. Lov\u00e1sz proved:<\/p>\nTesting $\\beta\\leq 1$ in Binary Matroids<\/h1>\n
\nA cycle basis $B$ is odd<\/em> if all its cycles are odd, and it is totally odd<\/em> if moreover all the cycles of $B$ pairwise-intersect on an odd number of elements.<\/p>\n
\nLehman’s matroid-port theorem easily implies that each element of $M$ belongs to an odd circuit (see [8]). It follows straightforwardly that $M_p$ is a connected matroid.
\nFurthermore, a theorem of Coullard and Hellerstein states that for each connected matroid $N$ and every $e\\in E(N)$, there exists an ear-decomposition of $N$ whose circuits all contain $e$ and which can be found in polynomial-time [3].<\/p>\n\n
\nIf two elements of $B$ meet in an even number of elements, then Lemma 4\u00a0shows $\\beta(M)\\geq 2$ and a factor-critical restriction of $M$ with exactly two ears. Otherwise, $B$ is totally odd and Theorem 7\u00a0implies that $\\beta(M)\\leq 1$.<\/p>\n\n
Open Problems<\/h1>\n
References<\/h1>\n