Parameterized and Exact Computation: Third International Workshop, IWPEC 2008, Victoria, Canada, May 14-16, 2008, Proceedings (Lecture Notes in Computer Science, 5018)

✍ Scribed by Martin Grohe (editor), Rolf Niedermeier (editor)

• Publisher: Springer
• Year: 2008
• Tongue: English
• Leaves: 235
• Category: Library

✦ Synopsis

This book constitutes the refereed proceedings of the Third International Workshop on Parameterized and Exact Computation, IWPEC 2008, held in Victoria, Canada, in May 2008 - co-located with the 40th ACM Symposium on Theory of Computing, STOC 2008. The 17 revised full papers presented together with 3 invited lectures were carefully reviewed and selected from 32 submissions. The topics addressed cover research in all aspects of parameterized and exact computation and complexity, including but not limited to new techniques for the design and analysis of parameterized and exact algorithms, parameterized complexity theory, relationship between parameterized complexity and traditional complexity classifications, applications of parameterized computation, implementation and experiments, high-performance computing and fixed-parameter tractability.

✦ Table of Contents

Title Page
Preface
Organization
Table of Contents
Randomized Disposal of Unknowns and Implicitly Enforced Bounds on Parameters
Introduction
Disposal of a Small Unknown Subset
Implicitly Enforced Bounds on Parameters
Conclusion
Algorithmic Graph Minors and Bidimensionality
Algorithmic Meta-theorems
Parameterized Complexity of the Smallest Degree-Constrained Subgraph Problem
Introduction
Fixed-Parameter In-Tractability of MSMDd for d3
W[1]-Hardness of MSMDd for d=3
W[1]-Hardness of MSMDd for d4
Faster FPT Algorithms for Graphs with Bounded Local Tree-Width and Graphs with Excluded Minors
Graphs with Bounded Local Tree-Width
M-Minor Free Graphs
Conclusions
Fixed Structure Complexity
Introduction
Complexity and Hardness
Defining Fixed-Structure Graph Problems
Problems Equivalent to FS-Exact-Halt
Open Problems
An Improved Fixed-Parameter Algorithm for Minimum-Flip Consensus Trees
Introduction
Preliminaries
The Algorithm
Data Reduction
Solving Instances with c-Vertices of Degree at Least Three
Solving Instances with c-Vertices of Degree at Most Two
Algorithm Engineering
Experiments
Conclusion
An $O∗(1.0977^{n})$ Exact Algorithm for $\sc max independent set$ in Sparse Graphs
Introduction
Preprocessing
Branching
Dealing with Trees
The Concluding Theorem
New Fixed-Parameter Algorithms for the Minimum Quartet Inconsistency Problem
Introduction
Related Work
Our Result
Preliminaries
An O(3.0446kn + n4) Algorithm
An O(2.0162kn3 + n5) Algorithm
An O((1+)k) Algorithm
Capacitated Domination and Covering: A Parameterized Perspective
Introduction
Preliminaries
Parameterized Intractability -- Hardness Results
CDS Is W[1]-Hard Parameterized by Treewidth and Solution Size
CVC Parameterized by Treewidth Is W[1]-Hard
FPT Algorithm for CVC on Graphs of Bounded Treewidth
Conclusion
Some Fixed-Parameter Tractable Classes of Hypergraph Duality and Related Problems
Introduction
Number of Edges as Parameter
Maximum Degree as Parameter
Vertex Complementary Degree as Parameter
Results Based on the Apriori Technique
The Generalized Apriori Algorithm
Maximal Independent Sets
Maximal Frequent Sets
Concluding Remarks
A Purely Democratic Characterization of W[1]
Introduction
Preliminaries
Parameterized Complexity
Logical Circuits and the W-Hierarchy
Majority Circuits and the W"0365W-Hierarchy
W[1] W"0365W[1]
W"0365W[1] W[1]
Higher Levels of the Hierarchies
Discussion
Parameterized Complexity and Approximability of the SLCS Problem
Introduction
Definitions
Algorithmic Results for Slcs
Algorithms for Slcs
Algorithms for CSlcs
Hardness Results for Slcs
The Clases W[1] and WNL
Complexity w.r.t. q,k
Complexity w.r.t. k
Consequences for Problems of Bounded Width
Consequences for Lcs
Consequences for Other Problems
Concluding Remarks
FPT Algorithms for Path-Transversals and Cycle-Transversals Problems in Graphs
Introduction
Homogeneous Path Systems
Preliminaries
LP Formulation and Half-Integrality
Some Technical Lemmas
The Main Result
New Algorithms for the Multiway Cut and Multicut Problems
The Multiway Cut Problems
The Multicut Problem
The Vertex Multicut Problem
Feedback Set Problems on Group-Labelled Graphs
Preliminaries
The Group Feedback Vertex Set Problem
The Group Feedback Arc Set Problem
Concluding Remarks
Wheel-Free Deletion Is $W$[2]-Hard
Introduction
Notation, Terminology and Preliminaries
Wheel-Free Deletion Is $W$[2] Hard
Conclusions
References
Parameterized Derandomization
Introduction
Parameterized Randomization
The Dice Lemma
Derandomization
Questions
A Linear Kernel for Planar Feedback Vertex Set
Introduction
Preliminaries
Domination
Rules
Simple Rules
Less Simple Rules
The Algorithm
Automated Proofs
A Linear Bound on the Size of the Kernel
Improving the Bound on the Size of the Kernel
Conclusions
Parameterized Chess
Games as Combinatorial Problems
The Class AW[]
The Game of Short Generalized Chess
Parameterized Membership of Short Generalized Chess
Encoding Positions
The Winning Condition
Formula $F$
Testing for Broken Rules
Correctness of the Reduction
Hardness of Short Generalized Chess
The Time Complexity of Constraint Satisfaction
Introduction
Preliminaries
Binary Sparse CSP (Proof of Theorem 1)
Unique CSP (Theorem 2)
A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances
Introduction
Preliminaries
On Analysis by Compound Measure
Problem Definition and Algorithm
Analysis: Maximum Degree 4
Analysis: The General Case
Conclusions
Exact Algorithms for Edge Domination
Introduction
Preliminaries
Using Minimal Vertex Covers for Edge Dominating Set
Design by Measure and Conquer
Related Problems
Conclusion and Further Research
Author Index