A SAT-based Method for Solving the Maximum Independent Set Problem

DOI

Bibliographic Information

Other Title
  • 最大独立集合問題のSAT技術を用いた解法に関する研究

Abstract

<p>An independent set of a given undirected graph is a subset of the vertices that does not include adjacent vertices. The maximum independent set problem is the problem of finding the independent set with the largest number of vertices. It is used to solve scheduling problems, design DNA sequences, etc. In this paper, we propose a method for solving the maximum independent set problem using a SAT solver. Specifically, we propose two constraint models: a basic constraint model and an improved constraint model using a clique cover. We also propose an algorithm for solving the maximum independent set problem using incremental SAT method, which speeds up the process by reusing learnt clauses obtained in the search process. As an evaluation of the proposed method, we compared it with existing methods for the maximum independent set problem and confirmed the effectiveness of the proposed method.</p>

Journal

Keywords

Details 詳細情報について

Report a problem

Back to top