Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben

2015 | Buch

Introduction Kapitel lesen Erstes Kapitel lesen

Parameterized Algorithms

verfasst von: Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh

Verlag: Springer International Publishing

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten
insite
SUCHEN

Über dieses Buch

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[1]-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.

Inhaltsverzeichnis

Frontmatter

Basic Toolbox

Frontmatter
Chapter 1. Introduction
Abstract
A squirrel, a platypus and a hamster walk into a bar…
Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh
Chapter 2. Kernelization
Abstract
Kernelization is a systematic approach to study polynomial-time preprocessing algorithms. It is an important tool in the design of parameterized algorithms. In this chapter we explain basic kernelization techniques such as crown decomposition, the expansion lemma, the sunflower lemma, and linear programming. We illustrate these techniques by obtaining kernels for Vertex Cover, Feedback Arc Set in Tournaments, Edge Clique Cover, Maximum Satisfiablity, and d-HittingSet.
Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh
Chapter 3. Bounded Search Trees
Abstract
In this chapter we introduce a variant of exhaustive search, namely the method of bounded search trees. This is one of the most commonly used tools in the design of fixed-parameter algorithms. We illustrate this technique with algorithms for two different parameterizations of Vertex Cover, as well as for the problems (undirected) Feedback Vertex Set and Closest String.
Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh
Chapter 4. Iterative Compression
Abstract
In this chapter we introduce iterative compression, a simple yet very useful technique for designing fixed parameter tractable algorithms. Using this technique we obtain FPT algorithms for Feedback Vertex Set in Tournatments, Feedback Vertex Set and Odd Cycle Transversal.
Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh
Chapter 5. Randomized Methods in Parameterized Algorithms
Abstract
In this chapter, we study how the powerful paradigm of randomization can help in designing FTP algorithms. We introduce the general techniques of color coding, divide and color, and chromatic coding, and show the use of these techniques on the problems Longest Path and d-Clustering. We discuss also how these randomized algorithms can be derandomized using standard techniques.
Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh
Chapter 6. Miscellaneous
Abstract
In this chapter, we gather a few algorithmic tools that we feel are important, but do not fit into any of the previous chapters. First, we discuss exponentialtime dynamic-programming algorithms that consider all subsets of a certain set when defining the subproblems. Second, we introduce the Integer Linear Programming Feasibility problem, formulate the classical results on how to solve it in the case of a bounded number of variables, and show an example of its application in fixed-parameter algorithms. Finally, we discuss the algorithmic implications of the Robertson-Seymour theorem on graph minors.
Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh
Chapter 7. Treewidth
Abstract
The treewidth of a graph is one of the most frequently used tools in parameterized algorithms. Intuitively, treewidth measures how well the structure of a graph can be captured by a tree-like structural decomposition. When the treewidth of a graph is small, or equivalently the graph admits a good tree decomposition, then many problems intractable on general graphs become efficiently solvable. In this chapter we introduce treewidth and present its main applications in parameterized complexity. We explain how good tree decompositions can be exploited to design fast dynamic-programming algorithms. We also show how treewidth can be used as a tool in more advanced techniques, like shifting strategies, bidimensionality, or the irrelevant vertex approach.
Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh

Advanced Algorithmic Techniques

Frontmatter
Chapter 8. Finding cuts and separators
Abstract
The notion of important cuts and the related combinatorial bounds give a useful tool for showing the fixed-parameter tractability of problems where a graph has to be cut into certain parts. We discuss how this technique can be used to show that Edge Multiway Cut and Directed Feedback Vertex Set are FPT. Random sampling of important separators is a recent extension of this method, making it applicable to a wider range of problems. We illustrate how this extension works on a clustering problem called (p, q)-Partition.
Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh
Chapter 9. Advanced kernelization algorithms
Abstract
The systematic study of the kernelization framework, whose foretaste we had in Chapter 2 , revealed an intrinsic mathematical richness of this notion. In particular, many classic techniques turn out to be very useful in this context; examples include tools of combinatorial optimization, linear algebra, probabilistic arguments, or results of the graph minors theory. In this chapter, we provide an overview of some of the most interesting examples of more advanced kernelization algorithms. In particular, we provide a quadratic kernel for the Feedback Vertex Set problem. We also discuss the topics of above guarantee parameterizations in the context of kernelization, of kernelization on planar graphs, and of so-called Turing kernelization.
Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh
Chapter 10. Algebraic techniques: sieves, convolutions, and polynomials
Abstract
In this chapter we discuss selected techniques that have some “algebraic flavor,” i.e., they use manipulation of algebraic expression, rather than analyzing the combinatorial properties of objects. Another common theme in these techniques is “sieving”: we sieve out some unwanted objects by means of algebraic cancellation.
Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh
Chapter 11. Improving dynamic programming on tree decompositions
Abstract
In this chapter we consider more sophisticated dynamic-programming routines for graphs of bounded treewidth, compared with the classic ones described in Chapter 7. We give examples of algorithms based on subset convolution, Cut & Count and rank-based approaches.
Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh
Chapter 12. Matroids
Abstract
Tools and techniques from matroid theory have proven very useful in the design of parameterized algorithms and kernels. In this chapter, we showcase how a polynomial-time algorithm for Matroid Parity can be used as a subroutine in an FPT algorithm for Feedback Vertex Set . We then define the notion of representative sets, and use it to give polynomial kernels for d-Hitting Set and d-Set Packing , and fast (deterministic) FPT algorithms for Longest Path and Long Directed Cycle.
Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh

Lower Bounds

Frontmatter
Chapter 13. Fixed-parameter intractability
Abstract
In this chapter, we use parameterized reductions and W[1]-hardness to provide evidence that certain parameterized problems are unlikely to be fixed parameter tractable.
Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh
Chapter 14. Lower Bounds Based on the Exponential-Time Hypothesis
Abstract
The Exponential Time Hypothesis (ETH) is a conjecture stating that, roughly speaking, n-variable 3-SAT cannot be solved in time 2o(n). In this chapter, we prove lower bounds based on ETH for the time needed to solve various problems. In many cases, these lower bounds match (up to small factors) the running time of the best known algorithms for the problem.
Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh
Chapter 15. Lower bounds for kernelization
Abstract
In this chapter we discuss methodologies for proving lower bounds for kernelization. We describe the technique of compositionality, which is the main tool for proving negative results about the existence of polynomial kernels. We also give an introduction to weak compositions, which can be used to provide more precise lower bounds on kernel sizes.
Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh
Backmatter
Metadaten
Titel
Parameterized Algorithms
verfasst von
Marek Cygan
Fedor V. Fomin
Łukasz Kowalik
Daniel Lokshtanov
Dániel Marx
Marcin Pilipczuk
Michał Pilipczuk
Saket Saurabh
Copyright-Jahr
2015
Electronic ISBN
978-3-319-21275-3
Print ISBN
978-3-319-21274-6
DOI
https://doi.org/10.1007/978-3-319-21275-3

Premium Partner

    Bildnachweise