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 a 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ás Sebő, and appeared in [1].
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.
A matching 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 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.).
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 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).
Theorem 1. For every graph $G$:
\begin{equation*}\label{fonda-eqn-MATCH}
\mathsf{MATCH}(G):=\left\{x\in\mathbb{R}^{E(G)}\colon\begin{array}{cc}
x\geq 0, & \\
\displaystyle \sum_{\text{e incident to $v$}}x_e\leq 1 & \forall v\in V(G), \\
\displaystyle \sum_{e\in E(H)}x_e\leq \frac{|V(H)|-1}{2} & \text{$\forall H$ 2-connected factor-critical } \\
& \text{induced subgraph of $G$}
\end{array}\right\}.
\end{equation*}
Furthermore, Edmonds [4] shows that each inequality associated with a 2-connected factor-critical induced subgraph $H$ appears in every description of $ \mathsf{MATCH}(G)$.
An ear-decomposition 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\{
1,\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 of the decomposition (notice that we do not allow an ear to attach on a single vertex). The decomposition is odd if all ears have an odd number of edges. Lovász proved:
Theorem 2. A graph is 2-connected and factor-critical if and only if it has an odd ear-decomposition.
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 of $G$ is well-defined.
This and Lovász’s result suggest the following measure of complexity of the matching polytope:
Definition 3. For each graph $G$, let $\beta(G)$ denote the largest number of ears of a 2-connected factor-critical subgraph of $G$.
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.
The Parity Minor Algorithm [6] implies that for each fixed $k$, determining whether a graph $G$ satisfies $\beta(G)\geq k$ can be done in polynomial-time. However, the proof in [6] is 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] provided a direct solution to test $\beta\leq 1$ efficiently for graphs with maximum degree 3.
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.
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.
Our motivation in studying $\beta$ comes from the recognition problem for $h$-perfect graphs. A graph is $h$-perfect 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. The class of $h$-perfect graphs are a superclass 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).
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.
Testing $\beta\leq 1$ in Binary Matroids
An ear-decomposition 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 if the sets $C_i\setminus (\cup_{j<i}C_j)$ (the ears) all have odd cardinality (for $i\in\left\{1,\ldots,k\right\}$).
A matroid is factor-critical if it has an odd ear-decomposition. It 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$, 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.
For algorithmic considerations, we assume that binary matroids are given by a linear representation or an independence oracle; complexity refers to the number of required calls to this oracle.
The first important observation is the following (see [1] for a proof).
Lemma 4. 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. Furthermore, a factor-critical restriction of $M$ with two ears can be constructed from two such odd circuits in polynomial-time.
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$.
A cycle of a matroid is a union of disjoint circuits, and it is odd if it has odd cardinality. The 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 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 of $M$ if the incidence vectors of the elements of $S$ form a basis of $\mathcal{C}(M)$.
A cycle basis $B$ is odd if all its cycles are odd, and it is totally odd if moreover all the cycles of $B$ pairwise-intersect on an odd number of elements.
We now prove the main ingredient of our characterization. The fact that we have only circuits in the basis obtained is crucial.
Lemma 5. Each connected non-bipartite binary matroid has an odd cycle basis formed by circuits only. It can be constructed in polynomial time.
Proof. 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$.
Lehman’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.
Furthermore, 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].
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$
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}$).
Lemma 6. If a binary matroid has a totally odd cycle basis, then all its odd cycles pairwise-intersect in an odd number of elements.
We can finally prove our characterization.
Theorem 7. Let $M$ be a connected non-bipartite binary matroid. The following statements are equivalent.
- $\beta(M)\leq 1$,
- $M$ has a totally odd cycle basis formed by circuits only,
- each odd cycle basis of $M$ is totally odd.
Proof. 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 implies that the elements of $B$ pairwise-intersect in an odd number of elements. That is, $B$ is totally odd.
The implication $ (2)\Rightarrow (3) $ straightforwardly follows from Lemma 6.
We finally prove $ (3)\Rightarrow (1) $. Suppose that each odd cycle basis of $M$ is totally odd. Since $M$ is connected and non-bipartite, Lemma 5 shows 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$
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)$.
If two elements of $B$ meet in an even number of elements, then Lemma 4 shows $\beta(M)\geq 2$ and a factor-critical restriction of $M$ with exactly two ears. Otherwise, $B$ is totally odd and Theorem 7 implies that $\beta(M)\leq 1$.
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.
Proposition 8. Let $M$ be a connected binary matroid. The following statements are equivalent.
- $M$ is bipartite,
- There exists a cycle basis of $M$ containing only even circuits,
- Each cycle basis of $M$ contains only even cycles.
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 an odd circuit.
Open Problems
$\beta$ can be used as a parameter to separate on, for properties of the matching polytope (for example, the integer decomposition property [1]). The complexity of computing $\beta$ for graphs is apparently not known.
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$.
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).
References
[1] Y. Benchetrit and A. Sebő. Ear-decompositions and the complexity of the matching polytope. arXiv preprint, 2015.
[2] H. Bruhn and O. Schaudt. Claw-free t-perfect graphs can be recognised in polynomial time. In Jon Lee and Jens Vygen, editors, IPCO, volume 8494 of LNCS, pages 404–415. 2014.
[3] C. Coullard and L. Hellerstein. Independence and port oracles for matroids, with an application to computational learning theory. Combinatorica, 16(2):189–208, 1996.
[4] J. Edmonds. Maximum matching and a polyhedron with 0, 1 vertices. J. of Res. the Nat. Bureau of Standards, 69 B:125–130, 1965.
[5] J. Edmonds and W. Pulleyblank. Facets of 1-matching polyhedra. In Hypergraph Seminar of Columbus, 1974.
[6] K. Kawarabayashi, B. Reed, and P. Wollan. The graph minor algorithm with parity conditions. In FOCS, 2011 IEEE 52nd Annual Symposium, pages 27–36. IEEE, 2011.
[7] L. Lovász. A note on factor-critical graphs. Studia Sci. Math. Hungar., 7:279–280, 1972.
[8] James Oxley. Matroid Theory. 1992.
[9] B. Szegedy and C. Szegedy. Symplectic spaces and ear-decomposition of matroids. Combinatorica, 26(3):353–377, 2006.