Parameterized and Exact Computation

1. Front Matter

   PDF

2. The Path Taken for k-Path

   • Andreas Björklund

   Pages 1-1

3. Randomized Techniques for Parameterized Algorithms

   • Dániel Marx

   Pages 2-2

4. Finding a Maximum Induced Degenerate Subgraph Faster Than 2ⁿ

   • Marcin Pilipczuk, Michał Pilipczuk

   Pages 3-12

5. The Exponential Time Hypothesis and the Parameterized Clique Problem

   • Yijia Chen, Kord Eickmeyer, Jörg Flum

   Pages 13-24

6. New Results on Polynomial Inapproximability and Fixed Parameter Approximability of edge dominating set

   • Bruno Escoffier, Jérôme Monnot, Vangelis Th. Paschos, Mingyu Xiao

   Pages 25-36

7. A New Algorithm for Parameterized MAX-SAT

   • Ivan Bliznets, Alexander Golovnev

   Pages 37-48

8. Restricted and Swap Common Superstring: A Parameterized View

   • Paola Bonizzoni, Riccardo Dondi, Giancarlo Mauri, Italo Zoppis

   Pages 49-60

9. Nonblocker in H-Minor Free Graphs: Kernelization Meets Discharging

   • Łukasz Kowalik

   Pages 61-72

10. Some Definitorial Suggestions for Parameterized Proof Complexity

    • Jörg Flum, Moritz Müller

    Pages 73-84

11. An Exact Algorithm for Subset Feedback Vertex Set on Chordal Graphs

    • Petr A. Golovach, Pinar Heggernes, Dieter Kratsch, Reza Saei

    Pages 85-96

12. Preprocessing Subgraph and Minor Problems: When Does a Small Vertex Cover Help?

    • Fedor V. Fomin, Bart M. P. Jansen, Michał Pilipczuk

    Pages 97-108

13. A Polynomial-Time Algorithm for Planar Multicuts with Few Source-Sink Pairs

    • Cédric Bentz

    Pages 109-119

14. Instance Compression for the Polynomial Hierarchy and beyond

    • Chiranjit Chakraborty, Rahul Santhanam

    Pages 120-134

15. Polynomial Time and Parameterized Approximation Algorithms for Boxicity

    • Abhijin Adiga, Jasine Babu, L. Sunil Chandran

    Pages 135-146

16. Homomorphic Hashing for Sparse Coefficient Extraction

    • Petteri Kaski, Mikko Koivisto, Jesper Nederlof

    Pages 147-158

17. Fast Monotone Summation over Disjoint Sets

    • Petteri Kaski, Mikko Koivisto, Janne H. Korhonen

    Pages 159-170

18. Weighted Counting of k-Matchings Is #W[1]-Hard

    • Markus Bläser, Radu Curticapean

    Pages 171-181

19. Computing Directed Pathwidth in O(1.89ⁿ) Time

    • Kenta Kitsunai, Yasuaki Kobayashi, Keita Komuro, Hisao Tamaki, Toshihiro Tano

    Pages 182-193

20. MSOL Restricted Contractibility to Planar Graphs

    • James Abello, Pavel Klavík, Jan Kratochvíl, Tomáš Vyskočil

    Pages 194-205

This book constitutes the refereed proceedings of the 7th International Symposium on Parameterized and Exact Computation, IPEC 2012, in Ljubljana, Slovenia, in September 2012. The 21 revised full papers presented together with 2 keynote talks were carefully reviewed and selected from 37 submissions. The topics addressed cover research in all aspects of parameterized/exact algorithms and complexity including but are not limited to new techniques for the design and analysis of parameterized and exact algorithms; fixed-parameter tractability results; parameterized complexity theory; relationship between parameterized complexity and traditional complexity classifications; applications of parameterized and exact computation; and implementation issues of parameterized and exact algorithms.

• approximation algorithms
• graphs
• parametrized problems
• proof complexity
• vertex set problems
• algorithm analysis and problem complexity
• data structures

• Department of Mathematics, National and Kapodistrian University of Athens, Athens, Greece

  Dimitrios M. Thilikos

• Department of Mathematics and Computer Science, Eindhoven University of Technology, Eindhoven, The Netherlands

  Gerhard J. Woeginger

Policies and ethics