| 1. |
- Creignou, Nadia, et al.
(författare)
-
Paradigms for Parameterized Enumeration
- 2017
-
Ingår i: Theory of Computing Systems. - : Springer. - 1432-4350 .- 1433-0490. ; 60:4, s. 737-758
-
Tidskriftsartikel (refereegranskat)abstract
- The aim of the paper is to examine the computational complexity and algorithmics of enumeration, the task to output all solutions of a given problem, from the point of view of parameterized complexity. First, we define formally different notions of efficient enumeration in the context of parameterized complexity: FPT-enumeration and delayFPT. Second, we show how different algorithmic paradigms can be used in order to get parameter-efficient enumeration algorithms in a number of examples. These paradigms use well-known principles from the design of parameterized decision as well as enumeration techniques, like for instance kernelization and self-reducibility. The concept of kernelization, in particular, leads to a characterization of fixed-parameter tractable enumeration problems. Furthermore, we study the parameterized complexity of enumerating all models of Boolean formulas having weight at least k, where k is the parameter, in the famous Schaefer’s framework. We consider propositional formulas that are conjunctions of constraints taken from a fixed finite set Γ. Given such a formula and an integer k, we are interested in enumerating all the models of the formula that have weight at least k. We obtain a dichotomy classification and prove that, according to the properties of the constraint language Γ, either one can enumerate all such models in delayFPT, or no such delayFPT enumeration algorithm exists under some complexity-theoretic assumptions.
|
|
| 2. |
- Jonsson, Peter, et al.
(författare)
-
The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems
- 2021
-
Ingår i: Theoretical Computer Science. - : Elsevier. - 0304-3975 .- 1879-2294. ; 892, s. 1-24
-
Tidskriftsartikel (refereegranskat)abstract
- Obtaining lower bounds for NP-hard problems has for a long time been an active area of research. Algebraic techniques introduced by Jonsson et al. (2017) [4] show that the fine-grained time complexity of the parameterized [Formula presented] problem correlates to the lattice of strong partial clones. With this ordering they isolated a relation R such that [Formula presented] can be solved at least as fast as any other NP-hard [Formula presented] problem. In this paper we extend this method and show that such languages also exist for the surjective SAT problem, the max ones problem, the propositional abduction problem, and the Boolean valued constraint satisfaction problem over finite-valued constraint languages. These languages may be interesting when investigating the borderline between polynomial time, subexponential time and exponential-time algorithms since they in a precise sense can be regarded as NP-hard problems with minimum time complexity. Indeed, with the help of these languages we relate all of the above problems to the exponential time hypothesis (ETH) in several different ways.
|
|
