Die Struktur parametrischer Komplexitätsklassen

• Applicants: Professor Dr. Jörg Flum; Professor Dr. Martin Grohe
• Subject Area: Theoretical Computer Science
• Term: from 2003 to 2012
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 5416593

• Final Report Year: 2015

Final Report Abstract

Wir haben im Rahmen dieses Projekts eine Reihe von Fragestellungen in der parametrischen Komplexitätstheorie untersucht, die jenseits der traditionell betrachteten worst-case Komplexität von Entscheidungsproblemen liegen. Die technisch substantiellsten Resultate liegen dabei wohl in den Bereichen Approximierbarkeit und Kernelisierung. Erwähnenswert ist auch, dass im Umfeld dieses Projekts fünf Dissertationen entstanden sind.

Publications

• On parameterized approximability: Proceedings of the 2nd International Workshop on Parameterized and Exact Computation. Lecture Notes in Computer Science, Vol. 4169. 2006, pp 109-120.
  Y. Chen, M. Grohe, M. Grüber
  (See online at https://dx.doi.org/10.1007/11847250_10)
• On Parameterized Path and Chordless Path Problems. In: Proceedings of the 22nd IEEE Conference on Computational Complexity, 2007,pp. 250-263.
  Y. Chen, J. Flum
  (See online at https://dx.doi.org/10.1109/CCC.2007.21)
• The parameterized complexity of maximality and minimality problems. Annals of Pure and Applied Logic, Vol. 151. 2008, Issue 1, pp. 22–61.
  Y. Chen, J. Flum
  (See online at https://dx.doi.org/10.1016/j.apal.2007.09.003)
• Understanding the Complexity of Induced Subgraph Isomorphisms: Proceedings of the 35th International Colloquium on Automata, Languages and Programming. Lecture Notes in Computer Science, Vol. 5125. 2008, pp 587-596.
  Y. Chen, M. Thurley, M. Weyer
  (See online at https://dx.doi.org/10.1007/978-3-540-70575-8_48)
• Parameterized Approximability. Dissertation, Humboldt Universität zu Berlin, 2009.
  Magdalena Grüber
  
• Parameterized Randomization. Fakultät für Mathematik und Physik der Albert-Ludwigs-Universität Freiburg im Breisgau, 2009.
  Moritz Müller
  
• Subexponential Time and Fixed-parameter Tractability: Exploiting the Miniaturization Mapping. Journal of Logic and Computation, Vol. 19.2009, Issue 1, pp. 89-122.
  Y. Chen, J. Flum
  (See online at https://dx.doi.org/10.1093/logcom/exn029)
• Algorithmic graph minor theory: approximation, parameterized complexity, and practical aspects. Dissertation, Mathematisch-Naturwissenschaftliche Fakultät II, Humboldt-Universität zu Berlin, 2010.
  Siamak Tazari
  
• W-hierarchies defined by symmetric gates. Theory of Computing Systems, Vol. 46. 2010, Issue 2, pp 311-339.
  M. Fellows, J. Flum, D. Hermelin, M. Müller, F. Rosamond
  (See online at https://dx.doi.org/10.1007/s00224-008-9138-6)
• Lower bounds for kernelizations and other preprocessing procedures. Theory of Computing Systems, Vol. 48. 2011, Issue 4, pp 803-839.
  Y. Chen, J. Flum, M. Müller
  (See online at https://dx.doi.org/10.1007/s00224-010-9270-y)
• Non-Definability Results for Randomised First-Order Logic. Proceedings of the 25th International Workshop on Computer Science Logic, 2011, pp. 218–232.
  K. Eickmeyer
  (See online at https://dx.doi.org/10.4230/LIPIcs.CSL.2011.218)
• Randomisation and derandomisation in descriptive complexity theory. Logical Methods in Computer Science, Vol. 7. 2011, Issue 3, Paper 14.
  K. Eickmeyer, M. Grohe
  (See online at https://dx.doi.org/10.2168/LMCS-7(3:14)2011)
• Randomness in complexity theory and logics. Dissertation, Mathematisch-Naturwissenschaftliche Fakultät II, Humboldt-Universität zu Berlin, 2011.
  Kord Eickmeyer
  
• Kernelization of packing problems. Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, 2012, pp. 68-81.
  H. Dell, D. Marx
  
• Exponential Time Complexity of the Permanent and the Tutte Polynomial. ACM Transactions on Algorithms, Vol. 10. 2014, Issue 4, Article No. 21.
  H. Dell, T. Husfeldt, D. Marx, N. Taslaman, M. Wahlen
  (See online at https://doi.org/10.1145/2635812)
• Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses. Journal of the ACM, Vol. 61. 2014, Issue 4, Article No. 23.
  H. Dell, D. van Melkebeek
  (See online at https://doi.org/10.1145/2629620)