This comprehensive textbook presents a clean and coherent account of most fundamental tools and techniques in Parameterized Algorithms and is a self-contained guide to the area. The book covers many of the recent developments of the field, including application of important separators, branching based on linear programming, Cut & Count to obtain faster algorithms on tree decompositions, algorithms based on representative families of matroids, and use of the Strong Exponential Time Hypothesis. A number of older results are revisited and explained in a modern and didactic way. The book provides a toolbox of algorithmic techniques. Part I is an overview of basic techniques, each chapter discussing a certain algorithmic paradigm. The material covered in this part can be used for an introductory course on fixed-parameter tractability. Part II discusses more advanced and specialized algorithmic ideas, bringing the reader to the cutting edge of current research. Part III presents complexity results and lower bounds, giving negative evidence by way of W-hardness, the Exponential Time Hypothesis, and kernelization lower bounds. All the results and concepts are introduced at a level accessible to graduate students and advanced undergraduate students. Every chapter is accompanied by exercises, many with hints, while the bibliographic notes point to original publications and related work.
While polynomial-time approximation algorithms remain a dominant notion in tackling computationally hard problems, the framework of parameterized complexity has been emerging rapidly in recent years. Roughly speaking, the analytic framework of parameterized complexity attempts to grasp the difference between problems which admit O(c k . poly(n))-time algorithms such as Vertex Cover, and problems like Dominating Set for which essentially brute-force O(n k)-algorithms are best possible until now. Problems of the former type is said to be fixed-parameter tractable (FPT) and those of the latter type are regarded intractable. In this thesis, we investigate some problems on directed graphs and a number of constraint satisfaction problems (CSPs) from the parameterized perspective. We develop fixed-parameter algorithms for some digraph problems. In particular, we focus on the basic problem of finding a tree with certain property embedded in a given digraph. New or improved fpt-algorthms are presented for finding an out-branching with many or few leaves (Directed Maximum Leaf, Directed Minimum Leaf problems). For acyclic digraphs, Directed Maximum Leaf is shown to allow a kernel with linear number of vertices. We suggest a kernel for Directed Minimum Leaf with quadratic number of vertices. An improved fpt-algorithm for finding k-Out-Tree is presented and this algorithm is incorporated as a subroutine to obtain a better algorithm for Directed Minimum Leaf. In the second part of this thesis, we concentrate on several CSPs in which we want to maximize the number of satisfied constraints and consider parameterization "above tight lower bound" for these problems. To deal with this type of parameterization, we present a new method called SABEM using probabilistic approach and applying harmonic analysis on pseudo-boolean functions. Using SABEM we show that a number of CSPs admit polynomial kernels, thus being fixed-parameter tractable. Moreover, we suggest some problem-specific combinatorial approaches to Max-2-Sat and a wide special class of Max-Lin2, which lead to a kernel of smaller size than what can be obtained using SABEM for respective problems.
19th Annual European Symposium, Saarbrücken, Germany, September 5-9, 2011, Proceedings
Author: Camil Demetrescu
This book constitutes the refereed proceedings of the 19th Annual European Symposium on Algorithms, ESA 2011, held in Saarbrücken, Germany, in September 2011 in the context of the combined conference ALGO 2011. The 67 revised full papers presented were carefully reviewed and selected from 255 initial submissions: 55 out of 209 in track design and analysis and 12 out of 46 in track engineering and applications. The papers are organized in topical sections on approximation algorithms, computational geometry, game theory, graph algorithms, stable matchings and auctions, optimization, online algorithms, exponential-time algorithms, parameterized algorithms, scheduling, data structures, graphs and games, distributed computing and networking, strings and sorting, as well as local search and set systems.
Third International Workshop, IWPEC 2008, Victoria, Canada, May 14-16, 2008, Proceedings
Author: Martin Grohe
Publisher: Springer Science & Business Media
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.
19th International Symposium, ISAAC 2008, Gold Coast, Australia, December 15-17, 2008. Proceedings
Author: Seok-Hee Hong
This volume contains the proceedings of the 19th International Symposium on Algorithmsand Computation (ISAAC 2008),held on the Gold Coast, Australia, December 15–17, 2008. In the past, it was held in Tokyo (1990), Taipei (1991), Nagoya (1992), Hong Kong (1993), Beijing (1994), Cairns (1995), Osaka (1996), Singapore (1997), Daejeon (1998), Chennai (1999), Taipei (2000), Christchurch (2001), Vancouver (2002), Kyoto (2003), Hong Kong (2004), Hainan (2005), Kolkata (2006), and Sendai (2007). ISAACis anannualinternationalsymposiumthatcoversthe verywide range of topics in the ?eld of algorithms and computation. The main purpose of the symposium is to provide a forum for researchers working in algorithms and theoryofcomputationfrom allovertheworld.In responseto ourcallfor papers, we received 229 submissions from 40 countries. The task of selecting the papers in this volume was done by our Program Committee and many other external reviewers. After an extremely rigorous review process and extensive discussion, the Committee selected 78 papers. We hope all accepted papers will eventually appear in scienti?c journals in a more polished form. Two special issues, one of Algorithmica and one of the International Journal on Computational Geometry and Applications, with selected papers from ISAAC 2008 are in preparation.
An application-oriented introduction to the highly topical area of the development and analysis of efficient fixed-parameter algorithms for hard problems. Aimed at graduate and research mathematicians, algorithm designers, and computer scientists, it provides a fresh view on this highly innovative field of algorithmic research.
9th International Workshop, WADS 2005, Waterloo, Canada, August 15-17, 2005, Proceedings
Author: Frank Dehne
Publisher: Springer Science & Business Media
This book constitutes the refereed proceedings of the 9th International Workshop on Algorithms and Data Structures, WADS 2005, held in Waterloo, Canada, in August 2005. The 37 revised full papers presented were carefully reviewed and selected from 90 submissions. A broad variety of topics in algorithmics and data structures is addressed including searching and sorting, approximation, graph and network computations, computational geometry, randomization, communications, combinatorial optimization, scheduling, routing, navigation, coding, and pattern matching.
8th International Symposium, IPEC 2013, Sophia Antipolis, France, September 4-6, 2013, Revised Selected Papers
Author: Gregory Gutin
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.
9th International Symposium, IPEC 2014, Wroclaw, Poland, September 10-12, 2014. Revised Selected Papers
Author: Marek Cygan
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.