CiteULike: AbnerCYH's parameterized

Width Parameters Beyond Tree-width and their Applications

Petr Hlineny — 2008-05-02T14:57:45-00:00

The Computer Journal, Vol. 51, No. 3. (1 May 2008), pp. 326-362.

Besides the very successful concept of tree-width (see [Bodlaender, H. and Koster, A. (2007) Combinatorial optimisation on graphs of bounded treewidth. These are special issues on Parameterized Complexity]), many concepts and parameters measuring the similarity or dissimilarity of structures compared to trees have been born and studied over the past years. These concepts and parameters have proved to be useful tools in many applications, especially in the design of efficient algorithms. Our presented novel look at the contemporary developments of these width' parameters in combinatorial structures delivers--besides traditional tree-width and derived dynamic programming schemes--also a number of other useful parameters like branch-width, rank-width (clique-width) or hypertree-width. In this contribution, we demonstrate how width' parameters of graphs and generalized structures (such as matroids or hypergraphs), can be used to improve the design of parameterized algorithms and the structural analysis in other applications on an abstract level. 10.1093/comjnl/bxm052

Parameterized Complexity of Geometric Problems

Panos Giannopoulos — 2008-05-02T14:57:42-00:00

The Computer Journal, Vol. 51, No. 3. (1 May 2008), pp. 372-384.

This paper surveys parameterized complexity results for hard geometric algorithmic problems. It includes fixed-parameter tractable problems in graph drawing, geometric graphs, geometric covering and several other areas, together with an overview of the algorithmic techniques used. Fixed-parameter intractability results are surveyed as well. Finally, we give some directions for future research. 10.1093/comjnl/bxm053

Combinatorial Optimization on Graphs of Bounded Treewidth

Hans Bodlaender — 2008-05-02T14:42:37-00:00

The Computer Journal, Vol. 51, No. 3. (1 May 2008), pp. 255-269.

There are many graph problems that can be solved in linear or polynomial time with a dynamic programming algorithm when the input graph has bounded treewidth. For combinatorial optimization problems, this is a useful approach for obtaining fixed-parameter tractable algorithms. Starting from trees and series-parallel graphs, we introduce the concepts of treewidth and tree decompositions, and illustrate the technique with the Weighted Independent Set problem as an example. The paper surveys some of the latest developments, putting an emphasis on applicability, on algorithms that exploit tree decompositions, and on algorithms that determine or approximate treewidth and find tree decompositions with optimal or close to optimal treewidth. Directions for further research and suggestions for further reading are also given. 10.1093/comjnl/bxm037

Fixed-Parameter Tractability, Definability, and Model-Checking

Jörg Flum — 2008-03-26T09:20:01-00:00

SIAM Journal on Computing, Vol. 31, No. 1. (2001), pp. 113-145.

Pages 113-145,

Techniques for Practical Fixed-Parameter Algorithms

Falk Huffner — 2008-01-10T14:03:22-00:00

The Computer Journal, Vol. 51, No. 1. (1 January 2008), pp. 7-25.

The fixed-parameter approach is an algorithm design technique for solving combinatorially hard (mostly NP-hard) problems. For some of these problems, it can lead to algorithms that are both efficient and yet at the same time guaranteed to find optimal solutions. Focusing on their application to solving NP-hard problems in practice, we survey three main techniques to develop fixed-parameter algorithms, namely: kernelization (data reduction with provable performance guarantee), depth-bounded search trees and a new technique called iterative compression. Our discussion is circumstantiated by several concrete case studies and provides pointers to various current challenges in the field. 10.1093/comjnl/bxm040

On Two Techniques of Combining Branching and Treewidth

Fedor Fomin — 2007-12-19T05:33:25-00:00

Algorithmica

Abstract Branch & Reduce and dynamic programming on graphs of bounded treewidth are among the most common and powerful techniques used in the design of moderately exponential time exact algorithms for NP hard problems. In this paper we discuss the efficiency of simple algorithms based on combinations of these techniques. The idea behind these algorithms is very natural: If a parameter like the treewidth of a graph is small, algorithms based on dynamic programming perform well. On the other side, if the treewidth is large, then there must be vertices of high degree in the graph, which is good for branching algorithms. We give several examples of possible combinations of branching and programming which provide the fastest known algorithms for a number of NP hard problems. All our algorithms require non-trivial balancing of these two techniques. In the first approach the algorithm either performs fast branching, or if there is an obstacle for fast branching, this obstacle is used for the construction of a path decomposition of small width for the original graph. Using this approach we give the fastest known algorithms for Minimum Maximal Matching and for counting all 3-colorings of a graph. In the second approach the branching occurs until the algorithm reaches a subproblem with a small number of edges (and here the right choice of the size of subproblems is crucial) and then dynamic programming is applied on these subproblems of small width. We exemplify this approach by giving the fastest known algorithm to count all minimum weighted dominating sets of a graph. We also discuss how similar techniques can be used to design faster parameterized algorithms.

Improved Algorithms and Complexity Results for Power Domination in Graphs

Jiong Guo — 2007-12-10T04:17:39-00:00

Algorithmica

Abstract The NP-complete Power Dominating Set problem is an “electric power networks variant” of the classical domination problem in graphs: Given an undirected graph G=(V,E), find a minimum-size set P⊆V such that all vertices in V are “observed” by the vertices in P. Herein, a vertex observes itself and all its neighbors, and if an observed vertex has all but one of its neighbors observed, then the remaining neighbor becomes observed as well. We show that Power Dominating Set can be solved by “bounded-treewidth dynamic programs.” For treewidth being upper-bounded by a constant, we achieve a linear-time algorithm. In particular, we present a simplified linear-time algorithm for Power Dominating Set in trees. Moreover, we simplify and extend several NP-completeness results, particularly showing that Power Dominating Set remains NP-complete for planar graphs, for circle graphs, and for split graphs. Specifically, our improved reductions imply that Power Dominating Set parameterized by |P| is W[2]-hard and it cannot be better approximated than Dominating Set.

On Fixed-Parameter Tractability and Approximability of NP Optimization Problems

Liming Cai — 2007-11-15T09:24:36-00:00

Journal of Computer and System Sciences, Vol. 54, No. 3. (June 1997), pp. 465-474.

Fixed-parameter tractability of NP optimization problems is studied by relating it to approximability of the problems. It is shown that an NP optimization problem is fixed-parameter tractable if it admits a fully polynomial-time approximation scheme, or if it belongs to the class MAX SNP or to the class MIN F+[Pi]1. This provides strong evidence that noW[1]-hard NP optimization problems belong to these optimization classes and includes a very large class of approximable optimization problems into the class of fixed-parameter tractable problems. Evidence is also demonstrated to support the current working hypothesis in the theory of fixed-parameter tractability.

Fixed-Parameter Approximation: Conceptual Framework and Approximability Results

Liming Cai — 2007-11-13T17:12:09-00:00

Parameterized and Exact Computation (2006), pp. 96-108.

The notion of fixed-parameter approximation is introduced to investigate the approximability of optimization problems within the framework of fixed-parameter computation. This work partially aims at enhancing the world of fixed-parameter computation in parallel with the conventional theory of computation that includes both exact and approximate computations. In particular, it is proved that fixed-parameter approximability is closely related to the approximation of small-cost solutions in polynomial time. It is also demonstrated that many fixed-parameter intractable problems are not fixed-parameter approximable. On the other hand, fixed-parameter approximation appears to be a viable approach to solving some inapproximable yet important optimization problems. For instance, all problems in the class MAX SNP admit fixed-parameter approximation schemes in time O(2O((1– ε/O(1))k)p(n)) for any small ε> 0.

Parameterized Approximation Problems

Rodney Downey — 2007-11-13T17:06:43-00:00

Parameterized and Exact Computation (2006), pp. 121-129.

Up to now, most work in the area of parameterized complexity has focussed on exact algorithms for decision problems. The goal of this paper is to apply parameterized ideas to approximation. We begin exploration of parameterized approximation problems, where the problem in question is a parameterized decision problem, and the required approximation factor is treated as a second parameter for the problem.

Parameterized complexity and polynomial-time approximation schemes

Xiuzhen Huang — 2007-11-13T10:33:37-00:00

(December 2004)

According to the theory of NPcompleteness, many problems that have important realworld applications are NPhard. This excludes the possibility of solving them in polynomial time unless P=NP. A number of approaches have been proposed in dealing with NPhard problems, among them are approximation algorithms and parameterized algorithms. The study of approximation algorithms tries to ﬁnd good enough solutions instead of optimal solutions in polynomial time, while parameterized algorithms try to give exact solutions when a natural parameter is small. In this thesis, we study the structural properties of parameterized computation and approximation algorithms for NP optimization problems. In particular, we investigate the relationship between parameterized complexity and polynomialtime approximation scheme (PTAS) for NP optimization problems. We give nice characterizations for two important subclasses in PTAS: Fully Polynomial Time Approximation Scheme (FPTAS) and Effcient Polynomial Time Approximation Scheme (EPTAS), using the theory of parameterized complexity. Our characterization of the class FPTAS has its advantages over the former characterizations, and our characterization of EPTAS is the ﬁrst systematic investigation of this new but important approximation class. We develop new techniques to derive strong computational lower bounds for certain parameterized problems based on the theory of parameterized complexity. For example, we prove that unless an unlikely collapse occurs in parameterized complexity theory, the clique problem could not be solved in time O(f (k)no(k)) for any function f . This lower bound matches the upper bound of the trivial algorithm that simply enumerates and checks all subsets of k vertices in the given graph of n vertices. We then extend our techniques to derive computational lower bounds for PTAS and EPTAS algorithms of NP optimization problems. We prove that certain NP optimization problems with known PTAS algorithms have no PTAS algorithms of running time O(f (1/Epsilon)no(1/Epsilon)) for any function f . Therefore, for these NP optimization problems, although theoretically they can be approximated in polynomial time to an arbitrarily small error bound Epsilon, they have no practically effective approximation algorithms for small error bound Epsilon. To our knowledge, this is the ﬁrst time such lower bound results have been derived for PTAS algorithms. This seems to open a new direction for the study of computational lower bounds on the approximability of NP optimization problems.

Minimum Membership Set Covering and the Consecutive Ones Property

Michael Dom — 2007-11-11T18:05:08-00:00

Algorithm Theory – SWAT 2006 (2006), pp. 339-350.

The Minimum Membership Set Cover problem has recently been introduced and studied in the context of interference reduction in cellular networks. It has been proven to be notoriously hard in several aspects. Here, we investigate how natural generalizations and variations of this problem behave in terms of the consecutive ones property: While it is well-known that classical set covering problems become polynomial-time solvable when restricted to instances obeying the consecutive ones property, we experience a significantly more intricate complexity behavior in the case of Minimum Membership Set Cover. We provide polynomial-time solvability, NP-completeness, and approximability results for various cases here. In addition, a number of interesting challenges for future research is exhibited.

On The Parameterized Intractability Of Motif Search Problems

Michael Fellows — 2007-11-10T19:07:09-00:00

Combinatorica, Vol. 26, No. 2. (30 April 2006), pp. 141-167.

We show that Closest Substring, one of the most important problems in the field of consensus string analysis, is W[1]-hard when parameterized by the number k of input strings (and remains so, even over a binary alphabet). This is done by giving a “strongly structure-preserving” reduction from the graph problem Clique to Closest Substring. This problem is therefore unlikely to be solvable in time O(f(k)•nc) for any function f of k and constant c independent of k, i.e., the combinatorial explosion seemingly inherent to this NP-hard problem cannot be restricted to parameter k. The problem can therefore be expected to be intractable, in any practical sense, for k ≥ 3. Our result supports the intuition that Closest Substring is computationally much harder than the special case of Closest String, althoughb othp roblems are NP-complete. We also prove W[1]-hardness for other parameterizations in the case of unbounded alphabet size. Our W[1]-hardness result for Closest Substring generalizes to Consensus Patterns, a problem arising in computational biology.

Parameterized Complexity and Biopolymer Sequence Comparison

Liming Cai — 2007-11-10T18:57:42-00:00

The Computer Journal, Vol. 51, No. 3. (27 June 2007), bxm035.

The paper surveys parameterized algorithms and complexities for computational tasks on biopolymer sequences, including the problems of longest common subsequence, shortest common supersequence, pairwise sequence alignment, multiple sequencing alignment, structure-sequence alignment and structure-structure alignment. Algorithm techniques, built on the structural-unit level as well as on the residue level, are discussed. 10.1093/comjnl/bxm035

On the Parameterized Intractability of CLOSEST SUBSTRING and Related Problems

Michael Fellows — 2007-11-10T12:15:30-00:00

STACS 2002: 19th Annual Symposium on Theoretical Aspects of Computer Science, Antibes - Juan les Pins, France, March 14-16, 2002. Proceedings (2002), pp. 734-734.

We show that CLOSEST SUBSTRING, one of the most important problems in the field of biological sequence analysis, is W[1]-hard with respect to the number k of input strings (even over a binary alphabet). This problem is therefore unlikely to be solvable in time $O(f(k)n^c)$ for any function f and constant c independent of k - effectively, the problem can be expected to be intractable, in any practical sense, for k $≥ 3$. Our result supports the intuition that CLOSEST SUBSTRING is computationally much harder than the special case of CLOSEST STRING, although both problems are NP-complete and both possess polynomial time approximation schemes. We also prove W[1]-hardness for other parameterizations in the case of unbounded alphabet size. Our main W[1]-hardness result generalizes to CONSENSUS PATTERNS, a problem of similar significance in computational biology.

Fixed-parameter tractability and completeness II: On completeness for W[1]

Rod Downey — 2007-11-10T09:13:48-00:00

Theoretical Computer Science, Vol. 141, No. 1-2. (17 April 1995), pp. 109-131.

For many fixed-parameter problems that are trivially solvable in polynomial-time, such as k-DOMINATING SET, essentially no better algorithm is presently known than the one which tries all possible solutions. Other problems, such as FEEDBACK VERTEX SET, exhibit fixed-parameter tractability: for each fixed k the problem is solvable in time bounded by a polynomial of degree c, where c is a constant independent of k. In a previous paper, the W Hierarchy of parameterized problems was defined, and complete problems were identified for the classes W[t] for t [greater-or-equal, slanted] 2. Our main result shows that INDEPENDENT SET is complete for W[1].

Invitation to Fixed Parameter Algorithms (Oxford Lecture Series in Mathematics and Its Applications)

Rolf Niedermeier — 2007-11-10T08:38:36-00:00

(20 March 2006)

A fixed-parameter is an algorithm that provides an optimal solution to a combinatorial problem. This research-level text is an application-oriented introduction to the growing and highly topical area of the development and analysis of efficient fixed-parameter algorithms for hard problems. <br>The book is divided into three parts: a broad introduction that provides the general philosophy and motivation; followed by coverage of algorithmic methods developed over the years in fixed-parameter algorithmics forming the core of the book; and a discussion of the essential from parameterized<br>hardness theory with a focus on W [1]-hardness, which parallels NP-hardness, then stating some relations to polynomial-time approximation algorithms, and finishing up with a list of selected case studies to show the wide range of applicability of the presented methodology. <br>Aimed at graduate and research mathematicians, programmers, algorithm designers and computer scientists, the book introduces the basic techniques and results and provides a fresh view on this highly innovative field of algorithmic research.

Polynomial time approximation schemes and parameterized complexity

Jianer Chen — 2007-11-08T18:10:21-00:00

Discrete Appl. Math., Vol. 155, No. 2. (January 2007), pp. 180-193.

Parameterized Complexity and Approximation Algorithms

Daaniel Marx — 2007-11-08T18:10:19-00:00

The Computer Journal (28 July 2007), bxm048.

Approximation algorithms and parameterized complexity are usually considered to be two separate ways of dealing with hard algorithmic problems. In this paper, our aim is to investigate how these two fields can be combined to achieve better algorithms than what any of the two theories could offer. We discuss the different ways parameterized complexity can be extended to approximation algorithms, survey results of this type and propose directions for future research. 10.1093/comjnl/bxm048

Infeasibility of Instance Compression and Succinct PCPs for NP

Lance Fortnow — 2007-11-08T17:00:38-00:00

No. TR07-096. (2007)

We study the notion of "instance compressibility" of NP problems [Harnik-Naor06], closely related to the notion of kernelization in parameterized complexity theory [Downey-Fellows99, Flum-Grohe06, Niedermeier06]. A language $L$ in NP is instance compressible if there is a polynomial-time computable function $f$ and a set $A$ such that for each instance $x$ of $L$, $f(x)$ is of size polynomial in the it witness size of $x$, and $f$ reduces $L$ to $A$. We prove that SAT is not instance compressible unless NP is contained in coNP/poly, and the Polynomial Hierarchy collapses. This result settles an open problem posed by [Harnik-Naor06] and [Downey07], and has a number of implications: 1. A number of parametric NP problems, including SAT, Clique, DominatingSet and IntegerProgramming, are not polynomially kernelizable unless NP is contained in coNP/poly. 2. SAT does not have "succinct PCPs", i.e., PCPs of size polynomial in the number of variables, unless NP is contained in coNP/poly. 3. An approach of Harnik and Naor to constructing collision-resistant hash functions from one-way functions is inviable in its present form. 4. (Burhman) There are no sub-exponential size complete sets for NP or coNP unless NP is contained in coNP/poly.

Some New Techniques in Design and Analysis of Exact (Exponential) Algorithms

Fedor Fomin — 2007-11-06T13:50:37-00:00

Bulletin of the EATCS, Vol. 87 (2005), pp. 47-77.

On Parameterized Approximability

Yijia Chen — 2007-11-06T11:20:17-00:00

Vol. TR07-106 (28 October 2007)

Combining classical approximability questions with parameterized complexity, we introduce a theory of parameterized approximability. The main intention of this theory is to deal with the efficient approximation of small cost solutions for optimisation problems.

The parameterized complexity of sequence alignment and consensus

Hans Bodlaender — 2007-10-23T08:01:04-00:00

Theoretical Computer Science, Vol. 147, No. 1-2. (7 August 1995), pp. 31-54.

The problem is examined from the point of view of parameterized computational complexity. There are several different ways in which parameters enter the problem, such as the number of sequences to be analyzed, the length of the common subsequence, and the size of the alphabet. Lower bounds on the complexity of this basic problem imply lower bounds on a number of other sequence alignment and consensus problems. An issue in the theory of parameterized complexity is whether a problem which takes input (x, k) can be solved in time f(k) [middle dot] n[alpha] where [alpha] is independent of k (termed fixed-parameter tractability). It can be argued that this is the appropriate asymptotic model of feasible computability for problems for which a small range of parameter values covers important applications -- a situation which certainly holds for many problems in biological sequence analysis. Our main results show that: 1. (1) The (LCS) parameterized by the number of sequences to be analyzed is hard for W[t] for all t. 2. (2) The LCS problem, parameterized by the length of the common subsequence, belongs to W[P] and is hard for W[2]. 3. (3) The LCS problem parameterized both by the number of sequences and the length of the common subsequence, is complete for W[1]. All of the above results are obtained for unrestricted alphabet sizes. For alphabets of a fixed size, problems (2) and (3) are fixed-parameter tractable. We conjecture that (1) remains hard.

Linear time algorithms for NP-hard problems restricted to partial k-trees

Stefan Arnborg — 2007-10-03T12:34:55-00:00

Discrete Applied Mathematics, Vol. 23, No. 1. (April 1989), pp. 11-24.

We present and illustrate by a sequence of examples an algorithm paradigm for solving NP- hard problems on graphs restricted to partial graphs of k-trees and given with an embedding in a k-tree. Such algorithms, linear in the size of the graph but exponential or superexponential in k, exist for most NP-hard problems that have linear time algorithms for trees. The examples used are optimization problems involving independent sets, dominating sets, graph coloring, Hamiltonian circuits, network reliability and minimum vertex deletion forbidden subgraphs. The results generalize previous results for series-parallel graphs, bandwidth-constrained graphs, and non- serial dynamic programming.

Non deterministic polynomial optimization problems and their approximations

A Paz — 2007-10-03T03:19:48-00:00

Theoretical Computer Science, Vol. 15, No. 3. (1981), pp. 251-277.

A unified and general framework for the study of nondeterministic polynomial optimization problems (NPOP) is presented and some properties of NPOP's are investigated. A characterization of NPOP's with regard to their approximability properties is given by proving necessary and sufficient conditions for two approximability schemes. Known approximability results are shown to fit within the general frame developed in the paper. Finally NPOP's are classified and studied with regard to the possibility or impossibility of `reducing' certain types of NPOP's to other types in a sense specified in the text.

Nondeterministic Graph Searching: From Pathwidth to Treewidth

Fedor Fomin — 2007-10-01T05:06:58-00:00

Algorithmica

Abstract We introduce nondeterministic graph searching with a controlled amount of nondeterminism and show how this new tool can be used in algorithm design and combinatorial analysis applying to both pathwidth and treewidth. We prove equivalence between this game-theoretic approach and graph decompositions called q -branched tree decompositions, which can be interpreted as a parameterized version of tree decompositions. Path decomposition and (standard) tree decomposition are two extreme cases of q-branched tree decompositions. The equivalence between nondeterministic graph searching and q-branched tree decomposition enables us to design an exact (exponential time) algorithm computing q-branched treewidth for all q≥0, which is thus valid for both treewidth and pathwidth. This algorithm performs as fast as the best known exact algorithm for pathwidth. Conversely, this equivalence also enables us to design a lower bound on the amount of nondeterminism required to search a graph with the minimum number of searchers.

Parameterized Algorithmics: A Graph-Theoretic Approach

H Fernau — 2007-09-23T12:43:17-00:00

(2005)