Although several tractable classes of SAT are known, none of these turns out to be easy for optimization, probabilistic and counting versions of SAT. These problems can be solved efficiently for formulas with bounded treewidth. However, the resulting time bounds are exponential in the treewidth, which means exponential in the size of the largest clause.In this paper we show that solution methods for formulas with treewidth two can be combined with specialized techniques for dealing with "long" clauses, thus obtaining time bounds independent of the treewidth. This leads to the definition of a new class of tractable instances for SAT and its extensions. This class is related to a particular class of reducible hypergraphs, that extends partial 2-trees and hypertrees.

Hypergraph Reductions and Satisfiability Problems / Pretolani, Daniele. - STAMPA. - 2919:(2004), pp. 383-397. ((Intervento presentato al convegno 6th International Conference on Theory and Applications of Satisfiability Testing tenutosi a Santa Margherita Ligure, ITALY nel MAY 05-08, 2003.

Hypergraph Reductions and Satisfiability Problems

PRETOLANI, Daniele
2004

Abstract

Although several tractable classes of SAT are known, none of these turns out to be easy for optimization, probabilistic and counting versions of SAT. These problems can be solved efficiently for formulas with bounded treewidth. However, the resulting time bounds are exponential in the treewidth, which means exponential in the size of the largest clause.In this paper we show that solution methods for formulas with treewidth two can be combined with specialized techniques for dealing with "long" clauses, thus obtaining time bounds independent of the treewidth. This leads to the definition of a new class of tractable instances for SAT and its extensions. This class is related to a particular class of reducible hypergraphs, that extends partial 2-trees and hypertrees.
THEORY AND APPLICATIONS OF SATISFIABILITY TESTING
3-540-20851-8
SPRINGER-VERLAG BERLIN
GERMANIA
Hypergraph Reductions and Satisfiability Problems / Pretolani, Daniele. - STAMPA. - 2919:(2004), pp. 383-397. ((Intervento presentato al convegno 6th International Conference on Theory and Applications of Satisfiability Testing tenutosi a Santa Margherita Ligure, ITALY nel MAY 05-08, 2003.
Pretolani, Daniele
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

Licenza Creative Commons
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11380/586971
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 2
social impact