Abstract
Motivated by recent results showing that there are natural parameterized problems that are fixed-parameter tractable, but can only be solved by fixed-parameter tractable algorithms the running time of which depends non-elementarily on the parameter, we propose a notion of bounded fixed-parameter tractability, where the dependence of the running time on the parameter is restricted to be singly exponential. We develop a basic theory that is centred around the class EPT of tractable problems and an EW-hierarchy of classes of intractable problems, both in the bounded sense. By and large, this theory is similar to the established unbounded parameterized complexity theory, but there are some remarkable differences. Most notably, certain natural model-checking problems that are known to be fixed-parameter tractable in the unbounded sense have a very high complexity in the bounded theory. The problem of computing the VC-dimension of a family of sets, which is known to be complete for the class W[1] in the unbounded theory, is complete for the class EW[3] in the bounded theory. It turns out that our bounded parameterized complexity theory is closely related to the classical complexity theory of problems that can be solved by a nondeterministic polynomial time algorithm that only uses log2 n nondeterministic bits, and in particular to the classes LOGSNP and LOGNP introduced by Papadimitriou and Yannakakis [15].
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Abrahamson, K.A., Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness IV: On completeness for W[P] and PSPACE analogs. Annals of pure and applied logic 73, 235–276 (1995)
Courcelle, B.: Graph rewriting: An algebraic and logic approach. In: van Leeuwen, J. (ed.) Handbook of Theoretical Computer Science, vol. B, pp. 194–242. Elsevier Science Publishers, Amsterdam (1990)
Downey, R.: Parameterized complexity for the skeptic. In: Proceedings of the 18th IEEE Conference on Computational Complexity (2003)
Downey, R.G., Evans, P.A., Fellows, M.R.: Parameterized learning complexity. In: Proceedings of the 6th Annual ACM Conference on Computational Learning Theory, pp. 51–57 (1993)
Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness III: Some structural aspects of the W-hierarchy. In: Ambos-Spies, K., Homer, S., Schöning, U. (eds.) Complexity Theory, pp. 166–191. Cambridge University Press, Cambridge (1993)
Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1999)
Downey, R.G., Fellows, M.R., Regan, K.: Descriptive complexity and the W-hierarchy. In: Beame, P., Buss, S. (eds.) Proof Complexity and Feasible Arithmetic. AMS-DIMACS Volume Series, vol. 39, pp. 119–134. AMS, Providence (1998)
Eiter, T., Gottlob, G., Makino, K.: New results on monotone dualization and generating hypergraph transversals. In: Proceedings of the 34th ACMSymposium on Theory of Computing, pp. 14–22 (2002)
Flum, J., Grohe, M.: Fixed-parameter tractability, definability, and model checking. SIAM Journal on Computing 31(1), 113–145 (2001)
Flum, J., Grohe, M.: Model-checking problems as a basis for parameterized intractability. To appear in Proceedings of the 19th IEEE Symposium on Logic in Computer Science (2004); Full version available as Technical Report 23/2003, Fakultät für Mathematik und Physik, Albert-Ludwigs-Universität Freiburg (2003)
Flum, J., Grohe, M., Weyer, M.: Bounded fixed-parameter tractability and log2n nondeterministic bits. Technical Report 04/2004, Fakultät für Mathematik und Physik, Albert- Ludwigs-Universität Freiburg (2004)
Frick, M., Grohe, M.: The complexity of first-order and monadic second-order logic revisited. In: Proceedings of the 17th IEEE Symposium on Logic in Computer Science, pp. 215–224 (2002)
Grohe, M.: Parameterized complexity for the database theorist. SIGMOD Record 31(4), 86–96 (2002)
Kintala, C., Fischer, P.: Refining nondeterminism in relativised polynomial time bounded computations. SIAM Journal on Computing 9, 46–53 (1980)
Papadimitriou, C.H., Yannakakis, M.: On limited nondeterminism and the complexity of V-C dimension. Journal of Computer and System Sciences 53, 161–170 (1996)
Schaefer, M.: Deciding the Vapnik-Cěrvonenkis dimension is \(\Sigma^P_3\)-complete. Journal of Computer and System Sciences 58, 177–182 (1999)
Weyer, M.: PhD thesis (in preparation)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Flum, J., Grohe, M., Weyer, M. (2004). Bounded Fixed-Parameter Tractability and log2 n Nondeterministic Bits. In: Díaz, J., Karhumäki, J., Lepistö, A., Sannella, D. (eds) Automata, Languages and Programming. ICALP 2004. Lecture Notes in Computer Science, vol 3142. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-27836-8_48
Download citation
DOI: https://doi.org/10.1007/978-3-540-27836-8_48
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-22849-3
Online ISBN: 978-3-540-27836-8
eBook Packages: Springer Book Archive