article

Vertex packings: Structural properties and algorithms

Authors:

G. L. Nemhauser,

L. E. Trotter, Jr.Authors Info & Claims

Mathematical Programming: Series A and B, Volume 8, Issue 1

Pages 232 - 248

https://doi.org/10.1007/BF01580444

Published: 01 December 1975 Publication History

Abstract

We consider a binary integer programming formulation (VP) for the weighted vertex packing problem in a simple graph. A sufficient "local" optimality condition for (VP) is given and this result is used to derive relations between (VP) and the linear program (VLP) obtained by deleting the integrality restrictions in (VP). Our most striking result is that those variables which assume binary values in an optimum (VLP) solution retain the same values in an optimum (VP) solution. This result is of interest because variables are (0, 1/2, 1). valued in basic feasible solutions to (VLP) and (VLP) can be solved by a "good" algorithm. This relationship and other optimality conditions are incorporated into an implicit enumeration algorithm for solving (VP). Some computational experience is reported.

References

[1]

E. Balas and H. Samuelsson, "Finding a minimum node cover in an arbitrary graph", Management Sciences Research Rept. No. 325, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, Pa. (November 1973).

[2]

M.L. Balinski, "On maximum matching, minimum covering and their connections", in: H.W. Kuhn, ed., Proceedings of the Princeton symposium on mathematical programming, (Princeton University Press, Princeton, N.J., 1970) pp. 303-312.

[3]

C. Berge, The theory of graphs and its applications (Methuen, London, 1962).

[4]

V. Chvatal, "On certain polytopes associated with graphs", Centre de Recherches Mathematiques-238, Universite de Montreal (October 1972).

[5]

V. Chvatal, "Edmonds polytopes and a hierarchy of combinatorial problems", Discrete Mathematics 5 (1973) 305-337.

Digital Library

[6]

J. Edmonds, "Covers and packings in a family of sets", Bulletin of the American Mathematical Society 68 (1962) 494-499.

[7]

J. Edmonds, "Paths, trees, and flowers", Canadian Journal of Mathematics 17 (1965) 449-467.

[8]

L.R. Ford, Jr. and D.R. Fulkerson, Flows in networks (Princeton University Press, Princeton, N.J., 1962).

[9]

D.R. Fulkerson, "Anti-blocking polyhedra", Journal of Combinatorial Theory 12 (1972) 50-71.

[10]

F. Gavril, "Algorithms for minimum coloring, maximum clique, minimum covering by cliques and maximum independent set of a chordal graph", SIAM Journal of Computing 1 (1972) 180-187.

[11]

A.M. Geoffrion, "An improved implicit enumeration approach for integer programming", Operations Research 17 (1969) 437-454.

Digital Library

[12]

R.M. Karp, "Reducibility among combinatorial problems", in: R.E. Miller, J.W. Thatcher and J.D. Bohlinger, eds.; Complexity of computer computations (Plenum Press, New York, 1972) pp. 85-103.

[13]

C.E. Lemke, H.M. Salkin and K. Spielberg, "Set covering by single branch enumeration with linear programming subproblems", Operations Research 19 (1971) 998-1022.

Digital Library

[14]

G.L. Nemhauser and L.E. Trotter, Jr., "Properties of vertex packing and independence system polyhedra", Mathematical Programming 6 (1974) 48-61.

Digital Library

[15]

M. Padberg, "On the facial structure of set packing polyhedra", Mathematical programming 5 (1973) 199-216.

Digital Library

[16]

R. Tarjan, "Finding a maximum clique", Tech. Rept. 72-123, Dept. of Computer Science, Cornell University, Ithaca, N.Y. (March 1972).

[17]

L.E. Trotter, Jr., "Solution characteristics and algorithms for the vertex packing problem", Tech. Rept. No. 168, Dept. of Operations Research, Cornell University, Ithaca, N.Y. (January 1973).

[18]

L.E. Trotter, Jr., "A class of facet producing graphs for vertex packing polyhedra", Research Rept, No. 78, Dept. of Administrative Sciences, Yale University, New Haven, Conn. (February 1974).

Cited By

Lu TXiao HFang Q(2024)Approximate core allocations for edge cover gamesTheoretical Computer Science10.1016/j.tcs.2024.114433991:COnline publication date: 12-Apr-2024
https://dl.acm.org/doi/10.1016/j.tcs.2024.114433
Donkers HJansen B(2024)Preprocessing to reduce the search spaceJournal of Computer and System Sciences10.1016/j.jcss.2024.103532144:COnline publication date: 18-Jul-2024
https://dl.acm.org/doi/10.1016/j.jcss.2024.103532
Dekker DJansen B(2024)Kernelization for feedback vertex set via elimination distance to a forestDiscrete Applied Mathematics10.1016/j.dam.2023.12.016346:C(192-214)Online publication date: 31-Mar-2024
https://dl.acm.org/doi/10.1016/j.dam.2023.12.016
Show More Cited By

Vertex packings: Structural properties and algorithms
1. Mathematics of computing
  1. Discrete mathematics
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Fractional programming formulation for the vertex coloring problem

We devise a new formulation for the vertex coloring problem. Different from other formulations, decision variables are associated with pairs of vertices. Consequently, colors will be distinguishable. Although the objective function is fractional, it can ...
Minimum vertex blocker clique problem

We study the minimum vertex blocker clique problem VBCP,1 which is to remove a subset of vertices of minimum cardinality in a weighted undirected graph, such that the maximum weight of a clique in the remaining graph is bounded above by a given integer ...
The min-cut and vertex separator problem

We consider graph three-partitions with the objective of minimizing the number of edges between the first two partition sets while keeping the size of the third block small. We review most of the existing relaxations for this min-cut problem and focus ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Mathematical Programming: Series A and B

Mathematical Programming: Series A and B Volume 8, Issue 1

December 1975

391 pages

ISSN:0025-5610

Issue’s Table of Contents

Copyright © Copyright © 1975 The Mathematical Programming Society.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 December 1975

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

195
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 10 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lu TXiao HFang Q(2024)Approximate core allocations for edge cover gamesTheoretical Computer Science10.1016/j.tcs.2024.114433991:COnline publication date: 12-Apr-2024
https://dl.acm.org/doi/10.1016/j.tcs.2024.114433
Donkers HJansen B(2024)Preprocessing to reduce the search spaceJournal of Computer and System Sciences10.1016/j.jcss.2024.103532144:COnline publication date: 18-Jul-2024
https://dl.acm.org/doi/10.1016/j.jcss.2024.103532
Dekker DJansen B(2024)Kernelization for feedback vertex set via elimination distance to a forestDiscrete Applied Mathematics10.1016/j.dam.2023.12.016346:C(192-214)Online publication date: 31-Mar-2024
https://dl.acm.org/doi/10.1016/j.dam.2023.12.016
Dey SDubey YMolinaro MShah P(2024)A theoretical and computational analysis of full strong-branchingMathematical Programming: Series A and B10.1007/s10107-023-01977-x205:1-2(303-336)Online publication date: 1-May-2024
https://dl.acm.org/doi/10.1007/s10107-023-01977-x
Krysta PMari MZhi N(2024)Ultimate Greedy Approximation of Independent Sets in Subcubic GraphsAlgorithmica10.1007/s00453-024-01268-786:11(3518-3578)Online publication date: 12-Sep-2024
https://dl.acm.org/doi/10.1007/s00453-024-01268-7
Oostveen Jvan Leeuwen E(2024)Parameterized Complexity of Streaming Diameter and Connectivity ProblemsAlgorithmica10.1007/s00453-024-01246-z86:9(2885-2928)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1007/s00453-024-01246-z
Suppakitpaisarn VHao J(2024)Utilizing Graph Sparsification for Pre-processing in Max Cut QUBO SolverMetaheuristics10.1007/978-3-031-62912-9_22(219-233)Online publication date: 4-Jun-2024
https://dl.acm.org/doi/10.1007/978-3-031-62912-9_22
Delle Donne DEscalante MFekete PMoroni L(2024)1-Persistency of the Clique Relaxation of the Stable Set PolytopeCombinatorial Optimization10.1007/978-3-031-60924-4_6(71-84)Online publication date: 22-May-2024
https://dl.acm.org/doi/10.1007/978-3-031-60924-4_6
Mandal SMisra PRai ASaurabh S(2024)Parameterized Approximation Algorithms for Weighted Vertex CoverLATIN 2024: Theoretical Informatics10.1007/978-3-031-55601-2_12(177-192)Online publication date: 18-Mar-2024
https://dl.acm.org/doi/10.1007/978-3-031-55601-2_12
Lu TXiao HFang Q(2023)Approximate Core Allocations for Edge Cover GamesFrontiers of Algorithmics10.1007/978-3-031-39344-0_8(105-115)Online publication date: 14-Aug-2023
https://dl.acm.org/doi/10.1007/978-3-031-39344-0_8
Show More Cited By

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents