Parameterized and Exact Computation
6th International Symposium, IPEC 2011, Saarbrücken, Germany, September 6-8, 2011. Revised Selected Papers
Published on 9. March 2012
VIII, 273 pages
978-3-642-28050-4 (ISBN)
Description
This book constitutes the thoroughly refereed post-conference proceedings of the 6th International Symposium on Parameterized and Exact Computation, IPEC 2011, in Saarbrücken, Germany, in September 2011. The 21 revised full papers presented were carefully reviewed and selected from 40 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, 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.
More details
Other editions
Additional editions
Dániel Marx | Peter Rossmanith
Parameterized and Exact Computation
6th International Symposium, IPEC 2011, Saarbrücken, Germany, September 6-8, 2011. Revised Selected Papers
Book
03/2012
1st Edition
Springer
€53.49
Shipment within 7-9 days
Content
- 7112
- Preface
- Organization
- Table of Contents
- On Multiway Cut Parameterized above Lower Bounds
- Introduction
- Algorithms for Multiway Cut
- From Node Multiway Cut to Almost 2-SAT
- Hardness of Node Multicut Parameterized above LP-Relaxation
- Conclusions
- References
- Parameterized Complexity of Firefighting Revisited
- Introduction
- Saving and Protecting Vertices
- W[1]-Hardness on General Graphs
- Improved Algorithm on Trees
- Tractability on Graphs of Bounded Treewidth
- Burning Vertices
- Algorithms
- No Poly-kernel for Trees
- Open Problems
- References
- Parameterized Complexity in Multiple-Interval Graphs: Domination
- Introduction
- Dominating Set
- Connected Dominating Set, Independent Dominating Set, and Dominating Clique
- Distance Dominating Set
- Perfect Code
- Distance Perfect Code
- References
- A Faster Algorithm for Dominating Set Analyzed by the Potential Method
- Introduction
- Definitions
- Potential Method
- Main Idea
- Algorithm
- Analysis
- Exponential Space
- Algorithm
- Analysis
- Conclusion
- References
- Contracting Graphs to Paths and Trees
- Introduction
- Definitions and Notation
- Tree Contraction
- Path Contraction
- Concluding Remarks
- References
- Increasing the Minimum Degreeof a Graph by Contractions
- Introduction
- Preliminaries
- Contractions
- Weighted Contractions
- Concluding Remarks
- References
- Planar Disjoint-Paths Completion
- Introduction
- Proof Strategy
- Preliminaries
- Bounding the Size of the Completion
- The Algorithm for Planar-Dpc
- The Enhancement Operation
- The Stretching Lemma
- Reducing PDPC to Topological Minor Testing
- Further Extensions and Open Problems
- References
- Sparse Solutions of Sparse Linear Systems: Fixed-Parameter Tractability and an Application of Complex Group Testing
- Introduction
- Row-Sparse Linear Systems of Equations
- A Problem Kernel for Binary Matrices
- Sparse Nonnegative Solutions of Systems of Linear Inequalities via the Complex Model of Group Testing
- Conclusions
- References
- New Upper Bounds for MAX-2-SAT and MAX-2-CSP w.r.t. the Average Variable Degree
- Introduction
- Problem Statement
- The Main Definitions
- Known Results
- New Upper Bounds
- Organization of the Paper
- A Simple Algorithm for MAX-2-SAT and MAX-2-CSP
- Removing Variables of Degree 2
- An Algorithm
- Going from the Maximal Degree to the Average Degree
- An Algorithm for MAX-2-SAT and MAX-2-CSP
- Further Directions
- References
- Improved Parameterized Algorithms for above Average Constraint Satisfaction
- Introduction
- Preliminaries
- Max-c-Lin-2 above Average
- Boolean MAX-c-CSP above Average
- MAX-c-Permutation CSP above Average
- References
- On Polynomial Kernels for Structural Parameterizations of Odd Cycle Transversal
- Introduction
- Preliminaries
- Combinatorial Properties of Separators in Labeled Graphs
- Polynomial Kernelization for (BIP Gtw(w))-OCT
- Lower Bounds for Kernelization
- Conclusion
- Kernel Bounds for Path and Cycle Problems
- Introduction
- Preliminaries
- A Property of Maximum Matchings in Bipartite Graphs
- Polynomial Kernels for Path and Cycle Problems
- Long Cycle Parameterized by a Vertex Cover
- Other Path and Cycle Problems Parameterized by Vertex Cover
- Parameterization by Max Leaf Number
- Parameterization by a Modulator to Cluster Graphs
- Lower Bounds for Path and Cycle Problems
- Directed Hamiltonian Cycle with a Modulator to Bi-paths
- Hamiltonian Cycle with a Modulator to Outerplanar Graphs
- Finding Paths with Respect to Forbidden Pairs
- Conclusion
- References
- On the Hardness of Losing Width
- Introduction
- ? -Transversal Parameterized by Vertex Cover
- Lower Bounds
- Conclusions and Perspectives
- References
- Safe Approximation and Its Relation to Kernelization
- Introduction
- Preliminaries
- Safe Approximation
- Kernelization and Safe Approximation
- Planar Dominating Set
- Feedback Vertex Set
- Multicut Problems
- Conclusion
- References
- Simpler Linear-Time Kernelization for Planar Dominating Set
- Introduction
- Overview of the New Algorithm
- Preliminaries
- Definitions and Notation
- Properties of Planar Graphs
- Near-Twin Reduction
- Description
- Correctness
- Execution Time
- Reduction Progress
- Shrinking Iterations
- Description
- Correctness
- Execution Time
- Reduction Progress
- The Complete Algorithm
- References
- Linear-Time Computation of a Linear Problem Kernel for Dominating Set on Planar Graphs
- Introduction
- Comparison to Previous Kernelizations
- Data Reduction Rules
- Private Neighborhood Rule
- Joint Neighborhood Rule
- Problem Kernel
- Conclusion
- References
- Tight Complexity Bounds for FPT Subgraph Problems Parameterized by Clique-Width
- Introduction
- Definitions and Preliminary Results
- Sparse and Dense k-Subgraph Problems
- Algorithmic Upper Bounds for Sparse k-Subgraph
- Lower Bounds
- Degree-Constrained Subgraph Problems
- Conclusion
- References
- Finding Good Decompositions for Dynamic Programming on Dense Graphs
- Introduction
- Boolean-Width
- Heuristic Algorithm
- Greedy Initialization
- Local Search
- Discussion and Implementation Details
- Experimental Results
- Small Grid Graphs
- Conclusion
- References
- Parameterized Maximum Path Coloring
- Introduction
- Definitions and Preliminaries
- Structural Parameterizations
- Parameterizations Involving the Objective Function
- Conclusions and Open Problems
- References
- On Cutwidth Parameterized by Vertex Cover
- Introduction
- Faster Cutwidth Parameterized by Vertex Cover
- Kernelization Lower Bound
- The Auxiliary Problem
- No Polykernel for Hypergraph Minimum Bisection
- From Hypergraph Minimum Bisection to Cutwidth
- Conclusions
- References
- Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics
- Introduction
- An FPT Algorithm for Graph Motif
- Introducing Twin-Covers
- Algorithms on Twin-Cover
- Graph Motif
- Equitable Coloring
- Precoloring Extension
- Boxicity
- Additional algorithms
- Monadic Second-Order Logic
- MS1 on Graphs of Bounded Vertex Cover
- MS1 on Graphs of Bounded Twin-Cover
- Concluding notes
- References
- Author Index
