The Boolean conjunctive normal form (CNF) satisfiability problem, called SAT for short, gets as input a CNF formula and has to decide whether this formula admits a satisfying truth assignment. As is well known, the remarkable result by S. Cook in 1971 established SAT as the first and genuine complete problem for the complexity class NP. In this thesis we consider SAT for a subclass of CNF, the so called Mixed Horn formula class (MHF). A formula F in MHF consists of a 2-CNF part P and a Horn part H. We propose that MHF has a central relevance in CNF because many prominent NP-complete problems, e.g. Feedback Vertex Set, Vertex Cover, Dominating Set and Hitting Set, can easily be encoded as MHF. Furthermore, we show that SAT remains NP-complet...
In this paper we propose a structural parameter of CNF formulas and use it to identify instances of ...
Abstract—The field of exact exponential time algorithms for NP-hard problems has thrived over the la...
Proposing a fibre view on propositional clause sets, we investigate satisfiability testing for sever...
AbstractIn this paper the class of mixed Horn formulas is introduced that contain a Horn part and a ...
XSAT and NAE-SAT are important variants of the propositional satisfiability problem (SAT). Both are ...
In this paper, we study {em linear} CNF formulas generalizing linear hypergraphs under combinatorial...
AbstractIn this paper, we study linear CNF formulas generalizing linear hypergraphs under combinator...
AbstractThe NP-hard problem of finding the largest renamable Horn sub-CNF of a given CNF is consider...
AbstractIt is shown that the tractable class of CNF formulas solvable by linear autarkies properly c...
The field of exact exponential time algorithms for non-deterministic polynomial-time hard problems h...
We study the propositional satisfiability problem (SAT) on classes of CNF formulas (formulas in Conj...
The field of exact exponential time algorithms for non-deterministic polynomial-time hard problems h...
We introduce the problem of finding a satisfying assignment to a CNF formula that must further belon...
We show that the Satisfiability (SAT) problem for CNF formulas with ββ-acyclic hypergraphs can be so...
This paper initiates the study of SAT instances of bounded diameter. The diameter of an ordered CNF ...
In this paper we propose a structural parameter of CNF formulas and use it to identify instances of ...
Abstract—The field of exact exponential time algorithms for NP-hard problems has thrived over the la...
Proposing a fibre view on propositional clause sets, we investigate satisfiability testing for sever...
AbstractIn this paper the class of mixed Horn formulas is introduced that contain a Horn part and a ...
XSAT and NAE-SAT are important variants of the propositional satisfiability problem (SAT). Both are ...
In this paper, we study {em linear} CNF formulas generalizing linear hypergraphs under combinatorial...
AbstractIn this paper, we study linear CNF formulas generalizing linear hypergraphs under combinator...
AbstractThe NP-hard problem of finding the largest renamable Horn sub-CNF of a given CNF is consider...
AbstractIt is shown that the tractable class of CNF formulas solvable by linear autarkies properly c...
The field of exact exponential time algorithms for non-deterministic polynomial-time hard problems h...
We study the propositional satisfiability problem (SAT) on classes of CNF formulas (formulas in Conj...
The field of exact exponential time algorithms for non-deterministic polynomial-time hard problems h...
We introduce the problem of finding a satisfying assignment to a CNF formula that must further belon...
We show that the Satisfiability (SAT) problem for CNF formulas with ββ-acyclic hypergraphs can be so...
This paper initiates the study of SAT instances of bounded diameter. The diameter of an ordered CNF ...
In this paper we propose a structural parameter of CNF formulas and use it to identify instances of ...
Abstract—The field of exact exponential time algorithms for NP-hard problems has thrived over the la...
Proposing a fibre view on propositional clause sets, we investigate satisfiability testing for sever...