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

1999 | Buch

Computers, Complexity, and Intractability from the Parametric Point of View Kapitel lesen Erstes Kapitel lesen

Parameterized Complexity

verfasst von: R. G. Downey, M. R. Fellows

Verlag: Springer New York

Buchreihe : Monographs in Computer Science

Enthalten in: Professional Book Archive

Einloggen, um Zugang zu erhalten
insite
SUCHEN

Über dieses Buch

The idea for this book was conceived over the second bottle of Villa Maria's Caber­ net Medot '89, at the dinner of the Australasian Combinatorics Conference held at Palmerston North, New Zealand in December 1990, where the authors first met and discovered they had a number of interests in common. Initially, we embarked on a small project to try to formulate reductions to address the apparent parame­ terized intractability of DOMINATING SET, and to introduce a structure in which to frame our answers. Having spent several months trying to get the definitions for the reductions right (they now seem so obvious), we turned to our tattered copies of Garey and Johnson's work [239]. We were stunned to find that virtually none of the classical reductions worked in the parameterized setting. We then wondered if we'd be able to find any interesting reductions. Several years, many more bottles, so many papers, and reductions later it [3] seemed that we had unwittingly stumbled upon what we believe is a truly central and new area of complexity theory. It seemed to us that the material would be of great interest to people working in areas where exact algorithms for a small range of parameters are natural and useful (e. g. , Molecular Biology, VLSI design). The tractability theory was rich with distinctive and powerful techniques. The intractability theory seemed to have a deep structure and techniques all of its own.

Inhaltsverzeichnis

Frontmatter

Computers, Complexity, and Intractability from the Parametric Point of View

1. Computers, Complexity, and Intractability from the Parametric Point of View
Abstract
The subject of this book is perhaps best introduced through a somewhat whimsical story.
R. G. Downey, M. R. Fellows

Parameterized Tractability

Frontmatter
2. The Basic Definitions
Abstract
Our concerns are (decision) problems with two or more inputs. Thus, we will be considering languages \(L \subseteq \Sigma * \times \Sigma *\). We refer to such languages as parameterized languages. If 〈x, k〉 is in a parameterized language L, we call k the parameter. Usually the parameter will be a positive integer, but it might be a graph or algebraic structure. However, in the interest of readability and with no loss of generality, we will usually identify the domain of the parameter as the natural numbers N and hence consider languages \(L \subseteq \Sigma * \times \mathbb{N}\). For a fixed k, we call L k = {〈x, k〉 :〈x, k〉 ∈ L} the kth slice of L.
R. G. Downey, M. R. Fellows
3. Some Ad Hoc Methods: The Methods of Bounded Search Tree and Problem Kernel
Abstract
The method of bounded search trees is probably the easiest to apply and is based on the following facts. Many combinatorial problems can be solved by algorithms that can be decomposed into two distinct parts:
  • First, within the algorithm we compute, perhaps inefficiently, some search space which is often an exponential-sized search tree.
  • Thereafter, we run some relatively efficient algorithm on each branch of the tree often simply based upon, say, depth first search.
R. G. Downey, M. R. Fellows
4. Optimization Problems, Approximation Schemes, and Their Relation with FPT
Abstract
Optimization problems are at the heart of complexity theory. In practice, we usually wish to optimize some objective function (e.g., find a least-cost tour) rather than solve a related decision problem. Furthermore, even if we demonstrate that some problem has no fast solution, it is often acceptable to find an approximate solution to some desired performance ratio. In this section, we will see that parametric complexity and approximatibility are deeply related.
R. G. Downey, M. R. Fellows
5. The Advice View Revisited and LOGSPACE
Abstract
In this brief chapter, we will further examine the advice view of parameterized tractability introduced in Chapter 2, Section 2.2. The material of the present section is a little technical and might well be omitted on the first reading of the book. Such omission will have no effect on the readability or coherence of the rest of the book.
R. G. Downey, M. R. Fellows
6. Methods via Automata and Bounded Treewidth
Abstract
Many of the methods we use on graphs are analogs of methods used for languages accepted by finite automata. Because of this, in the next few sections we will give a self-contained account of the aspects of classical formal language theory which we need. We begin with finite automata.
R. G. Downey, M. R. Fellows
7. Well-Quasi-Orderings and the Robertson-Seymour Theorems
Abstract
As we will see, well-quasi-orderings (WQO’s) provide a powerful engine for demonstrating that classes of problems are FPT. In this section, we will look at the rudiments of the theory of WQO’s, and in subsequent sections, we will examine applications to combinatorial problems.
R. G. Downey, M. R. Fellows
8. Miscellaneous Techniques
Abstract
In this chapter, we explore three additional methods for proving fixed-parameter tractability results. Two of these build upon and extend the bounded-treewidth ideas of Chapter 6. The first is the basic graph-theoretic algorithmic technique of depth-first search. The second involves a clever utilization of tree decompositions in attacking subgraph problems. The third technique employs a family of number-theoretic hash functions to address parameterized problems in the combinatorics of finite sets. In particular, we will utilize k-perfect families of hash functions.
R. G. Downey, M. R. Fellows

Parameterized Intractability

Frontmatter
9. Reductions
Abstract
In Part I, we looked at a number of methods of establishing fixed-parameter tractability. Part II is devoted to problems where there is no known method which enables us to demonstrate fixed-parameter tractability. We are concerned with the situation where we can prove, or at least have good evidence to believe, that no such method exists. As we will see, for some combinatorial problems, we can actually prove intractability. However, as with classical NP and PSPACE “intractability,” for most interesting natural problems we can only offer a completeness theory.
R. G. Downey, M. R. Fellows
10. The Basic Class W[1] and an Analog of Cook’s Theorem
Abstract
In the last chapter, we looked at one of the ingredients of classical hardness results: the notion of a reducibility. The other basic ingredient is the identification of classes of intractable problems. In the case of NP-completeness, recall that a language L is a member of the class NP iff there is a polynomial-time relation R and a polynomial p such that x ∈ L iff ∃y[|y| ≤ p(|x|) ∧ R(x, y) holds] For instance, if L is the collection of satisfiable formulas, then a formula x is satisfiable iff there is some satisfying assignment y of the variables. Recall that L is NP-complete iff L ∈ NP, and for any language L1 ∈ N P, L1 ≤ m p L. The hidden beauty and power of these definitions comes from the profound discovery that there are literally thousands of important and natural NP-complete problems. If any of them were solvable in polynomial-time, then all of them would be. Moreover, other than a few exceptions, if a natural problem is in NP and is apparently not in P, then the problem seems to always be NP-complete.
R. G. Downey, M. R. Fellows
11. Some Other W[1]-Hardness Results
Abstract
In this chapter, we will explore some further W[1]-hardness and completeness results. These examples are taken from logic, formal language theory, and from combinatorial problems arising from molecular biology. We also look at further applications of the theory to arenas such as algebra and number theory in the Exercises, where problems such as the following are proven to be W[1]-hard (and the first two are in W[2]):
R. G. Downey, M. R. Fellows
12. The W -Hierarchy
Abstract
The defining problem for the “W -Hierarchy” introduced in the present chapter, is the WEIGHTED WEFT t DEPTH h CIRCUIT SATISFIABILITY problem, WCS(t, h) (Definition 10.1). The reader should recall that this problem takes as input a decision circuit C with large gate depth t and bounded depth h and asks if C accepts a weight k input vector. This problem was introduced as a generalization of the problem WEIGHTED 3SAT. Indeed, in Chapter 10, we proved that in the case t = 1, there is no difference between the parameterized power of weft t circuits and boolean expressions of logical depth t, in the sense that we proved that WEIGHTED 3SAT is W[1]-complete.
R. G. Downey, M. R. Fellows
13. Beyond W[t]-Hardness
Abstract
The W[t]-classes reflect the intrinsic difficulty of solution checking formulas of bounded logical depth. Naturally, the question arises as to what happens if we have no bound on the depth and simply look at parameterized problems of “polynomial size.” When we do this, we arrive at classes hard for U t W[t]. The study of such classes is the theme of the present chapter. Two important classes immediately suggest themselves. These are the classes W[SAT] and W[P] generated by the following problems.
R. G. Downey, M. R. Fellows
14. Fixed Parameter Analogs of PSPACE and k-Move Games
Abstract
As we have seen, classical time complexity classes such as NP seem to split into many parameterized classes when natural parameterized versions of the problems are considered. So too, the same situation seems to occur when we look at parameterized space. Of course, a natural parameterized space class suggests itself if we wish to consider fixed-parameter space complexity.
R. G. Downey, M. R. Fellows
15. Provable Intractability: The Class X P
Abstract
We have seen many classes that are apparently different from FPT, but as with classical complexity theory, we have no proof of this fact. Moving further along, we might seek classes that are provably distinct from FPT, along the lines that EXP ≠ P. We will briefly look at one such class in this section.
R. G. Downey, M. R. Fellows

Structural and Other Results

Frontmatter
16. Another Basis for the W -Hierarchy, the Tradeoff-Theorem, and Randomized Reductions
Abstract
The fundamental separation hypothesis upon which our theory of parameterized intractability is based is W[1] ≠ FPT.
R. G. Downey, M. R. Fellows
17. Relationships with Classical Complexity and Limited Nondeterminism
Abstract
In the previous chapter, we looked at some evidence that the W -hierarchy does not collapse. Here, we will begin by looking at further results that may support this hypothesis. We analyze the following question: “Does W -hierarchy collapse imply anything unreasonable in the classical complexity classes such as NP?”
R. G. Downey, M. R. Fellows
18. The Monotone and Antimonotone Collapse Theorems: MONOTONEW[2t + 1] = W[2t] and ANTIMONOTONE W[2t + 2] = W[2t + 1]
Abstract
In this chapter, we will give proofs of the two structural collapses noted in Chapter 12.3 after Theorem 12.6. The techniques are similar to the proof of the Normalization Theorem.
R. G. Downey, M. R. Fellows
19. The Structure of Languages Under Parameterized Reducibilities
Abstract
In this rather technical chapter, we will develop techniques which will enable us to have some insight into the structure of the recursive languages under the various reducibilities. The techniques and results of this chapter have a strongly recursion-theoretic flavor and require some rather sophisticated techniques from classical recursion theory. We will assume that the reader is noddingly familiar with the basic notions from classical recursion theory, such as Kleene’s Arithmetical Hierarchy and the like, but not familiar with priority arguments.
R. G. Downey, M. R. Fellows
Backmatter
Metadaten
Titel
Parameterized Complexity
verfasst von
R. G. Downey
M. R. Fellows
Copyright-Jahr
1999
Verlag
Springer New York
Electronic ISBN
978-1-4612-0515-9
Print ISBN
978-1-4612-6798-0
DOI
https://doi.org/10.1007/978-1-4612-0515-9