home	education	contact	library	calendar	search
	about us	research	people	archive	services	jobs

publications by S. Kratsch

• Metis is a dutch, academic research information database
• see also: Metis for Departement Informatica
• please send notifications, questions, remarks etc to metis@cs.uu.nl
• see also : research -> Metis overviews

S. Kratsch

• contact information
• former member of group algorithmic systems

some publications

Bredereck, R., Chen, J., Hartung, S., Niedermeier, R., Suchy, O. & Kratsch, S. (2012). A Multivariate Complexity Analysis of Lobbying in Multiple Referenda. In Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence. AIII Press.

Kratsch, S., Cygan, M., Pilipczuk, M., Wahlström, M. & Pilipczuk, Michal (2012). Clique Cover and Graph Separation: New Incompressibility Results. In A. Czumaj, K. Mehlhorn, A.M. Pitts & R. Wattenhofer (Eds.), Proceedings 39th International Colloquium on Automata, Languages, and Programming (Part I) (pp. 254-265). Springer.

Kratsch, S. (2012). Co-nondeterminism in compositions: a kernelization lower bound for a Ramsey-type problem. In Yuval Rabani (Ed.), Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012 (pp. 114-122). SIAM.

Kratsch, S. & Wahlström, M. (2012). Compression via matroids: a randomized polynomial kernel for odd cycle transversal. In Yuval Rabani (Ed.), Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012 (pp. 94-103). SIAM.

Kratsch, S., Pilipczuk, M., Pilipczuk, Michal & Wahlström, M. (2012). Fixed-Parameter Tractability of Multicut in Directed Acyclic Graphs. In Artur Czumaj, Kurt Mehlhorn, Andrew.M. Pitts & Roger Wattenhofer (Eds.), Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part I (pp. 581-593). Springer.

Kratsch, S. & Schweitzer, P. (2012). Graph Isomorphism for Graph Classes Characterized by Two Forbidden Induced Subgraphs. In Proceedings 38th International Workshop on Graph Theoretic Concepts in Computer Science Vol. 7551. Lecture Notes in Computer Science (pp. 34-45). Springer.

Bodlaender, H.L., Jansen, B.M.P. & Kratsch, S. (2012). Kernel Bounds for Path and Cycle Problems. In Dániel Marx & Peter Rossmanith (Eds.), Parameterized and Exact Computation - 6th International Symposium, IPEC 2011, Saarbrücken, Germany, September 6-8, 2011. Revised Selected Papers (pp. 145-158). Springer.

Bodlaender, H.L., Jansen, B.M.P. & Kratsch, S. (2012). Kernel Bounds for Structural Parameterizations of Pathwidth. In F..V. Fomin & P. Kaski (Eds.), Algorithm Theory - SWAT 2012 - 13th Scandinavian Symposium and Workshops, Helsinki, Finland, July 4-6, 2012 Vol. 7357. Lecture Notes in Computer Science (pp. 352-363). Springer.

Kratsch, S., Pilipczuk, M., Rai, A. & Raman, V. (2012). Kernel Lower Bounds Using Co-nondeterminism: Finding Induced Hereditary Subgraphs. In Fedor.V. Fomin & Petteri Kaski (Eds.), Algorithm Theory - SWAT 2012 - 13th Scandinavian Symposium and Workshops, Helsinki, Finland, July 4-6, 2012. Proceedings (pp. 364-375). Springer.

Jansen, B.M.P. & Kratsch, S. (2012). On Polynomial Kernels for Structural Parameterizations of Odd Cycle Transversal. In Dániel Marx & Peter Rossmanith (Eds.), Parameterized and Exact Computation - 6th International Symposium, IPEC 2011, Saarbrücken, Germany, September 6-8, 2011. Revised Selected Papers (pp. 132-144). Springer.

Kratsch, S. (2012). Polynomial Kernelizations for MIN F+Pi1 and MAX NP. Algorithmica, 63(1-2), 532-550.

Kratsch, S. (2012). Polynomial Kernelizations for MIN F+Π1 and MAX NP. Algorithmica, 63(1-2), 532-550.

Kratsch, S. & Wahlström, M. (2012). Representative Sets and Irrelevant Vertices: New Tools for Kernelization. In Proceedings, 53rd Annual IEEE Symposium on Foundations of Computer Science (pp. 450-459). IEEE Computer Science.

Guo, J., Kanj, I.A. & Kratsch, S. (2012). Safe Approximation and Its Relation to Kernelization. In Dániel Marx & Peter Rossmanith (Eds.), Parameterized and Exact Computation - 6th International Symposium, IPEC 2011, Saarbrücken, Germany, September 6-8, 2011. Revised Selected Papers (pp. 169-180). Springer.

Kratsch, S. (2011). Co-nondeterminism in compositions: A kernelization lower bound for a Ramsey-type problem. CoRR, abs/1107.3.

Kratsch, S. & Wahlström, M. (2011). Compression via Matroids: A Randomized Polynomial Kernel for Odd Cycle Transversal. CoRR, abs/1107.3.

Bodlaender, H.L., Jansen, B.M.P. & Kratsch, S. (2011). Cross-Composition: A New Technique for Kernelization Lower Bounds. In C. Dürr & T. Schwentick (Eds.), Proceedings 28th International Symposium on Theoretical Aspects of Computer Science, STACS 2011 (pp. 165-176). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik.

Jansen, B.M.P. & Kratsch, S. (2011). Data Reduction for Graph Coloring Problems. In O. Owe, M. Steffen & J..A. Telle (Eds.), Proceedings 18th International Symposium on Fundamentals of Computation Theory, FCT 2011 Vol. 6914. Lecture Notes in Computer Science (pp. 90-101). Springer.

Bodlaender, H.L., Jansen, B.M.P. & Kratsch, S. (2011). Kernel Bounds for Path and Cycle Problems. In D. Marx & P. Rossmanith (Eds.), Parameterized and Exact Computation - 6th International Symposium, IPEC 2011 Vol. 7112. Lecture Notes in Computer Science (pp. 145-158). Springer.

Bodlaender, H.L., Jansen, B.P.M. & Kratsch, S. (2011). Kernel Bounds for Path and Cycle Problems. CoRR, abs/1106.4.

Jansen, B.M.P. & Kratsch, S. (2012). On Polynomial Kernels for Structural Parameterizations of Odd Cycle Transversal. In D. Marx & P. Rossmanith (Eds.), Parameterized and Exact Computation - 6th International Symposium, IPEC 2011 Vol. 7112. Lecture Notes in Computer Science (pp. 132-144). Springer.

Jansen, B.P.M. & Kratsch, S. (2011). On Polynomial Kernels for Structural Parameterizations of Odd Cycle Transversal. CoRR, abs/1107.3.

Bodlaender, H.L., Jansen, B.M.P. & Kratsch, S. (2011). Parameterized Complexity of Vertex Deletion into Perfect Graph Classes. In O. Owe, M. Steffen & J..A. Telle (Eds.), Proceedings 18th International Symposium on Fundamentals of Computation Theory, FCT 2011 Vol. 6914. Lecture Notes in Computer Science (pp. 240-251). Springer.

Hermelin, D., Huang, C., Kratsch, S. & Wahlstrom, M. (2011). Parameterized Two-Player Nash Equilibrium. In P. Kolman & J. Kratochvil (Eds.), WG (pp. 215-226).

Bodlaender, H.L., Jansen, B.M.P. & Kratsch, S. (2011). Preprocessing for Treewidth: A combinatorial analysis through kernelization. In L. Aceto, M. Henzinger & J. Sgall (Eds.), Proceedings of the 38th International Colloquium on Automata, Languages, and Programming ICALP 2011 Vol. 6755. Lecture Notes in Computer Science (pp. 437-448). Springer.