Computing diverse pair of solutions for tractable SAT
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916508990439424 |
|---|---|
| author | Gima, Tatsuya Iwamasa, Yuni Kobayashi, Yasuaki Kurita, Kazuhiro Otachi, Yota Saito, Rin |
| author_facet | Gima, Tatsuya Iwamasa, Yuni Kobayashi, Yasuaki Kurita, Kazuhiro Otachi, Yota Saito, Rin |
| contents | In many decision-making processes, one may prefer multiple solutions to a single solution, which allows us to choose an appropriate solution from the set of promising solutions that are found by algorithms. Given this, finding a set of \emph{diverse} solutions plays an indispensable role in enhancing human decision-making. In this paper, we investigate the problem of finding diverse solutions of Satisfiability from the perspective of parameterized complexity with a particular focus on \emph{tractable} Boolean formulas. We present several parameterized tractable and intractable results for finding a diverse pair of satisfying assignments of a Boolean formula. In particular, we design an FPT algorithm for finding an ``almost disjoint'' pair of satisfying assignments of a $2$CNF formula. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_04016 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Computing diverse pair of solutions for tractable SAT Gima, Tatsuya Iwamasa, Yuni Kobayashi, Yasuaki Kurita, Kazuhiro Otachi, Yota Saito, Rin Data Structures and Algorithms In many decision-making processes, one may prefer multiple solutions to a single solution, which allows us to choose an appropriate solution from the set of promising solutions that are found by algorithms. Given this, finding a set of \emph{diverse} solutions plays an indispensable role in enhancing human decision-making. In this paper, we investigate the problem of finding diverse solutions of Satisfiability from the perspective of parameterized complexity with a particular focus on \emph{tractable} Boolean formulas. We present several parameterized tractable and intractable results for finding a diverse pair of satisfying assignments of a Boolean formula. In particular, we design an FPT algorithm for finding an ``almost disjoint'' pair of satisfying assignments of a $2$CNF formula. |
| title | Computing diverse pair of solutions for tractable SAT |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2412.04016 |