A Multilevel Bilinear Programming Algorithm For the Vertex Separator Problem
Authors:
- William W. HagerWHWilliam W. Hager
- James T. HungerfordJHJames T. Hungerford
- Ilya SafroISIlya Safro
Preprint
Abstract
The Vertex Separator Problem for a graph is to find the smallest collection of vertices whose removal breaks the graph into two disconnected subsets that satisfy specified size constraints. In the paper 10.1016/j.ejor.2014.05.042, the Vertex Separator Problem was formulated as a continuous (non-concave/non-convex) bilinear quadratic program. In this paper, we develop a more general continuous bilinear program which incorporates vertex weights, and which applies to the coarse graphs that are generated in a multilevel compression of the original Vertex Separator Problem. A Mountain Climbing Algorithm is used to find a stationary point of the continuous bilinear quadratic program, while second-order optimality conditions and perturbation techniques are used to escape from either a stationary point or a local maximizer. The algorithms for solving the continuous bilinear program are employed during the solution and refinement phases in a multilevel scheme. Computational results and comparisons demonstrate the advantage of the proposed algorithm.Keywords
All Related Versions
This publication has 16 references indexed in Scilit:
- Optimality conditions for maximizing a function over a polyhedronMathematical Programming, 2013
- Partitioning Hypergraphs in Scientific Computing Applications through Vertex Separators on GraphsSIAM Journal on Scientific Computing, 2012
- Algebraic Distance on GraphsSIAM Journal on Scientific Computing, 2011
- Relaxation-Based Coarsening and Multiscale Graph OrganizationMultiscale Modeling & Simulation, 2011
- Graph minimum linear arrangement by multilevel weighted edge contractionsJournal of Algorithms, 2006
- Multigrid Solvers and Multilevel Optimization Strategies2003
- Finding good approximate vertex and edge partitions is NP-hardInformation Processing Letters, 1992
- Partitioning Sparse Matrices with Eigenvectors of GraphsSIAM Journal on Matrix Analysis and Applications, 1990
- A parallel graph partitioning algorithm for a message-passing multiprocessorLecture Notes in Computer Science, 1988
- An Efficient Heuristic Procedure for Partitioning GraphsBell System Technical Journal, 1970