Parameterized And Exact Computation: 8th International Symposium, Ipec 2013, Sophia Antipolis, France, September 4-6, 2013, Revised Selected Papers (lecture Notes In Computer Science)

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. Front Matter....Pages - Exact Complexity and Satisfiability....Pages 1-3 The Parameterized Complexity of Fixpoint Free Elements and Bases in Permutation Groups....Pages 4-15 Parameterized Complexity of Two Edge Contraction Problems with Degree Constraints....Pages 16-27 Declarative Dynamic Programming as an Alternative Realization of Courcelle’s Theorem....Pages 28-40 The Fine Details of Fast Dynamic Programming over Tree Decompositions....Pages 41-53 On Subexponential and FPT-Time Inapproximability....Pages 54-65 Multi-parameter Complexity Analysis for Constrained Size Graph Problems: Using Greediness for Parameterization....Pages 66-77 Chain Minors Are FPT....Pages 78-83 Incompressibility of H -Free Edge Modification....Pages 84-96 Contracting Few Edges to Remove Forbidden Induced Subgraphs....Pages 97-109 Fixed-Parameter and Approximation Algorithms: A New Look....Pages 110-122 Subgraphs Satisfying MSO Properties on z -Topologically Orderable Digraphs....Pages 123-136 Computing Tree-Depth Faster Than 2 n ....Pages 137-149 Faster Exact Algorithms for Some Terminal Set Problems....Pages 150-162 Parameterized Algorithms for Modular-Width....Pages 163-176 A Faster FPT Algorithm for Bipartite Contraction....Pages 177-188 On the Ordered List Subgraph Embedding Problems....Pages 189-201 A Completeness Theory for Polynomial (Turing) Kernelization....Pages 202-215 On Sparsification for Computing Treewidth....Pages 216-229 The Jump Number Problem: Exact and Parameterized....Pages 230-242 On the Hardness of Eliminating Small Induced Subgraphs by Contracting Edges....Pages 243-254 Hardness of r - dominating set on Graphs of Diameter ( r + 1)....Pages 255-267 Amalgam Width of Matroids....Pages 268-280 On the Parameterized Complexity of Reconfiguration Problems....Pages 281-294 FPT Algorithms for Consecutive Ones Submatrix Problems....Pages 295-307 Upper Bounds on Boolean-Width with Applications to Exact Algorithms....Pages 308-320 Speeding Up Dynamic Programming with Representative Sets....Pages 321-334 Completeness Results for Parameterized Space Classes....Pages 335-347 Treewidth and Pure Nash Equilibria....Pages 348-360 Algorithms for k -Internal Out-Branching....Pages 361-373 Back Matter....Pages -