Parameterized and Exact Computation

1. Front Matter

   PDF

2. Exact Complexity and Satisfiability

   • Russell Impagliazzo, Ramamohan Paturi

   Pages 1-3

3. The Parameterized Complexity of Fixpoint Free Elements and Bases in Permutation Groups

   • Vikraman Arvind

   Pages 4-15

4. Parameterized Complexity of Two Edge Contraction Problems with Degree Constraints

   • Rémy Belmonte, Petr A. Golovach, Pim van ’t Hof, Daniël Paulusma

   Pages 16-27

5. Declarative Dynamic Programming as an Alternative Realization of Courcelle’s Theorem

   • Bernhard Bliem, Reinhard Pichler, Stefan Woltran

   Pages 28-40

6. The Fine Details of Fast Dynamic Programming over Tree Decompositions

   • Hans L. Bodlaender, Paul Bonsma, Daniel Lokshtanov

   Pages 41-53

7. On Subexponential and FPT-Time Inapproximability

   • Edouard Bonnet, Bruno Escoffier, Eun Jung Kim, Vangelis Th. Paschos

   Pages 54-65

8. Multi-parameter Complexity Analysis for Constrained Size Graph Problems: Using Greediness for Parameterization

   • Édouard Bonnet, Bruno Escoffier, Vangelis Th. Paschos, Émeric Tourniaire

   Pages 66-77

9. Chain Minors Are FPT

   • Jarosław Błasiok, M. Kamiński

   Pages 78-83

10. Incompressibility of H-Free Edge Modification

    • Leizhen Cai, Yufei Cai

    Pages 84-96

11. Contracting Few Edges to Remove Forbidden Induced Subgraphs

    • Leizhen Cai, Chengwei Guo

    Pages 97-109

12. Fixed-Parameter and Approximation Algorithms: A New Look

    • Rajesh Chitnis, MohammadTaghi Hajiaghayi, Guy Kortsarz

    Pages 110-122

13. Subgraphs Satisfying MSO Properties on z-Topologically Orderable Digraphs

    • Mateus de Oliveira Oliveira

    Pages 123-136

14. Computing Tree-Depth Faster Than 2ⁿ

    • Fedor V. Fomin, Archontia C. Giannopoulou, Michał Pilipczuk

    Pages 137-149

15. Faster Exact Algorithms for Some Terminal Set Problems

    • Rajesh Chitnis, Fedor V. Fomin, Daniel Lokshtanov, Pranabendu Misra, M. S. Ramanujan, Saket Saurabh

    Pages 150-162

16. Parameterized Algorithms for Modular-Width

    • Jakub Gajarský, Michael Lampis, Sebastian Ordyniak

    Pages 163-176

17. A Faster FPT Algorithm for Bipartite Contraction

    • Sylvain Guillemot, Dániel Marx

    Pages 177-188

18. On the Ordered List Subgraph Embedding Problems

    • Olawale Hassan, Iyad Kanj, Daniel Lokshtanov, Ljubomir Perković

    Pages 189-201

19. A Completeness Theory for Polynomial (Turing) Kernelization

    • Danny Hermelin, Stefan Kratsch, Karolina Sołtys, Magnus Wahlström, Xi Wu

    Pages 202-215

20. On Sparsification for Computing Treewidth

    • Bart M. P. Jansen

    Pages 216-229

This book constitutes the thoroughly refereed post-conference proceedings of the 8th International Symposium on Parameterized and Exact Computation, IPEC 2013, in Sophia Antipolis, France, in September 2013.
The 29 revised full papers presented were carefully reviewed and selected from 58 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 meta-theorems
• dynamic programming
• exact algorithms
• parametrized complexity
• representative sets
• algorithm analysis and problem complexity
• data structures

• Royal Holloway, University of London, Egham, UK

  Gregory Gutin

• Institute of Information Systems, Vienna University of Technology, Vienna, Austria

  Stefan Szeider

Policies and ethics