Reductions for the Stable Set Problem

Authors

  • E. C. Sewell Southern Illinois University Edwardsville
  • S. H. Jacobson University of Illinois
  • Hemanshu Kaul Illinois Institute of Technology

Keywords:

Maximum stable set, reductions, probing, hypergraphs

Abstract

One approach to finding a maximum stable set (MSS) in a graph is to try to reduce the size of the problem by transforming the problem into an equivalent problem on a smaller graph. This paper introduces several new reductions for the MSS problem, extends several well-known reductions to the maximum weight stable set (MWSS) problem, demonstrates how reductions for the generalized stable set problem can be used in conjunction with probing to produce powerful new reductions for both the MSS and MWSS problems, and shows how hypergraphs can be used to expand the capabilities of clique projections. The effectiveness of these new reduction techniques are illustrated on the DIMACS benchmark graphs, planar graphs, and a set of challenging MSS problems arising from Steiner Triple Systems.

Downloads

Additional Files

Published

2011-05-30

How to Cite

Sewell, E. C., Jacobson, S. H., & Kaul, H. (2011). Reductions for the Stable Set Problem. Algorithmic Operations Research, 6(1), Pages 40 – 55. Retrieved from https://journals.lib.unb.ca/index.php/AOR/article/view/12604

Issue

Vol. 6 No. 1 (2011)

Section

Articles

License

The copyright of the submitted article is hereby transferred to “Preeminent Academic Facets Inc. (the “publisher”) to the extent possible by the laws in the respective countries of the author(s). The author(s) retain all other rights including the following: 1. Any patents and trademark rights. 2. Right to post a pre-print version of the paper on the author’s personal website which is not used for commercial purposes. The author(s) warrant that the work is original, it has not been published elsewhere, it is not currently under consideration for publication in any form, and it does not infringe any copyright laws. The signing author or agent further warrants that all authors, if applicable, have been informed of the terms of this agreement and obtained the approval and authority to sign the agreement.