The parameterized complexity of relational database queries and an improved characterization of \(W[1]\). (English) Zbl 0918.68018
Bridges, D. S. (ed.) et al., Combinatorics, complexity, and logic. Proceedings of the 1st international conference on discrete mathematics and theoretical computer science, DMTCS ’96, Auckland, New Zealand, December 9–13, 1996. Berlin: Springer. 194-213 (1997).
Summary: It is well known that for a fixed relational database query \(\phi\) in \(m\) free variables, it can be determined in time polynomial in the size \(n\) of the database whether there exists an \(m\)-tuple \(x\) that belongs to the relation defined by the query. For the best known algorithms, however, the exponent of the polynomial is proportional to the size of the query. We study the data complexity of this problem parameterized by the size \(k= |\phi|\) of the query, and answer a question recently raised by M. Yannakakis [Perspectives on database theory. Proceedings FOCS 95, 224-246. Computer Science Press (1988)]. Our main results show: (1) the general problem is complete for the parametric complexity class \(AW[*]\), and (2) when restricted to monotone queries, the problem is complete for the fundamental parametric complexity class \(W[1]\). The practical significance of these results is that unless the parameterized complexity hierarchy collapses, there are unlikely to be algorithms that solve this problem (even under the restriction to monotone queries) in time \(f(k)n^c\), where \(f\) is an arbitrary function of \(k\) and \(c\) is a constant independent of \(k\).
An important consequence of the proof of (2) is a significantly improved characterization of the parameterized complexity class \(W[1]\). Previous results by Downey and Fellows characterize \(W[1]\) in terms of the \(k\)-WEIGHTED CIRCUIT SATISFIABILITY problem, for families of circuits that satisfy: (1) the depth of the circuits is bounded by a constant \(c\), (2) on any input-output path there is at most one gate having unbounded fan-in (termed a large gate), with all other gates having fan-in bounded by \(c\) (that is, small gates). We show that the definition can be broadened by allowing circuits of depth bounded by an arbitrary function \(f(k)\). If we denote this parameterized complexity class \(W^*[1]\), then our corollary is: \(W^*[1]= W[1]\). As a consequence, the \(k\)-WEIGHTED SATISFIABILITY problem for Boolean expressions that are products of \(k\)-sums is complete for \(W[1]\). Part of our argument establishes a general normalization lemma for \(W^*[t]\) for all \(t\).
For the entire collection see [Zbl 0892.00029].
An important consequence of the proof of (2) is a significantly improved characterization of the parameterized complexity class \(W[1]\). Previous results by Downey and Fellows characterize \(W[1]\) in terms of the \(k\)-WEIGHTED CIRCUIT SATISFIABILITY problem, for families of circuits that satisfy: (1) the depth of the circuits is bounded by a constant \(c\), (2) on any input-output path there is at most one gate having unbounded fan-in (termed a large gate), with all other gates having fan-in bounded by \(c\) (that is, small gates). We show that the definition can be broadened by allowing circuits of depth bounded by an arbitrary function \(f(k)\). If we denote this parameterized complexity class \(W^*[1]\), then our corollary is: \(W^*[1]= W[1]\). As a consequence, the \(k\)-WEIGHTED SATISFIABILITY problem for Boolean expressions that are products of \(k\)-sums is complete for \(W[1]\). Part of our argument establishes a general normalization lemma for \(W^*[t]\) for all \(t\).
For the entire collection see [Zbl 0892.00029].
MSC:
| 68P15 | Database theory |
| 68Q15 | Complexity classes (hierarchies, relations among complexity classes, etc.) |
| 68Q25 | Analysis of algorithms and problem complexity |
