Страница публикации

On Reducing Maximum Independent Set to Minimum Satisfiability

Тип публикации: Статья в журнале

Тип материала: Текст

Авторы: Ignatiev A., Morgado A., Marques-Silva J.

Журнал: Lecture Notes in Computer Science

Язык публикации: english

Том: 8561

Номера страниц: 103-120

Количество страниц: 18

Год публикации: 2014

Отчетный год: 2014

DOI: 10.1007/978-3-319-09284-3-9

Аннотация: 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.

Индексируется WOS: Q4

Индексируется Scopus: Нет

Индексируется УБС: Нет

Индексируется РИНЦ: Да

Индексируется ВАК: Нет

Индексируется CORE: Нет