=Paper=
{{Paper
|id=Vol-1623/paperco16
|storemode=property
|title=Separation Problem for k-parashuties
|pdfUrl=https://ceur-ws.org/Vol-1623/paperco16.pdf
|volume=Vol-1623
|authors=Inna Urazova, Ruslan Simanchev
|dblpUrl=https://dblp.org/rec/conf/door/UrazovaS16
}}
==Separation Problem for k-parashuties==
https://ceur-ws.org/Vol-1623/paperco16.pdf
Separation Problem for k-parashuties
Inna Urazova1 and Ruslan Simanchev1,2
1
Omsk State University, 55a Mira avenue, 644077 Omsk, Russia
urazovainn@mail.ru
2
Omsk Scientific Center of SB RAS, 15 Marksa avenue, 644024 Omsk, Russia
osiman@rambler.ru
Abstract. 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.
Keywords: polytope, facet inequality, separation problem.
1 Introduction
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 finding M-graph H minimizing the functional
ρG (H) = |EG ∪ EH| − |EG ∩ EH| (1)
on set µ(V ). Here EG and EH are sets of edges of G and H, respectively. In other
words, it is necessary to find 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 first to state graph approximation problem in [10] in 1955. In the
1960s-1970s in a number of works non-trivial classes of graphs on which the problem
is polynomially solvable [7, 18] . In 1986 Krivanek and Moravek considered graph ap-
proximation problem as a particular case of the tree clusterization and proved that
it was NP-hard [11] . Systematic studies of graph approximation problem began in
the last decade when the problem was re-discovered under different names (correla-
tion clustering; Cluster editing) by different groups of authors [3, 4, 13]. In particular,
the NP-hardness of its various options was established [1, 3, 13] and suggested first ap-
proximate algorithms with the guaranteed accuracy evaluation [3, 5, 8]. The best of the
currently known graph approximation algorithms finds a guaranteed solution by factor
of max. 2.5 worse than the optimum one [2, 17].
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
110 I. Urazova, R. Simanchev
In this work which continues the work [16] we consider polyheldral setting of the
graph approximation problem. The polyhedral approach to the solution of extreme com-
binatorial problems consists in the correlation of the problem with a special polytope
set as a convex hull of incidence vectors of the admissible solutions and, consequently,
the use of convex analysis and integer programming means. In this route a special role
belongs to the task of polytope description as a set of solutions to the system of linear
equations and inequalities. If a full linear description of the polytope is available, the
extreme combinatorial problem reduces to the linear programming problem (possibly -
with exponential number of constraints) which quite often enables obtaining effective
algorithms for the solution thereof. One of the most widely known examples of such
a situation is problem of maximum weighted matching [6, 12]. As a rule, for NP-hard
problems a full liner description of the polytope is not known (see, e.g., [9]). Never-
theless, the availability of a partial description, i.e., classes of valid, support or facet
inequalities enables building evaluations of the target function optimum value, develop
special cutting plane procedures.
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 ∈ E we will also use uv notation, where u and v are
vertices from V incident to edge e. For D ⊆ Kn and u ∈ 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 n 2−n by
2
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 ∈ RE and R ⊆ E, then we denote linear form xe via x(R). The incidence vector
e∈R
of the arbitrary graph D ⊆ Kn without isolated vertices is called vector xD ∈ RE with
components xD e = 1 at e ∈ ED and xe = 0 at e ∈
D
/ ED. The latter rule, obviously, sets
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 finite number of
points. Linear inequality aT x ≤ a0 (a, x ∈ RE , a ̸= 0, a0 ∈ R, ”T ” transposition sign)
is called support to P if it is fulfilled 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 {x ∈ P |aT x = a0 } 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.
Separation Problem for k-parashuties 111
Facet inequalities are present (with the equivalency accuracy) in any linear descrip-
tion of the polytope [14, 12]. Besides, they proved to be good as cutting planes for the
solution of high dimensionality problems (see, e.g., [15, 9]).
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̄ ∈ RE . It is required
to find 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 combinato-
rial problems and inequality classes for which the separation problem is polynomially
solvable, for example, travelling salesman problem and subtour elimination inequalities
[9], the problem of building a multi-processor schedule and inequality class induced by
the paths in the precedence graph [15] etc. are known. In this work NP-hardness of
the separation problem of k-parachute class inequalities relative to M-graph polytope
is proved.
2 M -graph polytope and k-parachutes
We will refer to the set
Pn = conv{xH ∈ RE |H ∈ µ(V )}
as an M-graph polytope. Here ”conv” means ”convex hull”.
In [16] it was prove that (0, 1)-vector x ∈ RE is the vector of incidences of M -graph
if and only if it satisfies the system:
−xuv + xuw + xvw ≤ 1
xuv − xuw + xvw ≤ 1, (2)
xuv + xuw − xvw ≤ 1
where u, v, w ∈ V are all kinds of sets of three pairwise different vertices,
xuv ≥ 0 for all uv ∈ E. (3)
Besides, in the same work it was demonstrated that the target function (1) in terms
of RE may be written as
ρG (x) = |EG| + x(E Ḡ) − x(EG). (4)
Therefore, graph approximation problem may be stated as a problem of integer linear
programming (2)–(4).
Let U = {u1 , u2 , . . . , uk } and W = {v1 , v2 , . . . , vp } 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 ui vj , 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
called a k-parachute. We will correlate inequality
k2 + k
x(ET ) − x(EKp ) ≤ .
2
112 I. Urazova, R. Simanchev
with this graph. In [16] it was proved that this inequality induced by k-parachute T ∪Kp
is support inequality to polytope Pn if and only if p ≥ k , and facet inequality if and
only if k = 1.
3 Separation Problem
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 separa-
tion problem stronger than it was done in the Introduction.
Problem A. Let x̄ ∈ RE and 0 ≤ x̄ ≤ 1. Does L class contain such an inequality for
2
which x̄(ET ) − x̄(EKp ) > k 2+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 rel-
ative 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 = {u}.
In this case Problem A may be re-stated as follows:
Problem B. Let x̄ ∈ RE and 0 ≤ x̄ ≤ 1. Is there among inequalities of the type
∑p ∑ ∑
p−1 p
xuvj − xvi vj ≤ 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 fixed. Now at preset point x̄ ∈ RE ,
0 ≤ x̄ ≤ 1 and vertex u ∈ V we will define vector c ∈ RE :
{
x̄e , e ∈ δ(u);
ce =
−x̄e , e ∈ E \ δ(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 < |V G|. Does graph G contain clique of the order larger
than s?
So, let what is given be graph G, |V G| = 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 ∪ {u}
where u is an added vertex. Let us assign the following weights to Kn edges:
1
s , e ∈ δ(u);
ce = 0, e ∈ EG;
1
− s , e ∈ E Ḡ,
where Ḡ is the complement of graph G.
Separation Problem for k-parashuties 113
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 ∪ {u} we have c(EK ′ ) > 1.
Let us suppose that in graph Kn (c, u) there is clique K̄ ⊂ Kn (c, u) such that
c(E K̄) > 1. Because only edges from δ(u) have positive weights, then necessarily
u ∈ V K̄. It means that clique K̄ may be presented as K̄ = δK̄ (u) ∪ K where K is
clique in G ∪ Ḡ. Clique K , in it turn may be represented as K = (K ∩ G) ∪ (K ∩ Ḡ).
Therefore, K̄ = δK̄ (u) ∪ (K ∩ G) ∪ (K ∩ Ḡ). Because edge sets of these three graphs
do not overlap pairwise, then
c(E K̄) = c(δK̄ (u)) + c(E(K ∩ G)) + c(E(K ∩ Ḡ)) =
1 1 1
= |V K| − |E(K ∩ Ḡ)| = (|V K| − |E(K ∩ Ḡ)|) > 1.
s s s
Hence, particularly, it follows that |V K| > |E(K ∩ Ḡ)|. Let us note that the with-
drawal of edges E(K ∩ Ḡ) from clique K gives exactly K ∩ G graph which, first,
lies fully in G, and second, by virtue of the lemma, contains clique of the order
|V K| − |E(K ∩ Ḡ)| > s.
The theorem is proved.
4 Conclusion
This article continues the work [16] in which facet inequalities to the graph approxi-
mation problem polytope is built. The next step in this direction is the inclusion of the
received facet inequalities into polyhedral type algorithms. The effectiveness of this in-
clusion depends essentially on the computational difficulties of the separation problem
of inequalities. In this work N P -hardness of the separation problem of k-parachutes
relative to M -graph polytope is proved. The most natural direction for further research
is the development of heuristics to separation problem.
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 first
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 con-
straints (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 first 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.
114 I. Urazova, R. Simanchev
Table 1.
n N umber of variables SR(mean time, sec) PR(mean time, sec)
10 45 0.16 0.23
15 105 0.66 1.99
20 190 46.91 35.35
25 300 6566.36 1464.68
References
1. Ageev A.A., Il’ev V.P., Kononov A.V., Talevnin A.S.: Computational complexity of the
graph approximation problem. J. of Applied and Industrial Mathematics. vol. 1, Issue 1,
1–8 (2007)
2. Ailon N., Charikar M., Newman A.: Aggregating inconsistent information: Ranking and
clustering. J. ACM. 55, 5, 1–27 (2008)
3. Bansal N., Blum A., Chawla S.: Correlation clustering. Machine Learning. 56, 89–113 (2004)
4. Ben-Dor A., Shamir R., Yakhimi Z.: Clustering gene expression patterns. J. Comput. Biol.
6, 3–4, 281–297 (1999)
5. Charikar M., Guruswami V., Wirth A.: Clustering with qualitative information. J. Comput.
Syst. Sci. 71, 3, 360–383 (2005)
6. Edmonds J.: Maximum matching and a polyhedron with 0,1 - vertices. J. of Research
National Bureau of Standards. Section B, 69, 125–130 (1965)
7. Fridman G. Sh.: A Problem of Graph Approximation (Russian). Upravlyaemye Sistemy. 8,
73–75 (1971)
8. Giotis I., Guruswami V.: Correlation clustering with a fixed number of clusters. Theory of
Computing. 2, 1, 249–266 (2006)
9. Grotschel M., Holland O.: Solution of large-scale symmetric travelling salesman problems.
Mathematical Programming. 51, 2, 141–202 (1991)
10. Harary, F.: On the notion of balance of a signed graph. Michigan Mathematical Journal.
2, 143–146 (1955)
11. Křivánek M., Morávek J.: NP-hard problems in hierarchical-tree clustering. Acta infor-
matica. 23, 311–323 (1986)
12. Schrijver, A.: Combinatorial Optimization. Polyhedra and Efficiency. Springer, Heidelberg
(2004)
13. Shamir R., Sharan R., Tsur D.: Cluster graph modification problems. J. Discrete Applied
Mathematics. 144, 1–2, 173–182 (2004)
14. Simanchev R.Yu.: Convex Polytope and Facet inequalities (Russian). Omsk State Univer-
sity, Omsk (1999)
15. Simanchev R.Yu., Urazova I.V.: Scheduling unit-time jobs on parallel processors polytope
(Russian). Diskretnyi Analiz i Issledovanie Operatsii. 18(11), 85–97 (2011)
16. Simanchev, R.Yu., Urazova, I.V.: On the Polytope Faces of the Graph Approximation
Problem. J. of Applied and Industrial Mathematics. vol. 9, 2, 283–291 (2015)
17. van Zuylen A., Williamson D.P.: Deterministic Pivoting Algorithms for Constrained Rank-
ing and Clustering Problems. Mathematics of Operations Research. 34, 3, 594–620 (2009)
18. Zahn C. T.: Approximating symmetric relations by equivalence relations. J. of the Society
for Industrial and Applied Mathematics. 12, 4, 840–847 (1964)