On reducing Maximum Independent Set to Minimum Satisfiability

Alexey Ignatiev, Antonio Morgado, Joao Marques-Silva

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

14 Citations (Scopus)

Abstract

Maximum Independent Set (MIS) is a well-known NP-hard graph problem, tightly related with other well known NP-hard graph problems, namely Minimum Vertex Cover (MVC) and Maximum Clique (MaxClq). This paper introduces a novel reduction of MIS into Minimum Satisfiability (MinSAT), thus, providing an alternative approach for solving MIS. The reduction naturally maps the vertices of a graph into clauses, without requiring the inclusion of hard clauses. Moreover, it is shown that the proposed reduction uses fewer variables and clauses than the existing alternative of mapping MIS into Maximum Satisfiability (MaxSAT). The paper develops a number of optimizations to the basic reduction, which significantly reduce the total number of variables used. The experimental evaluation considered the reductions described in the paper as well as existing state-of-the-art approaches. The results show that the proposed approaches based on MinSAT are competitive with existing approaches.

Original languageEnglish
Title of host publicationTheory and Applications of Satisfiability Testing – SAT 2014
Subtitle of host publication17th International Conference Held as Part of theVienna Summer of Logic, VSL 2014 Vienna, Austria, July 14-17, 2014 Proceedings
EditorsCarsten Sinz, Uwe Egly
Place of PublicationCham Switzerland
PublisherSpringer
Pages103-120
Number of pages18
ISBN (Electronic)9783319092843
ISBN (Print)9783319092836
DOIs
Publication statusPublished - 2014
Externally publishedYes
EventInternational Conference on Theory and Applications of Satisfiability Testing 2014
- Vienna, Austria
Duration: 14 Jul 201417 Jul 2014
Conference number: 17th
https://baldur.iti.kit.edu/sat2014/

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume8561
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceInternational Conference on Theory and Applications of Satisfiability Testing 2014
Abbreviated titleSAT 2014
Country/TerritoryAustria
CityVienna
Period14/07/1417/07/14
Internet address

Keywords

  • Maximum Clique
  • Basic Reduction
  • Maximum Clique Problem
  • Minimum Vertex Cover
  • Compatibility Class

Cite this