Parameterized and Exact Computation: 9th International Symposium, IPEC 2014, Wroclaw, Poland, September 10-12, 2014. Revised Selected Papers

✍ Scribed by Marek Cygan, Pinar Heggernes (eds.)

• Publisher: Springer International Publishing
• Year: 2014
• Tongue: English
• Leaves: 352
• Series: Lecture Notes in Computer Science 8894 Theoretical Computer Science and General Issues
• Edition: 1
• Category: Library

✦ Synopsis

This book constitutes the thoroughly refereed post-conference proceedings of the 9th International Symposium on Parameterized and Exact Computation, IPEC 2014, in Wroclaw, Poland, in September 2014. The 27 revised full papers presented together with one invited paper were carefully reviewed and selected from 42 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 exponential-time computation; and implementation issues of parameterized and exact exponential-time algorithms.

✦ Table of Contents

Front Matter....Pages I-IX
Lower Bounds for Kernelization....Pages 1-14
On the Parameterized Complexity of Associative and Commutative Unification....Pages 15-27
On Polynomial Kernelization of $$\mathcal {H}$$ - free Edge Deletion ....Pages 28-38
Solving Linear Equations Parameterized by Hamming Weight....Pages 39-50
The Parameterized Complexity of Geometric Graph Isomorphism....Pages 51-62
The Role of Planarity in Connectivity Problems Parameterized by Treewidth....Pages 63-74
Parameterized Inapproximability of Degree Anonymization....Pages 75-84
The $$k$$ -Distinct Language: Parameterized Automata Constructions....Pages 85-96
A $$14k$$ -Kernel for Planar Feedback Vertex Set via Region Decomposition....Pages 97-109
The Complexity of Bounded Length Graph Recoloring and CSP Reconfiguration....Pages 110-121
Quantified Conjunctive Queries on Partially Ordered Sets....Pages 122-134
Graph Isomorphism Parameterized by Elimination Distance to Bounded Degree....Pages 135-146
Exact Exponential Algorithms to Find a Tropical Connected Set of Minimum Size....Pages 147-158
A Tight Algorithm for Strongly Connected Steiner Subgraph on Two Terminals with Demands (Extended Abstract)....Pages 159-171
The Firefighter Problem: A Structural Analysis....Pages 172-183
AND-compression of NP-complete Problems: Streamlined Proof and Minor Observations....Pages 184-195
Editing to a Graph of Given Degrees....Pages 196-207
Polynomial Kernels and User Reductions for the Workflow Satisfiability Problem....Pages 208-220
Finding Shortest Paths Between Graph Colourings....Pages 221-233
Shortest Paths in Nearly Conservative Digraphs....Pages 234-245
Reconfiguration over Tree Decompositions....Pages 246-257
Finite Integer Index of Pathwidth and Treewidth....Pages 258-269
A Parameterized Study of Maximum Generalized Pattern Matching Problems....Pages 270-281
Improved FPT Algorithms for Weighted Independent Set in Bull-Free Graphs....Pages 282-293
Improved Parameterized Algorithms for Network Query Problems....Pages 294-306
On Kernels for Covering and Packing ILPs with Small Coefficients....Pages 307-318
No Small Nondeterministic Read-Once Branching Programs for CNFs of Bounded Treewidth....Pages 319-331
The Relative Exponential Time Complexity of Approximate Counting Satisfying Assignments....Pages 332-341
Back Matter....Pages 343-343

✦ Subjects

Computer Science, general; Algorithm Analysis and Problem Complexity; Algorithms; Discrete Mathematics in Computer Science; Math Applications in Computer Science; Discrete Mathematics in Computer Science