This article continues the work [16] in which polyhedral setting of graph approximation problem is provided, support inequalities to polytope are built. In this work NP-hard of the separation problem of k-parachutes relative to M-graph polytope is proved. Let Kn = (V; E) be a complete unoriented graph without loops and multipe edges. Spanning subgraph H Kn is called M-graph if each of its connected components is a clique or single-vertex graph. We denote a set of all M-graphs in Kn through (V ). Let G Kn be some a priori set spanning subgraph. Approximation problem of G consists in nding M-graph H minimizing the functional
G(H) = jEG [ EHj jEG \ EHj (1) on set (V ). Here EG and EH are sets of edges of G and H, respectively. In other words, it is necessary to nd such a set of pairwise non-overlapping cliques at V which is as far as possible less (in terms of edges) different from G.
Harary was the rst to state graph approximation problem in [
Copyright ⃝c by the paper's authors. Copying permitted for private and academic purposes. In: A. Kononov et al. (eds.): DOOR 2016, Vladivostok, Russia, published at http://ceur-ws.org
In this work which continues the work [
To state the results of this article, we will introduce the following designations and notions. For any graph D Kn via V D and ED we will denote a set of its vertices and edges, respectively. For an edge e 2 E we will also use uv notation, where u and v are vertices from V incident to edge e. For D Kn and u 2 V via D(u) we will denote the set of edges of the D incident to vertex u. If D = Kn, then in this notation we will omit index D. Each set of edges R E induces in Kn some subgraph T in which ET = R and V T is a set of vertices incident to edges from R. If no ambiguity arises, a graph induced by a set of edges R will be denoted via R. For subgraphs D; F Kn we assume
D [ F = ED [ EF; D \ F = ED \ EF:
We will correlate graph Kn with a Euclidean space RE of dimensions n22 n by correlating each edge with a coordinate axis in RE . This space may be considered as a space of column vectors with the components indexed by elements from E. If x 2 RE and R E, then we denote linear form ∑ xe via x(R). The incidence vector e2R of the arbitrary graph D Kn without isolated vertices is called vector xD 2 RE with components xD = 1 at e 2 ED and xD = 0 at e 2= ED. The latter rule, obviously, sets e e a one-to-one correspondence between the set of all subgraphs without isolated vertices of Kn and the set of vertices of the unit cube in RE .
A set P RE is called a polytope if it is a convex hull of a nite number of points. Linear inequality aT x a0 (a; x 2 RE ; a ̸= 0; a0 2 R; "T " transposition sign) is called support to P if it is ful lled for any point from P and there exists at least one point from P converting it into an equality. Any inequality support to P generates the set fx 2 P jaT x = a0g which is called the face of the polytope P . Maximum by the inclusion faces of the polytope are called facets. It is clear that a facet is the face and only the face the dimensionality of which is by 1 smaller than the dimensionality of the polytope itself. A support inequality generating a facet will, consequently, be referred to as a facet inequality.
Facet inequalities are present (with the equivalency accuracy) in any linear
description of the polytope [
During the development of cutting plane procedures using support inequalities the
separation problem goes to the foreground. It consists in the following. What is given
is a class of inequalities L support to polytope P and point x 2 RE . It is required
to nd an inequality in the class L strictly separating the point x from polytope P ,
or prove that in L such an inequality does not exist. Examples of extreme
combinatorial problems and inequality classes for which the separation problem is polynomially
solvable, for example, travelling salesman problem and subtour elimination inequalities
[
We will refer to the set
Pn = convfxH 2 RE jH 2 (V )g as an M-graph polytope. Here "conv" means "convex hull".
In [
Besides, in the same work it was demonstrated that the target function (1) in terms of RE may be written as
G(x) = jEGj + x(EG) x(EG): called a k-parachute. We will correlate inequality Therefore, graph approximation problem may be stated as a problem of integer linear programming (2){(4).
Let U = fu1; u2; : : : ; ukg and W = fv1; v2; : : : ; vpg be nonempty subsets of set V ,
U \ W = ∅, k 1, p 2 . We will designate star in Kn with the centre in vertex
ui and arms uivj ; j = 1; 2; : : : ; p through Ti; i = 1; 2; : : : ; k. We will denote the clique
k
on the set of vertices W through Kp. Let us assume that T = ∪ Ti. Graph T [ Kp is
i=1
x(ET )
x(EKp)
k2 + k
where u; v; w 2 V are all kinds of sets of three pairwise different vertices,
xuv + xuw + xvw
xuv xuw + xvw
xuv + xuw xvw
1
1;
1
xuv
0 for all uv 2 E:
(2)
(3)
(4)
with this graph. In [
Let L be a class of support inequalities to polytope Pn induced by k-parachutes. Whereas polytope Pn completely lies in the unit cube of RE , we will state the separation problem stronger than it was done in the Introduction.
Problem A. Let x 2 RE and 0 x 1. Does L class contain such an inequality for which x(ET ) x(EKp) > k22+k ?
We need auxiliary fact, which is easily proved by induction.
Lemma 1. If any t edges with t < n are withdrawn from the complete n-vertex graph, the remaining graph will contain clique of the order n t.
Theorem 1. The separation problem for the inequalities induced by k-parachutes relative to the polytope of the graph approximation problem is NP-hard. Proof. Let us prove that this problem is NP-hard already at k = 1, i.e., at U = fug. In this case Problem A may be re-stated as follows:
Problem B. Let x 2 RE and 0 x 1. Is there among inequalities of the type p p 1 p ∑ xuvj ∑ ∑ xvivj 1 such an inequality which is violated by point x? j=1 i=1 j=2;j>i
It is clear that in this problem u vertex may be xed. Now at preset point x 2 RE , 0 x 1 and vertex u 2 V we will de ne vector c 2 RE : ce = { xe; e 2 (u);
xe; e 2 E n (u).
We will denote this edge weighted graph via Kn(c; u). It is not difficult to see that Problem B is equivalent to the following problem.
Problem C. Does this edge weighted graph Kn(c; u) contain such clique K that c(EK) > 1?
Let us reduce CLIQUE problem stated as follows to Problem C: what is given is graph G and natural number s < jV Gj. Does graph G contain clique of the order larger than s?
So, let what is given be graph G, jV Gj = m and a natural number s < m. Let us assume that n = m + 1 and build a complete graph Kn on a set of vertices V G [ fug where u is an added vertex. Let us assign the following weights to Kn edges: ce = 8 1 ; e 2 (u); < s
0; e 2 EG; : 1s ; e 2 EG, where G is the complement of graph G.
Let us note that if in graph G there is clique K of the order larger than s, then for the clique K′ Kn(c; u) on the set of vertices V K [ fug we have c(EK′) > 1.
Let us suppose that in graph Kn(c; u) there is clique K Kn(c; u) such that c(EK) > 1. Because only edges from (u) have positive weights, then necessarily u 2 V K. It means that clique K may be presented as K = K (u) [ K where K is clique in G [ G. Clique K , in it turn may be represented as K = (K \ G) [ (K \ G). Therefore, K = K (u) [ (K \ G) [ (K \ G). Because edge sets of these three graphs do not overlap pairwise, then = c(EK) = c( K (u)) + c(E(K \ G)) + c(E(K \ G)) = 1 1 1 s jV Kj s jE(K \ G)j = s (jV Kj jE(K \ G)j) > 1:
Hence, particularly, it follows that jV Kj > jE(K \ G)j. Let us note that the withdrawal of edges E(K \ G) from clique K gives exactly K \ G graph which, rst, lies fully in G, and second, by virtue of the lemma, contains clique of the order jV Kj jE(K \ G)j > s.
The theorem is proved. 4
This article continues the work [
In conclusion, we will announce preliminary results of our numerical experiment. The aim of the experiment is the evaluation of the use of 1-parachutes in cutting plane and branch-bound algorithms to solve the graph approximation problem. Below are brief results which are as follows. We solve two integer linear programm. The rst problem have function (4) as an objective function and have polyhedron (2){(3) as a relaxation set. In the second problem, we change the polyhedron, adding to the constraints (2){(3) all 1-parachute inequalities. This, of course, imposes serious restrictions on the dimension of the problem. To solve this problem we used IBM ILOG CPLEX Optimization Studio package and Intel(R) Celeron(R) CPU N2830 2.16GHz. Solution time was limited to 2 hours. More than a hundred problems with different objective functions of the form (4) for n 25 were solved. Table 1 shows the average solving time for the rst type and second type problems (columns SR and PR, respectively). As the table shows, the addition of 1-parachutes greatly reduces the time to solve the problem.
The authors are grateful to A.V. Kononov for useful advice received when working on an article.