Packings, coverings and partitions

Stable sets and cliques

A stable set (or independent node set) is a node set without adjacent node pairs. A clique is a node set such that each pair of contained nodes is adjacent. A vertex cover is a node set which is incident with all edges.

The solver for the maximum stable set problem uses branch & bound with a fixed clique partition for bounding. Minimum vertex covers are obtained by taking the complementary node set of a maximum stable set. Maximum cliques are obtained by computing maximum stable sets in complementary graphs. The latter is inefficient if the original graph is very sparse.

The following diagram shows an independent positioning of queens on a chess board. In the underlying graph, nodes are adjacent if they are on a common grid line or diagonal:


[See API]


A node colouring is an assignment of the node colour register such that the end nodes of every edge have different colours. In other words, this denotes a partition of the node set into stable sets.

Bipartite graphs mean 2-colourable graphs. Probably the most famous theorem in graph theory states that every planar graph can be coloured with at most 4 different colours. The library comes up with a 5-colouring scheme for planar graphs. For the general setting, no efficient approximating method is available.

Observe that any clique size is a lower bound on the chromatic number (the minimum number of colour classes). If both numbers are equal and a maximum clique is given in advance (by the node colour register!), the node colour enumeration scheme will find a minimal colouring with some luck. Otherwise, only little effort is spent on computing a clique for dual bounding and it is most likely that the enumeration must be interrupted to obtain the heuristic solution found so far.

Similar to node colouring is the task of partitioning the node set into a minimum number of cliques. In the library, this problem is solved by searching for node colourings in the complementary graph. Needless to say that this is inefficient if the original graph is very sparse. If the graph is triangle free, however, clique partitioning is equivalent with maximum 1-matching, and this can be solved efficiently.

The following illustrates the clique cover problem. It is obvious that the displayed cover is minimal, since the graph does not include any 4-cliques (and this in turn follows from the fact that the graph is outerplanar):


[See API]

Maximum edge cuts

The maximum cut problem asks for a bipartition of the node set such that the total length of cross edges is maximized where arc capacities are interpreted as multiplicities. Note the difference with the min-cut solver which does not consider arc lengths, only capacities.

The solver also applies to directed and even mixed graphs. To this end, let the bipartition distinguish into left-hand and right-hand nodes. The goal is to maximize the length of non-blocking arcs in the left-to-right direction.

The following is a directed unit length and capacity example where the green nodes are left-hand and the red nodes are right-hand nodes:


[See API]

Feedback arc sets

A feedback arc set of a digraph is an arc set such that reverting these arcs results in a directed acyclic graph. Computing a minimum feedback arc set is NP-hard, but near-optimal solutions are used in the layered drawing approach to obtain readable drawings where the most arcs run in the same direction.

There is no elaborate branch & bound scheme for this problem, but only a 1/2 approximation method which is pretty analugue of the max-cut approximation.

[See API]

Tree packing

The maximum tree packing problem asks for a maximum cardinality set of edge disjoint spanning trees rooted at a common node, say r. It is well-known that this maximum equals the minimum cardinality of a directed cut with the node r on the left-hand side.

In principle, the library method for maximum tree packing also applies to the capacitated extension of this problem. But the procedure is only weakly polynomial, and the packing can be saved completely to the edge colour register only in the standard setting since a non-trivial capacity bound C means that this arc can be in C arborescences. The latter limitation can be overcome by using the extended API which allows to generate the arborescences step by step.

The procedure is little performant, and suited rather to illustrate the min-max relationship with minimum r-cut on small examples. Today, there is no method for the undirected analogue or even the extension to mixed graphs.

[See API]

Matchings & T-Joins

In the literature, a b-matching is a subgraph of an undirected graph such that for all nodes, the subgraph node degree does not exceed the node demand, Graph edges may occur in the b-matching with arbitrary multiplicity. A b-matching is called perfect if the subgraph node degrees and the node demands are equal.

There is also a standard notation of f-factors which differ from perfect b-matchings by that one does not allow for edge multiplicities. The perfect b-matching and the f-factor notation meet in the case of 1-factors respectively perfect 1-matchings which are subgraphs where every node is incident with exactly one edge. And 1-matchings are payed most attention in the literature, usually referring to matchings rather than 1-matchings. An example of a minimum cost 1-factor is given in the following figure:


For the library matching solver, edges may be assigned with arbitrary upper capacity bounds so that both f-factors and b-matchings are covered. It is possible to determine maximum matchings and minimum cost perfect matchings, even with specifying differing lower and upper node degree bounds.

For an undirected graph and some node set T with even cardinality, a T-join is a subgraph such that exactly the nodes in T have odd degree. This model covers several other optimization problems:

While the first two problems are indeed solved in the library by application of a T-join method, the 1-matching problem cannot be solved this way since it self forms part of the T-join method. When optimizing T-joins explicitly, the odd nodes (terminal nodes) are specified by the node demand labels.

The following figure shows a subgraph with two odd nodes. In fact, it is a minimum T-join for this odd node set. This example shows that a T-join for a 2-element node set T is a path only in certain circumstances. To this end, a sufficient condition is that no negative length cycles exist:


[See API]

Return to main page