The parameterized complexity of maximality and minimality problems

DOI10.1016/J.APAL.2007.09.003MaRDI QIDQ2470035zbMATH OpenOpenAlexFDO

Publication date 13 February 2008

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.apal.2007.09.003

Fagin-definability maximality problems minimality problems parameterized complexity

Complexity of computation (including implicit computational complexity) (03D15) Descriptive complexity and finite models (68Q19) Analysis of algorithms and problem complexity (68Q25)

Review text

This is an extensive paper related to parameterized complexity. The authors are two of the main researchers in the area. Indeed, Prof. Jörg Flum has co-authored one of the best books on parameterized complexity [\textit{J. Flum} and \textit{M. Grohe}, Parameterized complexity theory. Berlin: Springer (2006; Zbl 1143.68016)]. The authors deal with the problem of finding set-theoretical maximal or minimal sets of solutions of a given problem, from the point of view of parameterized complexity. If it is known that a problem \(P\) has \(k\) solutions, it is posed the question of whether there is a maximal set of solutions consisting of \(k\) elements or a minimal solution set with \(k\) elements. Let Maximal-\(P\) and Minimal-\(P\) denote these problems. Parameterized complexity appeared in the 90s, from seminal papers of Downey and Fellows. Here, complexity of algorithms is measured not depending just on the size of the inputs but also on a proper parameter. For instance, in an optimization problem if it is intended to find an extreme value within a threshold \(\varepsilon\), then \(\varepsilon^{-1}\) is a parameter determining the complexity of the optimization problem. The book of Flum and Grohe [op. cit.] is a very good introduction to this topic. An important notion is fixed-parameter tractability (fpt), which is a relaxation, regulated by a parameter, of the usual notion of tractability. A problem is fpt-reducible to another one if there is an fpt reduction among them. In parameterized complexity, there is an analogy to NP: A restricted Turing machine computes in time polynomial up to the product of a computable function of the parameter and it is allowed to perform a number of non-deterministic transitions bounded by a computable function of the parameter. \(W[P]\) is the class of problems decidable by those restricted Turing machines. For a given first formula \(\phi\), the Fagin-defined problem \(\text{FD}_{\phi}\) consists in deciding, given a structure, whether it contains a (finite) substructure satisfying \(\phi\). A problem is Fagin-defined by \(\phi\) if it coincides with \(\text{FD}_{\phi}\). The weighted Fagin-defined problem \(\text{WD}_{\phi}\) consists in deciding, given a structure and an integer \(k\), whether it contains a substructure of size \(k\) satisfying \(\phi\). The \(W\)-hierarchy is the union of levels \(W[t]\), each consisting of those problems fpt-reducible to problems \(\text{WD-}\Pi_t\). The above notions are motivated by Fagin's characterization of NP (a problem is in NP if it is \(\Sigma_1^1\)-definable). In the current paper the authors characterize the \(W\)-hierarchy in terms of Fagin-definability as well as in terms of the maximality and minimality versions of Fagin-defined problems. For a problem \(P\), let \(p\)-\(P\) be its version asking for a solution with size a given parameter. Initially, the following remarks are stated: \(p\)-\textsc{VertexCover} is ftp and \(p\)-\textsc{Minimal-VertexCover} is ftp; \(p\)-\textsc{IndependentSet} is \(W[1]\)-complete but \(p\)-\textsc{Maximal-IndependentSet} is \(W[2]\)-complete; and \(p\)-\textsc{DominatingSet} is \(W[2]\)-complete and \(p\)-\textsc{Minimal-DominatingSet} is \(W[2]\)-complete. Thus, maximality problems may increase the complexity in the \(W\)-hierarchy. Thereafter, the general results are stated: for \(t\) odd, \(W[t]\) coincides with the problems ftp-reducible to problems \(\text{WD}_{\phi(Z)}\) with \(Z\) a relation variable and \(\phi\in\Pi_{t+1}\) negative in \(Z\) (it appears only within the scope of single negations); for \(t\) even, \(W[t]\) coincides with the problems ftp-reducible to problems \(\text{WD}_{\phi(Z)}\) with \(\phi\in\Pi_{t+1}\) positive in \(Z\). Also, for \(t\) odd, \(W[t+1]\) coincides with the problems ftp-reducible to problems \(\text{Maximal-WD}_{\phi(Z)}\) with \(\phi\in\Pi_{t+1}\) negative in \(Z\); and for \(t\) even, \(W[t]\) coincides with the problems ftp-reducible to problems \(\text{Minimal-WD}_{\phi(Z)}\) with \(\phi\in\Pi_{t+1}\) positive in \(Z\). The parameterized version of \textsc{Sat} is \textsc{WSat} and it asks whether there is a satisfying model of size a given parameter. In the paper, it is shown that \(p\)-\textsc{Maximal-WSat}\((\Gamma_{1,1})\) is FPT and \(p\)-\textsc{Maximal-WSat}\((\Gamma_{1,2})\) is \(W[2]\)-complete; also that \(p\)-\textsc{Minimal-WSat}\((\Gamma_{1,d})\) is FPT for every \(d\). Here, \(\Gamma_{0,d}\) consists of phrases with at most \(d\) literals, \(\Delta_{0,d}\) consists of clauses with at most \(d\) literals, \(\Gamma_{t+1,d}\) consists of conjunctions of forms in \(\Delta_{t,d}\) and \(\Delta_{t+1,d}\) consists of disjunctions of forms in \(\Gamma_{t,d}\). Extensive relations among Fagin-defined problems \(\text{WD}_{\phi}\) and \(p\)-\textsc{WSat}\((\Gamma)\) are given, hence representative problems in classes of the \(W\)-hierarchy are provided. As consequences of the general results, the following particular results are proved: \(p\)-\textsc{Maximal-WSat}\((\Gamma_{t,d}^-)\) is \(W[t+1]\)-complete; \(p\)-\textsc{Minimal-WSat}\((\Gamma_{t,d})\) is \(W[t]\)-complete, for \(t\geq 2, d\geq 1\). \(p\)-\textsc{Minimal-WSat}\((\Gamma_{t,d}^+)\) is \(W[t]\)-complete, for \(t\geq 2\) even, and \(d\geq 1\); and \(p\)-\textsc{Minimal-WSat}\((\Gamma_{t,d}^+)\) is \(W[t-1]\)-complete, for \(t\geq 3\) odd, and \(d\geq 1\). (The upper sign in each set of forms means that its literals appear just with the given sign in that set.) Finally, counting problems are considered: How many sets realize minimal or maximal solution sets, especially those of the form \(p\)-\(\text{\#WD}_{\phi}\). The authors give a characterization of the corresponding classes \(\#W[t]\) (Theorems 53 and 58), and some illustrative complete problems on these classes (see Proposition~57). Indeed, as the authors claim, they have shown that Fagin definability is an appropriate framework for the analysis of maximality and minimality problems, and that the \(W\)-hierarchy can be characterized in terms of Fagin-defined problems by formulas in fixpoint logic.

Recommendations

Cites work

Cited in

(24)

This page was built for publication: The parameterized complexity of maximality and minimality problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2470035)