Set Covering

Ideal Clutters

Perfect and Ideal clutters

A family of sets over a finite groundset where no set is properly contained in another is a clutter. Given a clutter \(\mathcal F\) we can define the set packing polytope,

\[ Q(\mathcal F)=\{x\geq{\bf 0}: \sum_{v\in S}x_v\leq 1,\; S\in\mathcal F\}. \]

The clutter \(\mathcal F\) is said to be perfect if the associated set packing polytope \(Q(\mathcal F)\) is integral. Padberg, Chvátal, and Lovász proved that a clutter \(\mathcal F\) is perfect if and only if its members are the maximal cliques in a perfect graph. Thus the study of perfect clutters reduces to the study of perfect graphs. The Strong Perfect Graph theorem of Chudnowsky, Robertson, Seymour and Thomas, then easily leads to an excluded minor characterization for perfect clutters.

Given a clutter \(\mathcal F\) we can define the set covering polyhedron,

\[ P(\mathcal F)=\{x\geq{\bf 0}: \sum_{v\in S}x_v\geq 1,\; S\in{\mathcal F}\}. \]

The clutter \(\mathcal F\) is said to be ideal if the associated set covering polyhedron \(P\) is integral. Ideal clutters, in contrast to perfect clutters, are not associated with a single class of combinatorial objects.

Examples of ideal clutters

1. odd cycles of planar graphs;
2. odd cycles of graphs with an even-face embedding on the Klein Bottle;
3. \(T\)-cuts of grafts with terminals \(T\);
4. \(T\)-joins of grafts with terminals \(T\);
5. directed cuts in a directed graph;
6. rooted arborescences of a directed graph.

Not all examples of ideal clutters arise from graphs, there are some purely geometric constructions as well. Thus ideal clutters form a very rich and complex class of objects.

A solution to this problem seems to be out of range at this juncture, so we will consider special cases. Here we shall focus on excluded minor characterizations. Let us formalize this. Let \(\mathcal F\) be a clutter and let \(P'\) be the polyhedron obtained from \(P(\mathcal F)\) by setting variables to zero and projecting variables. Then \(P'\) is of the form \(P(\mathcal F')\) for some clutter \(\mathcal F'.\) We then say that \(\mathcal F'\) is a minor of \(\mathcal F.\) As projection and faces of integral polyhedra are integral, idealness is a minor closed property.

A clutter is said to be minimally non-ideal (mni) if it is not ideal, but every proper minor is. Lehman proved that minimally non-ideal clutters have a unique fractional extreme point, moreover, that fractional point satisfies some very strong regularity properties. However, this is only a partial characterization, and (in contrast to minimally non perfect clutters) there are complicated infinite classes, and lots of sporadic examples of mni clutters. An accessible proof of Lehman's result is available in [1]. Results about general mni clutters can be found in [2].

To make further headway we need to restrict ourselves to special classes of clutters.

Binary clutters

A signed matroid is a pair \((M,\Sigma)\) where \(M\) is a binary matroid and \(\Sigma\subseteq EM.\) A cycle of \(M\) is even (resp. odd) if \(|C\cap\Sigma|\) is even (resp. odd). Clearly, the set of inclusion-wise minimal odd cycles of \((M,\Sigma)\) is a clutter. Clutters that can be obtained by this construction are said to be binary.

If characterizing all mni clutters is difficult, what about binary mni clutters? At least we have the following beautiful 1977 conjecture by Seymour:

For (1) the groundset of the clutter are the elements of the Fano matroids, and the members the lines. We illustrate the corresponding clutter \(\mathcal F\) in the following picture:

For (2) and (3) the groundset are the edges of the complete graph on \(5\) vertices. Note for (2) the members are the triangles and the pentagons and for (3) the members are triangles together with an independent edge and complete graphs on four vertices. The conjecture remains open but there are lots of known special cases as we will discuss next.

Known cases of the Flowing Conjecture

Consider a binary clutter \(\mathcal F\) and its associated signed matroid \((M,\Sigma)\). When \(M\) is co-graphic the members of \(\mathcal F\) are precisely the \(T\)-cuts of some graft \((G,T).\) As none of outcomes (1)-(3) of the Flowing Conjecture can be expressed as \(T\)-cuts, the conjecture implies that clutters of \(T\)-cuts are ideal. This is the case and was proved by Edmonds and Johnson. When \(M\) is graphic the members of \(\mathcal F\) are the odd circuits of some signed-graph \((G,\Sigma).\) It is easy to verify that (1) and (3) are not clutters of odd circuits of any signed-graph. Thus the Flowing Conjecture predicts that (2) is the only obstruction to idealness in that case. Indeed this is true [3].

An immediate consequence of this result are examples (a) and (b). This has implications for multi-commodity flow problems. For a survey on flows in graphs and matroids see [4]. Combining the Weakly Bipartite Theorem, the Theorem of Edmonds and Johnson on \(T\)-cuts and Seymour's decomposition of regular matroids, we can obtain sufficient conditions, in term of excluded minors, for a binary clutter to be ideal [5]. An extension to the Weakly Bipartite Theorem and an extension to the Edmonds and Johnson \(T\)-cuts Theorem is given in [6]. Furthermore, we develop an algorithmic version of Lehman's theorem with applications, [7]. including the following,

The Weak Flowing Conjecture

Consider a clutter \(\mathcal F\), the blocker of \(\mathcal F\) is the clutter \(b(\mathcal F)\) with the same groundset as \(\mathcal F\), where the members are the inclusion-wise minimal sets that intersect every member of \(\mathcal F.\) The blocking operation is an involution and Lehman proved that idealness is preserved under taking the blocker. This implies in particular, that if a clutter is mni then so is its blocker. Observe that the blocker of the Lines of the Fano is itself, and that the blocker of the complements of cuts of \(K_5\) is the clutter of odd circuits of \(K_5\). As the blocker of a binary clutter is also binary, the Flowing Conjecture can be restated as follows,

We proved that in fact the Weak Flowing Conjecture is equivalent to the Flowing Conjecture [8].

The Cycling Conjecture

A family of sets over a finite groundset where no set is properly contained in another is a clutter. A cover of a clutter is a subset of the groundset that intersects every member of the clutter. The maximum number of pairwise disjoint sets in a clutter is the packing number and the cardinality of the smallest cover is the covering number. Clearly, the packing number is at most the covering number and a clutter packs if both numbers coincide. Not every clutter packs; consider for instance:

\[ \mathcal F=\{\{1,2\},\{1,3\},\{2,3\}\}, \]

then the packing number is \(1\) but the covering number is \(2\).

Examples of clutters that pack

1. The clutter of chains in posets (Dilworth);
2. The clutter of st-paths (Menger);
3. \(T\)-cuts in a graft with terminal \(T\) and bipartite graph (Seymour);
4. odd cycles in odd-\(K_5\) free Eulerian graphs (Geelen, Guenin).

We will describe (d) in more detail later. Examples (c) and (d) both involve a parity condition. For (c) all circuits have even length and for (d) all edge cuts have an even number of edges. The Cycling Conjecture will provide sufficient conditions for a clutter, satisfying a particular parity condition, to pack.

The conjecture

Consider a clutter \(\mathcal F\) with an element \(e\) of the groundset. The deletion minor \(\mathcal F\setminus e\) is defined as \(\{S\in\mathcal F: e\notin S\}\), and the contraction minor \(\mathcal F/e\) is defined as the inclusion-wise minimal sets in \(\{S-\{e\}:S\in\mathcal F\}\). A minor of \(\mathcal F\) is a clutter obtained by a sequence of contractions and deletions.

A signed matroid is a pair \((M,\Sigma)\) where \(M\) is a binary matroid and \(\Sigma\subseteq EM\). A cycle of \(M\) is even (resp. odd) if \(|C\cap\Sigma|\) is even (resp. odd). Clearly, the set of inclusion-wise minimal odd cycles of \((M,\Sigma)\) is a clutter. Clutters that can be obtained by this construction are said to be binary.

A clutter \(\mathcal F\) is Eulerian if the parity of the cardinality of all inclusion-wise minimal covers is the same. At first glance this condition may appear non intuitive, so let us analyze what it says for a clutter \(\mathcal F\) of \(T\)-cuts in a graph \(G\) with terminals \(T\). The inclusion-wise minimal covers of \(\mathcal F\) are \(T\)-joins, and the parity of all \(T\)-joins is the same exactly when the symmetric difference of any two \(T\)-joins is a set with even cardinality. As the difference of two \(T\)-joins is an Eulerian subgraph, the condition translates to the requirement that \(G\) be bipartite.

We have the following conjecture that is essentially due to Seymour:

For (1) the groundset of the clutter are the elements of the Fano matroids, and the members the lines. For (2) and (3) the groundset are the edges of the complete graph on \(5\) vertices. Note for (2) the members are the triangles and the pentagons and for (3) the members are triangles together with an independent edge and complete graphs on four vertices. For (4) the groundset are the edges of the Petersen graph and the members, subgraphs where every vertex has odd degree. This conjecture is hard as it implies the Four Colour Theorem.

A special case of the conjecture

A signed-graph is a pair \((G,\Sigma)\) where \(G\) is a graph and \(\Sigma\) is a subset of the edges. We say that \(B\subseteq E(G)\) is even (resp. odd) if \(|B\cap\Sigma|\) is even (resp. odd). We call a subset of the edges of \((G,\Sigma)\) where \(s,t\in V(G)\) an odd \(st\)-walk if it is either an odd \(st\)-path, or it is the union of an even \(st\)-path \(P\) and an odd circuit \(C\) where \(P\) and \(C\) share at most one vertex. We consider the empty set to be an (even) \(st\)-path for the case where \(s=t\). Thus when \(s=t\), odd \(st\)-walks are odd circuits. We proved that the Cycling Conjecture holds for the clutter of odd \(st\)-walks [9].

Suppose \((G,\Sigma)\) is a signed-graph with vertices \(s,t\) and let \(\mathcal F\) be the clutter of odd \(st\)-walks of \((G,\Sigma)\). Then \(\mathcal F\) is Eulerian if either \(s=t\) and the degree of every vertex is even, or \(s\neq t\) and \(\deg(s)-|\Sigma|\) and the degree of every vertex in \(V(G)-\{s,t\}\) are even. The theorem states that in that case either the maximum number of pairwise (edge) disjoint odd \(st\)-walks is equal to the minimum number of edges needed to intersect all odd \(st\)-walks, or \(\mathcal F\) must have as a minor the clutter of the lines of the Fano or the clutter of odd circuits of \(K_5\).

When \(s=t\), the condition that \({\mathcal F}\) is Eulerian says that all vertices of \(G\) have even degree. Moreover, in that case odd \(st\)-walks are odd circuits. Hence, the Odd Walk Theorem implies:

A blocking vertex (resp. blocking pair) is a vertex (resp. pair of vertices) that intersects every odd circuit. Next we indicate a number of classes of signed-graphs for which the clutter of odd \(st\)-walks does not have as a minor the lines of the Fano or the clutter of odd circuits of \(K_5\):

1. There exists a blocking vertex;
2. \(s,t\) is a blocking pair;
3. Every odd \(st\)-walk is connected;
4. \(G\) is a plane graph with at most two odd faces;
5. \(G\) is a plane graph with a blocking pair \(u,v\) where \(s,u,t,v\) appear on a facial cycle in this order;
6. \(G\) has an embedding on the projective plane where every face is even and \(s, t\) are connected by an odd edge.

Applying the Odd Walk Theorem to class (a) we obtain:

Consider \(G\) obtained as follows:

Applying the Odd Walk to class (c) we obtain,

Suppose that \(H\) is as in (\(\star\)) and is loopless. Then by the above Corollary, there exists cuts \(\delta(U_1), \delta(U_2)\) such that every edge is in \(\delta(U_1)\cup\delta(U_2)\). It follows that for all \(i,j\in[4]\) where \(i\neq j\), \(U_i\cap U_j\) is a stable set. Hence, \(H\) is \(4\)-colourable.

The following conjecture would generalize the previous result as well as the 4-colour theorem,