Electronic Journal: Southwest Journal of Pure and Applied Mathematics Internet: http://rattler.cameron.edu/swjpam.html ISSN 1083-0464 Vol. No. 01, 1996, pp. 16–29. Submitted: November 20, 1995, Published: April 4, 1996.

Polynomial–Time Partition of a Graph into Cliques

Anatoly D. Plotnikov

Abstract

The properties of a finite partially ordered set are used to find the solution of the partition finding problem of an arbitrary undirected graph into the minimum number of cliques. The solving algorithm has a practical application. The run time of the solving algorithm is equal to O(n^{5}), where n is the number of vertices of the graph.

(1991) A.M.S. (MOS) Subject Classification codes: 05. Keywords and Phrases. Graph, clique, partial order, vertex-saturated.

1 Statement of the problem.

We will consider the class L_{n} of undirected n-graphs without loops and multiple edges.

Let G = (X, Γ) ∈ L_{n}, where X = {x_{1}, …, x_{n}} is the set of vertices of the graph G, Γ is mapping of X into X.

The set N ⊂ X creates a clique of the graph G if the correlation x_{i} ∈ Γx_{j} takes place for any x_{i}, x_{j} ∈ N (i ≠ j; ∀i, j ∈ {1, 2, …, n}). The clique of graph G, defined by the set of vertices N, we will denote: Q(N). In the special case, when Card(N) = 1, we will call it a single-vertex clique.

The graph G is partitioned into cliques Q(N_{1}), …, Q(N_{m}) if

⋃_{i=1}^{m} N_{i} = X,

Department of Applied Mathematics and Computing Systems, Vinnitsa State Technical University, Vinnitsa, Ukraine. E-mail: vstu@sovam.com Copyright \begin{matrix}c \\ ◯ \end{matrix}1996 by Cameron University where N_{i} ∩ N_{k} = ⊘ ∀i, k ∈ {1, …, m} (i ≠ k). Obviously, there exists a set of partitions of the graph G into cliques. The

partition F = {Q(N_{1}), …, Q(N_{m})} of the graph G into cliques will be called minimum (MCP) if it has the minimum number of elements in comparison with other partitions of the graph into cliques.

It is necessary to find the partition F of the graph G ∈ L_{n} with the minimum number of cliques.

The formulated problem on the partitioning of the graph G ∈ L_{n} with the minimum number of the cliques is one of the NP -complete problems on graphs as is defined in [1], [6]. This problem has numerous applications.

2 Vertex-saturated digraph

Let there be a graph G = (X, Γ) ∈ L_{n}.

A set U ⊂ X, satisfying the condition U ∩ ΓU = ⊘, is called an independent set of the vertices of the graph G. An independent set of vertices U is called maximal (MIS), if U ∪ ΓU = X. Finally, MIS Û is called maximum (MMIS), if Card(Û) > Card(U) for all MIS U ⊂ X of the graph G ∈ L_{n}.

In the graph G we will find the MIS X^{0} and we will construct the acyclic digraph G⃗(X^{0}) = (X, Γ⃗), by way of orientation of the edges of the graph G so that the set of vertices X^{0} will have only outgoing arcs. We will call the set X^{0} initiating, and digraph G⃗(X^{0}) – a directed mapping of the graph G = (X, Γ) ∈ L_{n}. There is a set D(G) a directed mapping of the graph G ∈ L_{n}.

We will further consider only digraphs, belonging to the set D(G).

The length ρ(x) of the maximum directed path, connecting the initiating set X^{0} with the vertex x, we will call the rank of the vertex x ∈ X. We will call the set of all vertices of rank ρ(x) = k k-th layer of the vertices of the digraph G⃗(X^{0}) and will designate it as: X^{k} (k = \overline{0, m}), where m is the maximum rank of the vertices from X \ X^{0}.

We will construct the graph G⃗_{t}(X^{0}) = (X, Γ⃗_{t}) of the transitive closure digraph G⃗(X^{0}). Obviously, the graph G⃗_{t}(X^{0}) determines a finite partially ordered set (X, >).

It is not worth while to distinguish between the graph of transitive closure G⃗_{t}(X^{0}) and the partially ordered set (X, >). Therefore in the graph G⃗_{t}(X^{0}) we will also consider antipaths.

We will say, that the antipath U_{1} precedes the antipath U_{2} in the graph G⃗_{t}(X^{0}) and designate this as: U_{1} ≺ U_{2}, if for all vertices x ∈ U_{1} \ U_{2} there is a vertex y ∈ U_{2} \ U_{1} such that x < y. The precedence relation, obviously, is transitive.

In the digraph G⃗(X^{0}) we will consider the set of all vertices having ranks greater than or equal to k: X^{k} ∪ ⋯ ∪ X^{m}. An oriented subgraph of digraph G⃗(X^{0}), defined for the set of vertices X^{k} ∪ ⋯ ∪ X^{m}, will be called a directed subgraph of digraph G⃗(X^{0}), generated by layer X^{k}, and designate as: G⃗(X^{k}).

[figure: x_{1}; x_{2}; x_{3}; x_{4}; x_{5}; x_{6}; x_{7}; x_{8}; x_{9}; x_{1}; x_{2}; x_{3}; x_{4}; x_{5}; x_{6}; x_{7}; x_{8}; x_{9}; x_{1}; x_{2}; x_{3}; x_{4}; x_{5}; x_{6}; x_{7}; x_{8}; x_{9}; (a); (b); (c)]

Figure 1: Some MPP of the graph

The acyclic digraph G⃗(X^{0}) will be called correctly constructed (CCD), if in each directed subgraph G⃗(X^{k}) (k = \overline{0, m}) the initiating set X^{k} is a MIS of this subgraph.

We will consider only correctly constructed digraphs from D(G).

Let there be CCD G⃗(X^{0}) and its graphs of transitive closure G⃗_{t}(X^{0}).

A search of the maximum antipath with a simultaneous partitioning of the vertices of the graph G⃗_{t}(X^{0}) into a minimum number of paths is possible to execute by any algorithm of a finding of the maximum matching in bipartite graph [2], [5], [4]. Using the methodology of Ford and Fulkerson [2] in the graph G⃗_{t}(X^{0}) one such the maximum antipath U can be found, for which any other maximum antipath U_{1} precedes, i.e. U_{1} ≺ U for any antipath U_{1} of the graph G⃗_{t}(X^{0}). Such an antipath of the graph G⃗_{t}(X^{0}) we will call general.

In addition to the general antipath, if it possible to find other antipaths of the graph G⃗_{t}(X^{0}) if they exist. So for any vertex x ∈ X of the graph G⃗_{t}(X^{0}) it is possible to find a maximum antipath U(x) such that x ∈ U(x). Technically to search for antipath U(x) it is sufficient in the Ford-Fulkerson working table in which the maximum number of units in allowable cells [2] is found, to mark a row, corresponding to vertex x, and to execute a cycle of appointment of marks. Clearly, the antipath U(x) will be general for the vertex x, i. e. any other antipath, containing vertex x, will precede this antipath.

We will notice, that in the general case it is not true that for any vertex x ∈ X of the graph G⃗_{t}(X^{0}) there exists the maximum antipath U(x).

In fig. 1 a digraph is shown for the graph of transitive closure for which there is a general antipath U = U(1) = U(2) = U(4) = U(7) = {x_{1}, x_{2}, x_{4}, x_{7}} but there is not an antipath U(8). (The orientation of arcs of a digraph on a drawing is from below upwards).

The directed subgraph G⃗(X^{k}) (k = \overline{0, m}) of the digraph G⃗(X^{0}) we will call vertex-saturated relative to the initiating set X^{k}, if in its graph of transitive closure G⃗_{t}(X^{k}) any maximum antipath U(x) ⊂ X, when it exists, is a MIS of subgraph G⃗(X^{k}) and satisfies the relation: Card(U(x)) = Card(X^{k}).

We will call CCD G⃗(X^{0}) vertex-saturated, if any of its directed subgraphs G⃗(X^{k}) (k = \overline{0, m}), generated by the layer X^{k}, is vertex-saturated relative to the initiating set X^{k}.

Obviously, for any graph G = (X, Γ) ∈ L_{n} it is easy to construct a vertexsaturated CCD G⃗(X^{0}). For this purpose consider any subgraph G⃗(X^{k}) (k = \overline{0, m}) and construct its graph of transitive closure G⃗_{t}(X^{k}) which may be considered as the graph of a partial ordering. For each vertex x ∈ X find the maximum antipath U(x) ⊂ X, if it exists.

Vertex-saturated digraph will have constructed if each found the maximum antipath U(x) ⊂ X of the graph G⃗_{t}(X^{k}) satisfies the relation Card(U(x)) = Card(X^{k}) and is a MIS of the subgraph G⃗(X^{k}). Consequently, any subgraph G⃗(X^{k}) also must be vertex-saturated relative to the inducing layer X^{k} (k = \overline{0, m}). Otherwise we form MIS S ⊂ X (U(x) ⊂ S) of the digraph G⃗(X^{k}) and all arcs, coming in the vertices of the set S, are reoriented.

For the new digraph G⃗(S) the procedure described above is repeated.

Thus, the construction of a vertex-saturated digraph G⃗(X^{0}) is a recursive procedure, i. e. after construction of the subgraph G⃗(X^{m}), which is vertexsaturated relative to the initiating set X^{m}, for all k (k = \overline{0, m}) vertex-saturating of each subgraph G⃗(X^{k}) relative to the set X^{k} must be checked again.

Clearly, one of the main properties of a vertex-saturated digraph is that each path of a partition P of the vertices of the graph G⃗_{t}(X^{0}) into a minimum number of paths begins at a vertex of the initiating set X^{0}.

Let U_{1}, U_{2} ⊂ X are antipaths, maximal by inclusion, of the graph G⃗_{t}(X^{0}) such that U_{1} ≺ U_{2}.

We will consider the bipartite digraph G̃ = (U_{1}, U_{2}, Γ̃). This digraph is a subgraph of G⃗_{t}(X^{0}), which we will say is the induced by maximal antipaths U_{1}, U_{2}. The number

∇(G̃) = max{Card(S) − Card(U_{1} ∩ Γ̃^{−1}S)} ∀S ⊂ U_{2}

will call the deficit of the bipartite digraph G̃ = (U_{1}, U_{2}, Γ̃) [5].

Theorem 1. Let there be a vertex-saturated digraph G⃗(X^{0}). Then the deficit ∇(G̃) of any bipartite subgraph G̃) ⊂ G⃗_{t}(X^{0}), induced by the maximal antipaths U_{1}, U_{2} ⊂ X such, that U_{1} ≺ U_{2}, is equal to zero and Card(U_{1}) > Card(U_{2}).

This is a direct result of the König theorem [2], [5] and the definition of a vertex-saturated digraph.□

3 Recursive sequence of digraphs.

Let there be a vertex-saturated CCD G⃗(X^{0}) and G⃗_{t}(X^{0}) be its graph of transitive closure.

Partition the set of the vertices X of the graph G⃗_{t}(X^{0}) into the minimum number of paths P = {S_{1}, …, S_{p}}, where p = Card(X^{0}). We will call the partition P the minimum path partition (MPP) and which in the general case is not single valued.

As usual we will call an arc of the graph G⃗_{t}(X^{0}) thick, or engaged, if its belongs to some path of MPP P of this graph. Otherwise, an arc of the graph G⃗_{t}(X^{0}) will be called thin, or free (see the fig. 1).

We will call the arc (x_{i}, x_{j}) of the graph G⃗_{t}(X^{0}) essential and we will use the notation: x_{i} > x_{j}, if arc (x_{i}, x_{j}) of digraph G⃗(X^{0}) corresponds to it. Otherwise, we will call the arc (x_{i}, x_{j}) of the graph G⃗_{t}(X^{0}) fictitious and we will use the notation: x_{i} ≫ x_{j}. We will call the terminal vertex x_{j} of a fictitious arc x_{i} ≫ x_{j}, both ends of which belong to the same path S_{q} ∈ P (q = \overline{1, p}), marked (in the given MPP P), and for the set of all marked vertices of the graph G⃗_{t}(X^{0}) we will use the notation: B(P).

We will call a fictitious arc x_{i} ≫ x_{j} of the graph G⃗_{t}(X^{0}) elementary (EFA), if in the digraph G⃗(X^{0}) the vertices x_{i} and x_{j} are connected by the shortest directed path of length 2. We will call corresponding essential arcs x_{i} > x_{k} and x_{k} > x_{j}, belonging to paths of the graph G⃗_{t}(X^{0}), generators for EFA. Otherwise, we will call the fictitious arc x_{i} ≫ x_{j} compound.

Obviously, any compound fictitious arc can be represented as union of elementary fictitious arcs.

Lemma 2. Let G⃗(X^{0}) be some digraph and G⃗_{t}(X^{0}) be its graph of transitive closure. If B(P) = ⊘, where P is MPP of the graph G⃗_{t}(X^{0}), its maximum antipath U is MMIS of the digraph G⃗(X^{0}), and MPP P is its minimum cliques partition.

For the proof, we observe that if conditions of Lemma 2 are satisfied, each path S_{q} ∈ P (q = \overline{1, p}) is a clique of the digraph G⃗(X^{0}) and, hence, MPP P is a minimum cliques partition of the digraph. On the other hand, the vertices of the maximum antipath U belong to the set of its cliques, i.e. the number of vertices in the MMIS U does not exceed number of vertices in the set U.□

Notice, if the graph of the transitive closure G⃗_{t}(X^{0}) satisfies the conditions of Lemma 2, then the initial graph G ∈ L_{n} certainly is not transitively directed, and the digraph G⃗(X^{0}) is not correctly constructed or vertex-saturated.

Theorem 3. Let CCD G⃗(X^{0}) be vertex-saturated. Then in the graph G⃗_{t}(X^{0}) the MPP P exists and its paths contain only essential arcs.

The validity of the assertion follows from the definition of a correctly constructed digraph and Theorem 1.□

We will call the MPP P of the graph G⃗_{t}(X^{0}) correct relative to the marked vertex x_{j} ∈ B(P), if the vertex x_{k} preceding it in the path S_{q} ∈ P (x_{j}, x_{k} ∈ X(S_{q})) is connected to the vertex x_{j} by an essential arc and there does not exist another path connecting these vertices. We will say the arc x_{k} > x_{j} of the graph G⃗_{t}(X^{0}), satisfying the indicated conditions, the leading arc for the vertex x_{j} ∈ B(P).

It is easy to see, that the leading arc always determines the oriented path of maximum length, connecting the vertices x_{k} and x_{j} in digraph G⃗(X^{0}). Obviously, for any marked vertex x_{j} ∈ B(P) there always exists MPP of the graph G⃗_{t}(X^{0}) which is correct relative to x_{j}.

To find a leading arc in the digraph G⃗(X^{0}) we will construct a procedure (similar breadth-first search), which is started at the vertex x_{k}, which precedes the vertex x_{j} ∈ B(P) in the path S_{q} ∈ P (x_{k}, x_{j} ∈ X(S_{q})) of the MPP P of the graph G⃗_{t}(X^{0}). As we proceed we will store all arcs, ending at the vertex x_{j}. The last arc found, obviously, determines the required leading arc in the correct MPP of the graph G⃗_{t}(X^{0}).

Let there be a vertex-saturated CCD G⃗(X^{0}).

The sequence of digraphs

T = (G⃗^{(1)}(X^{0}), G⃗^{(2)}(X^{0}), …, G⃗^{(h)}(X^{0})),

induced by the digraph G⃗(X^{0}) we will call recursive (RSD), if for each of digraphs G⃗^{(z)}(X^{0}) (z = \overline{1, h − 1}) within this sequence there is a vertex-saturated CCD, G⃗^{(1)}(X^{0}) = G⃗(X^{0}) where the digraph G⃗^{(z+1)}(X^{0}) was obtained from the digraph G⃗^{(z)}(X^{0}) by reorientation of one of its arcs.

The construction of RSD T is made as follows (in an initial digraph all arcs are unmarked).

For an initial vertex-saturated CCD G⃗^{(1)}(X^{0}) = G⃗(X^{0}) find its graph of transitive closure G⃗_{t}^{(1)}(X^{0}). In the graph G⃗_{t}^{(1)}(X^{0}) we will construct some of its MPP P.

Further, in the graph G⃗_{t}^{(1)}(X^{0}) the marked vertex of minimum rank can be found. If there are some such vertices, then a marked vertex, which located first by the order path of MPP P, is chosen. The order of a path in P is defined by the numbering of the vertex of initiating set X^{0}, from which the considered path of MPP is going.

After a finding the marked vertex the search for its leading arc is executed. The leading arc found in the digraph G⃗^{(1)}(X^{0}) is reoriented. This is yielded a transition to the consideration of a new digraph G⃗^{(2)}(X^{0}) RSD T . In the new digraph the reoriented arc is marked as ”considered”.

Thus, any arc, reoriented in the digraph G(z)(X^{0}) (z = \overline{1, h − 1}), in each subsequent digraph G⃗^{(z+1)}(X^{0}) (z + 1 < r < h) of the RSD T will be marked as ”considered”. Further such an arc of the digraph G⃗^{(z)}(X^{0}) ∈ T is reoriented, which is not marked as ”considered” and in its corresponding graph of transitive closure G⃗_{t}^{(z)}(X^{0}) one arc is a leading arc for some marked vertex.

After construction of each new digraph G⃗^{(z+1)}(X^{0}) ∈ T (z = \overline{1, h − 1}) a check is executed: is it vertex-saturated? If so, then the obtained digraph is vertex-saturated and its corresponding graph of transitive closure G⃗_{t}^{(z+1)}(X^{0}) has been constructed. In this case all thick arcs of the graph G⃗_{t}^{(z)}(X^{0}) (except the leading arc) are chosen as the thick arcs of an initial (not optimum) partition of the new graph G⃗_{t}^{(z+1)}(X^{0}) into a paths.

After reorientation of an arc (x, y) of the digraph G⃗^{(z)}(X^{0}) a new vertexsaturated digraph G⃗^{(z+1)}(X^{0}) ∈ T has been constructed. Then, it is first determined whether the vertex x is marked in the graph G⃗_{t}^{(z+1)}(X^{0}). If so, a leading arc for the vertex x is found. If this arc is marked as ”considered”, the construction of a RSD is finished and all marks of the arcs in the obtained digraph G⃗^{(z+1)}(X^{0}) = G⃗^{(h)}(X^{0}) are removed.

If the vertex x is marked in the graph G⃗_{t}^{(z+1)}(X^{0}) but its leading arc is not marked as ”considered” then in the corresponding path of MPP of the graph G⃗_{t}^{(z+1)}(X^{0}) the vertex of the minimum rank is found.

In all other cases for the graph Gt(z + 1)(X^{0}) a marked vertex of the minimum rank is found which is first by order of the path of MPP of this graph.

Thus, RSD T is finite and turns, if:

(1) Digraph G⃗^{(h)}(X^{0}) is not vertex-saturated;

(2) The digraph G⃗^{(h)}(X^{0}) is vertex-saturated and its corresponding graph of transitive closure does not have the marked vertices ;

(3) In the vertex-saturated digraph G⃗^{(h)}(X^{0}) the arc marked earlier is leading.

In case (2) we will call the digraph G⃗^{(h)}(X^{0}) deadlocked.

Lemma 4. In the graph G = (X, Γ) ∈ L_{n} let Q(U) be the set of all of its cliques to each of which belongs one of vertices of the maximum antipath U of the corresponding vertex-saturated digraph G⃗(X^{0}) ∈ D(G). Further, let there be an odd cycle C_{2k+1} (k ≥ 2) of graph G such that k of the vertices belong to the maximum antipath U. Then such an edge of cycle C_{2k+1} exists, which does not belong to any one of the cliques in the set Q(U).

Let conditions of a Lemma 4 be satisfied.

Since k of the vertices of cycle C_{2k+1} (k ≥ 2), belonging to the maximum antipath U, are independent, there are 2k of edges of this cycle, each of which is incident to any of k of the vertices. Hence, there will be such an edge of cycle C_{2k+1}, which does not belong to any of cliques of set Q(U).□

Theorem 5. In the construction of a RSD of a vertex-saturated digraph G⃗(X^{0}), the leading arc will be found to be marked ”considered” iff this arc belongs to the odd (undirected) cycle C_{2k+1} (k ≥ 2) of this digraph.

The necessity conditions of Theorem 5 follow from the Lemma 4.

Sufficiency. Let the designated RSD T of the vertex-saturated digraph G⃗(X^{0}) be completed as the result of the detection in a graph of transitive closure G⃗_{t}^{(h)}(X^{0}), a leading arc marked as ”considered”. Let it be the arc x_{i} > x_{j}.

Then, according to the definition of RSD T , the vertex-saturated digraph G⃗^{(h)}(X^{0}) is obtained from the vertex-saturated digraph G⃗^{(h−1)}(X^{0}) by a reorientation of an arc x_{j} > x_{i} in it. We tighten the arc x_{j} > x_{i} in the digraph G⃗^{(h−1)}(X^{0}) and arc x_{i} > x_{j} in the digraph G⃗^{(h)}(X^{0}) at one vertex x_{i,j}. We obtain as a result same digraph H⃗(X^{0}) in both cases. Since the MPPs of graphs G⃗_{t}^{(h−1)}(X^{0}) and G⃗_{t}^{(h)}(X^{0}) are different, it follows, that in the graph H⃗_{t}(X^{0}) there are two distinct MPPs, non-coincident (thick) arcs which will form an even cycle C_{2k} (k ≥ 2), containing vertex x_{i,j}. Therefore, the arc x_{i} > x_{j}, marked as ”considered” in the digraph G⃗_{t}^{(h)}(X^{0}), belongs to the odd cycle C_{2k+1} (k ≥ 2 in this digraph.

We will specify a way to search for this odd cycle in the digraph G⃗(X^{0}). Let P^{(h−1)} and P^{(h)} be the MPP of graphs G⃗_{t}^{(h−1)}(X^{0}) and G⃗_{t}^{(h)}(X^{0}) re-

spectively. We will combine the paths of MPP of the graphs G⃗_{t}^{(h−1)}(X^{0}) and G⃗_{t}^{(h)}(X^{0}) and will remove coinciding arcs (except the leading arc of the graph G⃗_{t}^{(h)}(X^{0})). It is easy to see, that part of the remaining arcs of MPP P^{(h−1)} and P^{(h)} forms the odd cycle C_{2k+1} (k ≥ 2). It follows that such cycle includes (possibly not all) arcs of alternating cycle, which was constructed during the transition from the initial (not optimum) partition of the graph G⃗_{t}^{(h)}(X^{0}) into a paths of the required MPP P^{(h)}.□

Theorem 6. If the digraph G⃗(X^{0}) ∈ D(G) does not have odd cycles, then its deadlocked digraph can be found by construction of the sequence T_{1}, …, T_{m} of a RSD of this digraph.

This follows from Theorem 5.□

4 Co-vertex.

Let G⃗(X^{0}) be a vertex-saturated digraph, for which RSD T has been constructed. Further, assume that for the digraph G⃗^{(z)}(X^{0}) ∈ T a leading arc (x_{i}, x_{j}), marked as ”considered”, has been is found. According to Theorem 5 this arc will belong to some odd cycle C_{2k+1} (k ≥ 2), the arcs of which x_{l} > x_{i} and x_{i} > x_{j} are generators for the elementary fictitious arc x_{l} ≫ x_{j} of graph G⃗_{t}^{(z)}(X^{0}).

In this case in the digraph G⃗^{(z)}(X^{0}) = G⃗(X^{0}) we will introduce the additional vertex x′, which we will call the co-vertex of the disclosed cycle C_{2k+1} (k ≥ 2). With the co-vertex x′ we will connect the (k + 1) vertices of cycle such that the introduced co-vertex and remaining vertices of cycle C_{2k+1} form an independent set. We assert that the vertex x′ is joined by arcs with all such vertices of the cycle C_{2k+1}, which belong to the initiating set X^{0}, as well as with x_{i}, which is initial vertex for the leading arc x_{i} > x_{j} of the graph G⃗_{t}^{(z)}(X^{0}) = G⃗_{t}(X^{0}). The vertex x′ will be terminal for such arcs.

[figure: x_{1}; x_{2}; x_{3}; x_{4}; x_{5}; x_{6}; x_{7}; x_{8}; x_{9}; x_{10}; x_{1}; x_{2}; x_{3}; x_{4}; x_{6}; x_{7}; x_{8}; x_{10}; (a); (b); x_{5}; x_{9}; x_{1}; x_{2}; x_{3}; x_{4}; x_{6}; x_{7}; x_{8}; x_{10}; (c); x_{5}; x_{9}; x_{9}; x_{2}; x_{5}; x_{1}; x_{6}; x′; (d); x′]

Figure 2: Introducing of co-vertex

The process of introducing a co-vertex in a digraph is illustrated in fig. 2 (a), (b) and (c). In fig. 2 (a) vertex-saturated digraph is shown in a graph of transitive closure in which the vertex x_{9} is found to be marked. In fig. 2 (b) is shown a vertex-saturated digraph, obtained from the previous digraph by reorientation of the arc (x_{5}, x_{9}), in a graph of transitive closure for which the vertex x_{5} was found to be marked.

Now the leading arc (x_{9}, x_{5}) is marked as ”considered”, for the odd cycle C_{5}, determined by the vertices x_{1}, x_{2}, x_{5}, x_{6} and x_{9}, the co-vertex x′ (see fig. 2 (c)) is introduced. We see that the required odd cycle is easily identified by imposing the MPPs of the graphs of transitive closure for the digraphs, shown in fig. 2 (a) and 2 (b). The undirected cycle C_{5} and the introduced co-vertex are separately represented in fig. 2 (d). It is not difficult to see that the undirected cycle C_{2k+1} (k ≥ 2) of the digraph G(X^{0}) to which arc (x_{i}, x_{j}) belongs, is enclosed in the cycle C_{2k+2}, formed by vertices of cycle C_{2k+1} and the introduced covertex in the extended digraph G′′(X^{0}), and the digraph G′′(X^{0}) will never be vertex-saturated.

Let X_{1} ⊂ X(C_{2k+1}) be the set of all vertices of cycle C_{2k+1}, adjacent to the introduced co-vertex.

Further, we will connect co-vertex x′ by arcs to all vertices of the digraph G⃗(X^{0}), with which one vertex from the set X_{1} is connected.

As a result of these constructions, we obtain the extended digraph G⃗′(X^{0}) = (X′, Γ⃗′), where X′ = X ∪ {x′}.

Clearly, in the extended digraph G⃗′(X^{0}), the undirected cycle C_{2k+1} (k ≥ 2) of the digraph G⃗(X^{0}), to which arc (x_{i}, x_{j}) belongs, is inserted in the cycle C_{2k+2}, formed by the vertices of the cycle C_{2k+1} and introduced co-vertex, and the digraph G⃗′(X^{0}) will never be vertex-saturated.

Lemma 7. In the undirected graph G′ = (X′, Γ′) ∈ L_{n′}, which is obtained from the graph G = (X, Γ) ∈ Ln by the introduction in the latter some co-vertex x′ of the cycle C_{2k+1} (k ≥ 2), for any vertex x of this cycle, adjacent to the co-vertex, the following correlation exists:

Γ′x\X(C_{2k+1}) ⊂ Γ′x′\X(C_{2k+1}).

The result follows directly from the definition of a co-vertex.□

Theorem 8. Let G = (X, Γ) ∈ L_{n}. Further, let the graph G′ = (X′, Γ′) be obtained from the graph G by the introduction of some co-vertices. Then the MCP F′ of the graph G′ with Card(F) = Card(F′) can be found for any MCP F of the graph G.

Let the graph G = (X, Γ) ∈ L_{n} and the MCP F of the graph G be given. Further, let the graph G′ = (X′, Γ′) be obtained from the graph G by the introduction of some co-vertices.

Clearly, the relation Card(F′) > Card(F) is true for any MCP F′ of the graph G′.

We will now show that any MCP of the graph G′ can be obtained from any MCP F of the graph G by the connection of cliques from F to existing co-vertices.

In fact, by the definition, the co-vertex x′ is introduced in the graph G, when the odd cycle C_{2k+1} (k ≥ 2) is found. The co-vertex x′ is connected by edges with (k + 1) vertices of cycle C_{2k+1} so that it and the remaining k vertices of this cycle form the independent set. Then in MCP F′ there will be at least one vertex x of cycle C_{2k+1} adjacent to the co-vertex x′. Therefore, by Lemma 7, if the co-vertex x′ is connected to the clique MCP F′, to which the vertex x of cycle C_{2k+1} belongs, then we obtain a new clique of the extended graph G′.

After executing similar connections of all co-vertices of the graph G′ to cliques MCP F, we obtain MCP F′ of the graph G′ such that Card(F′) = Card(F′).□

Theorem 9. A deadlocked digraph G⃗^{(h)}(X^{0}) can be constructed for any vertex-saturated digraph G⃗(X^{0}) as result of a sequential construction of RSD T_{1}, …, T_{t} and, if necessary, by introduction of a co-vertex into given the digraph.

As a result of a introduction of a co-vertex the resulting odd cycle is enclosed in the even cycle C_{2k+1} (k ≥ 2), the validity of the assertion follows from Theorem 6.□

5 Algorithm CLIPAT

Let G⃗^{(h)}(X^{0}) be a deadlocked digraph.

Because the deadlocked digraph G⃗^{(h)}(X^{0}) is a directed mapping of some extended graph G′ = (X′, Γ′) ∈ L_{n′}, where n′ > n, then the MPP P^{(h)} of graph G⃗_{t}^{(h)}(X^{0}) determines, according to Lemma 3, a MCP F′ of graph G′.

The following statement defines main property of a deadlocked digraph.

Theorem 10. Let G⃗^{(h)}(X^{0}) be a deadlocked digraph. Then for any independent set U ⊂ X of the graph G ∈ L_{n}, in the digraph G⃗^{(h)}(X^{0}) there exist Card(U) non-intersecting cliques of graph G, each of which contains one of the vertices of the set U and belongs to one of the paths of MPP A^{(h)} of the graph G⃗_{t}^{(h)}(X^{0}).

Let G⃗^{(}h)(X^{0}) be a deadlocked digraph.

Clearly, if U ⊂ X is some independent set of vertices of the graph G = (X, Γ) ∈ L_{n}, according to the construction of a deadlocked digraph, the vertices of set U belong to various paths of a MPP P^{(}h) of the graph G⃗_{t}^{(h)}(X^{0}). We take into account, that if in each path of a MPP P^{(h)} of the graph G⃗_{t}^{(h)}(X^{0}), passing through a vertex of set U, we delete a co-vertex, then we will obtain set with Card(U) disjoint from the cliques of the graph G, each of which contains some vertex of the set U.□

Theorem 11. Let there be graph G ∈ L_{n} and G⃗^{(h)}(X^{0}) is a deadlocked digraph, obtained as result of construction of some system of a RSD. Then in the graph G⃗_{t}^{(h)}(X^{0}) there exists such MPP P, in which each clique of a MCP of graph G belongs to different its paths and B(P) = ⊘.

Let F be some MCP of the graph G ∈ L_{n}.

Further, let G⃗_{t}^{(h)}(X^{0}) be a graph of transitive closure of the deadlocked digraph G⃗^{(}h)(X^{0}), in which some MPP P^{(h)} has vertices not marked.

In the graph G⃗_{t}^{(h)}(X^{0}) we will designate vertices, belonging to different cliques from MCP F. Obviously, the designated vertices will form a set P of non-intersecting oriented paths of the graph G⃗_{t}^{(h)}(X^{0}), which contains all vertices of the graph G.

If G⃗^{(h)}(X^{0}) ∈ D(G), then all paths from P form the required MPP P of graph G⃗_{t}^{(h)}(X^{0}).

Otherwise we have G⃗^{(h)}(X^{0}) ∈ D(G⃗′), where G⃗ ⊂ G⃗′ i. e. the deadlocked digraph is an extended mapping of the graph G⃗′.

We will construct a new MPP P of the graph G⃗_{t}^{(h)}(X^{0}) in the following way. We will assign to P paths from P, i.e. vertices of each path of P we believe

belong to the same path of the constructed MPP P. The vertices of the assigned paths form some subgraph G⃗′_{t} of the graph G⃗_{t}^{(h)}(X^{0}).

Further, in the obtained subgraph G⃗′_{t} and subsequent subgraphs of the graph G⃗_{t}^{(h)}(X^{0}) we will introduce its co-vertices one by one. For example, in the order in which they were introduced during design of the deadlocked digraph.

At any time we will attach an introduced co-vertex as expansion of such path of a constructed MPP P, with which this co-vertex will form a clique. By Theorem 8 it is always possible.

The process of introduction of co-vertices is finished when the list of covertices are exhausted, and the next constructed subgraph G⃗′′_{t} coincides with the graph G⃗_{t}^{(h)}(X^{0}). Clearly, the resulting MPP P has no marked vertices.□

Theorem 12. The general number of co-vertices of the graph G⃗_{t}^{(h)}(X^{0}) is equal to O(n).

This result follows from Theorem 11.□

The obtained results make it possible to formulate an algorithm CLIPAT (CLIque PArTition) for finding the minimal partition of the graph G ∈ L_{n} into cliques.

We will formulate the main steps of the algorithm CLIPAT.

Let there be a graph G = (X, Γ) ∈ L_{n}, for example, given by adjacency matrix.

Step 1. Orient the edges of the graph G = (X, Γ) ∈ L_{n} so as to obtain the acyclic digraph G⃗(X^{0}), where X^{0} is the MIS of graph G.

The result of step 1 is an acyclic digraph G⃗(X^{0}) = (X, Γ⃗).

Step 2. Construct a vertex-saturated digraph G⃗(X^{0}) from the given acyclic digraph.

Step 3. Find the marked vertex x_{j} ∈ B(P) of minimum rank in the graph of transitive closure G⃗_{t}(X^{0}) of the vertex-saturated digraph G⃗(X^{0}) for the constructed MPP P. If B(P) = ⊘ then go to Step 8. Otherwise, we have the marked vertex x_{j} ∈ B(P) of minimum rank.

Step 4. Find a leading arc (x_{i}, x_{j}) in the graph G⃗_{t}(X^{0}) by the given marked vertex x_{j} ∈ B(P).

Step 5. If the leading arc (x_{i}, x_{j}) is marked as ”considered” then go to Step 7. Otherwise, reorient arc (x_{i}, x_{j}) and mark arc (x_{j}, x_{i}) as ”considered” in the new digraph G⃗(X^{0}) . Go to Step 6.

Step 6. If the new digraph G⃗(X^{0}) is vertex-saturated then return to Step 3. Otherwise, remove all marks of arcs in the digraph and go to Step 2.

Step 7. Find the undirected odd cycle _{2k+1} (k ≥ 2) of digraph G⃗(X^{0}) and introduce a co-vertex x′ for it. As the result we obtain the new digraph G⃗(X^{0}). Go to Step 2.

Step 8. If the digraph G⃗(X^{0}) is deadlocked and does not have co-vertices, then stop the calculations, as the required partition F of graph G into the minimum number of cliques has been found. Each element of MCP F is formed by the vertices of a corresponding path of MPP P of graph G⃗_{t}(X^{0}). If the deadlocked digraph has even one co-vertex, go to Step 9.

Step 9. Remove all co-vertices in the deadlocked digraph G⃗(X^{0}). Paths of MPP P of the graph G⃗_{t}(X^{0}), intersecting remaining vertices, determine the required MCP of the graph G = (X, Γ) ∈ L_{n}.

Theorem 13. The algorithm CLIPAT finds a partition of the graph G ∈ L_{n} into the minimum number of cliques within time O(n^{5}).

First of all we notice that the algorithm CLIPAT constructs some deadlocked digraph and consequently, according to Theorem 11, finds some MCP F of the graph G = (X, Γ) ∈ L_{n}.

Obviously the operating time of the algorithm is determined by the time of design of deadlocked digraph.

We will evaluate an operating time for each step of the algorithm CLIPAT. Step 1 is executed once and requires O(n^{2} ) time units, where n is number

of vertices of the graph G ∈ L_{n}, since it is necessary to orient each edge of the graph G.

For reception of a vertex-saturated digraph it is necessary, that each of its subgraphs, induced by the layer X^{k} (k = \overline{0, m}), be vertex-saturated with respect to this layer. Therefore it is necessary for each subgraph G⃗(X^{k}):

(a) Find the graph of transitive closure G⃗_{t}(X^{k}). It is necessary for this purpose to expend O(n_{k}^{3}) units of the time [5], where n_{k} is the number of vertices in the graph G⃗_{t}(X^{k}).

(b) To design a MPP of the graph G⃗_{t}(X^{k}), using an algorithm of search of the maximum matching in bipartite graph with 2n_{k} vertices, it is necessary to expend O(n_{k}^{5/2}) units of the time [4].

(c) Find the maximum antipath for each vertex x ∈ X^{k} ∪ ⋯ ∪ X^{m}. The time of search of one antipath is equal to O(n_{k}^{2}) – the time of design of an alternating tree. Therefore a total time to complete this step is equal to O(n_{k}^{3}).

(d) Check, whether each of found the maximum antipaths U(x) a graph G⃗_{t}(X^{k}) will be a MIS of a digraph G⃗(X^{k}). If it so, to finish design of a digraph G⃗(X^{k}), vertex-saturated with respect to initiating set X^{k}. Otherwise to fill a found antipath to a MIS and to construct a new acyclic digraph G⃗(X^{k}) and to return to item (a).

Items (a) – (d) can be repeated. One completion of these steps requires O(n_{k}^{3}) time units. Assuming, that for each completion of the steps an increase of the maximum antipath at one vertex occurs, we obtain a time of design of a digraph G⃗(X^{k}), vertex-saturated with respect to initiating set, is equal to O(n_{k}^{4}).

Hence the time of design of a correctly constructed vertex-saturated digraph G⃗(X^{0}) is equal to:

∑_{∀n_{k}} O(n_{k}^{4}) = h,

where n_{0} + ⋯ + n_{m} = n.

The size h is maximal, if n_{0} = ⋯ = n_{m}. Hence we have:

h = O((m + 1)(\frac{n}{m + 1})^{4}) = O(n^{5})

.

The time for completion Step 3 is equal to, obviously, O(n^{2}).

The time for completion of Step 4 is equal to the time of the breadth-first search of the graph and is equal to O(n^{2}).

Step 5 requires one unit of the time.

The time for completion of Step 6 is equal to the time of required for completion of steps (a) – (d) during the design of a vertex-saturated digraph. It is possible this time to believe is equal to O(n^{3}).

The time of search of an odd cycle is equal to the time of depth-first search in a graph and is equal to O(n^{2}). Assuming the time to input a co-vertex is equal to O(n^{3}), we conclude, that the time for completion of Step 7 is equal to O(n^{3}).

Obviously steps 3 – 7 can be repeated not more then n^{2} times. Therefore the time of design of deadlocked digraph will be equal to O(n^{5}).

Steps 8 – 9 will not change the estimation.□

References

[1] Garey M.R., Johnson D. S. Computers and Intractability (W.H.Freeman and Company, San Francisco, 1979).

[2] Ford L.R., Fulkerson D.R. Flows in Networks (Princeton University press, Princeton, New Jersey, 1962).

[3] Christofides N. Graph theory (Academic press, New York, London, San Francisco, 1975).

[4] Papadimitriou C.H., Steiglitz K. Combinatorial optimization: Algorithms and Complexity (Prentice-hall Inc., Engiewood Cliffs, New Jersey, 1982).

[5] Swamy M.N.S., Thulasiraman K. Graphs, Networks and Algorithms (A Wiley Interscience Publication, John Wiley & Sons, New York, Chichester, Brisbane, Toronto, 1981).

[6] Tarjan R.E. Complexity of combinatorial algorithms, SIAM Rew., 20, N 3, (1978) 457–491.