Premium
Solving minimum K‐cardinality cut problems in planar graphs
Author(s) -
Bruglieri Maurizio,
Maffioli Francesco,
Trubian Marco
Publication year - 2006
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20129
Subject(s) - combinatorics , maximum cut , mathematics , cardinality (data modeling) , discrete mathematics , planar graph , vertex (graph theory) , graph , computer science , data mining
The present work tackles a recent problem in the class of cardinality constrained combinatorial optimization problems for the planar graph case: the minimum k ‐cardinality cut problem. Given an undirected edge‐weighted connected graph the min k ‐cardinality cut problem consists in finding a partition of the vertex set V in two sets V 1 , V 2 such that the number of the edges between V 1 and V 2 is exactly k and the sum of the weights of these edges is minimal. Although for general graphs the problem is already strongly ‐hard, we have found a pseudopolynomial algorithm for the planar graph case. This algorithm is based on the fact that the min k ‐cardinality cut problem in the original graph is equivalent to a bi‐weighted exact perfect matching problem in a suitable transformation of the geometric dual graph. Because the Lagrangian relaxation of cardinality constraint yields a max cut problem and max cut is polynomially solvable in planar graphs, we also develop a Lagrangian heuristic for the min k ‐cardinality cut in planar graphs. We compare the performance of this heuristic with the performance of a more general heuristic based on a Semidefinite Programming relaxation and on the Goemans and Williamson's random hyperplane technique. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 48(4), 195–208 2006