The generalized vertex cover problem and some variations

DOI10.1016/J.DISOPT.2018.06.004MaRDI QIDQ1756348zbMATH OpenOpenAlexWikidataFDO

Authors Pooja Pandey, Abraham P. Punnen

Publication date 14 January 2019

Published in Discrete Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1708.03703

zbMATH Keywords

0-1 programmingalgorithmscomplexitygeneralized vertex coverquadratic programming

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Integer programming (90C10) Quadratic programming (90C20)

Abstract: In this paper we study the generalized vertex cover problem (GVC), which is a generalization of various well studied combinatorial optimization problems. GVC is shown to be equivalent to the unconstrained binary quadratic programming problem and also equivalent to some other variations of the general GVC. Some solvable cases are identified and approximation algorithms are suggested for special cases. We also study GVC on bipartite graphs and identify some polynomially solvable cases. We show that GVC on bipartite graphs is equivalent to the bipartite unconstrained 0-1 quadratic programming problem. Integer programming formulations of GVC and related problems are presented and establish half-integrality property on some variables for the corresponding linear programming relaxations. We also discuss special cases of GVC where all feasible solutions are independent sets or vertex covers. These problems are observed to be equivalent to the maximum weight independent set problem or minimum weight vertex cover problem along with some algorithmic results.

Recommendations

• Exact solutions to generalized vertex covering problems: a comparison of two models
• The minimum generalized vertex cover problem
• Algorithms - ESA 2003
• The maximum vertex coverage problem on bipartite graphs
• scientific article; zbMATH DE number 2119748

Cites work

• A Graph-Theoretic Equivalence for Integer Programs
• A polynomial case of unconstrained zero-one quadratic optimization
• A solvable case of quadratic 0-1 programming
• A Tight Linearization and an Algorithm for Zero-One Quadratic Programming Problems
• An effective modeling and solution approach for the generalized independent set problem
• An extension of the Nemhauser-Trotter theorem to generalized vertex cover with applications
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Approximation algorithms for NP-complete problems on planar graphs
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Average value of solutions for the bipartite Boolean quadratic programs and rounding algorithms
• Efficient Computation of the Binary Vector That Maximizes a Rank-Deficient Quadratic Form
• Exact solutions to generalized vertex covering problems: a comparison of two models
• scientific article; zbMATH DE number 3889282 (Why is no real title available?)
• scientific article; zbMATH DE number 1219584 (Why is no real title available?)
• Minimum cuts and related problems
• On an approximation measure founded on the links between optimization and polynomial approximation theory
• Optimization procedures for the bipartite unconstrained 0-1 quadratic programming problem
• Polynomially solvable cases of binary quadratic programs
• Relaxations of vertex packing
• Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations
• Solving the fixed rank convex quadratic maximization in binary variables by a parallel zonotope construction algorithm
• Structure preserving reductions among convex optimization problems
• The bipartite unconstrained 0-1 quadratic programming problem: polynomially solvable cases
• The Boolean quadratic polytope: Some characteristics, facets and relatives
• The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds
• The minimum generalized vertex cover problem
• The travelling salesman problem: new solvable cases and linkages with the development of approximation algorithms
• The unconstrained binary quadratic programming problem: a survey
• Vertex packings: Structural properties and algorithms

Cited in

(7)

• Vertex Cover Reconfiguration and Beyond
• Extension of the Nemhauser and Trotter Theorem to Generalized Vertex Cover with Applications
• Exact solutions to generalized vertex covering problems: a comparison of two models
• Introduction to QUBO
• Complexity and polynomially solvable special cases of QUBO
• Parameterized Reductions and Algorithms for Another Vertex Cover Generalization
• Algorithms - ESA 2003

This page was built for publication: The generalized vertex cover problem and some variations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1756348)