Michael R. Fellows

MFCS Conference 2024 Conference Paper

Breaking a Graph into Connected Components with Small Dominating Sets

• Matthias Bentert
• Michael R. Fellows
• Petr A. Golovach
• Frances A. Rosamond
• Saket Saurabh 0001

We study DOMINATED CLUSTER DELETION. Therein, we are given an undirected graph G = (V, E) and integers k and d and the task is to find a set of at most k vertices such that removing these vertices results in a graph in which each connected component has a dominating set of size at most d. We also consider the special case where d is a constant. We show an almost complete tetrachotomy in terms of para-NP-hardness, containment in XP, containment in FPT, and admitting a polynomial kernel with respect to parameterizations that are a combination of k, d, c, and Δ, where c and Δ are the degeneracy and the maximum degree of the input graph, respectively. As a main contribution, we show that the problem can be solved in f(k, d) ⋅ n^O(d) time, that is, the problem is FPT when parameterized by k when d is a constant. This answers an open problem asked in a recent Dagstuhl seminar (23331). For the special case d = 1, we provide an algorithm with running time 2^𝒪(klog k) nm. Furthermore, we show that even for d = 1, the problem does not admit a polynomial kernel with respect to k + c.

ECAI Conference 2023 Conference Paper

On Solution Discovery via Reconfiguration

• Michael R. Fellows
• Mario Grobler
• Nicole Megow
• Amer E. Mouawad
• R. Vijayaragunathan
• Frances A. Rosamond
• Daniel Schmand
• Sebastian Siebertz

The dynamics of real-world applications and systems require efficient methods for improving infeasible solutions or restoring corrupted ones by making modifications to the current state of a system in a restricted way. We propose a new framework of solution discovery via reconfiguration for constructing a feasible solution for a given problem by executing a sequence of small modifications starting from a given state. Our framework integrates different aspects of classical local search, reoptimization, and combinatorial reconfiguration. We exemplify our framework on a multitude of fundamental combinatorial problems, namely VERTEX COVER, INDEPENDENT SET, DOMINATING SET, and COLORING. We study the classical as well as the parameterized complexity of the solution discovery variants of those problems and explore the boundary between tractable and intractable instances.

AIJ Journal 2022 Journal Article

Diversity of solutions: An exploration through the lens of fixed-parameter tractability theory

• Julien Baste
• Michael R. Fellows
• Lars Jaffke
• Tomáš Masařík
• Mateus de Oliveira Oliveira
• Geevarghese Philip
• Frances A. Rosamond

When modeling an application of practical relevance as an instance of a combinatorial problem X, we are often interested not merely in finding one optimal solution for that instance, but in finding a sufficiently diverse collection of good solutions. In this work we initiate a systematic study of diversity from the point of view of fixed-parameter tractability theory. First, we consider an intuitive notion of diversity of a collection of solutions which suits a large variety of combinatorial problems of practical interest. We then present an algorithmic framework which –automatically– converts a tree-decomposition-based dynamic programming algorithm for a given combinatorial problem X into a dynamic programming algorithm for the diverse version of X. Surprisingly, our algorithm has a polynomial dependence on the diversity parameter.

IJCAI Conference 2020 Conference Paper

Diversity of Solutions: An Exploration Through the Lens of Fixed-Parameter Tractability Theory

• Julien Baste
• Michael R. Fellows
• Lars Jaffke
• Tomáš Masařík
• Mateus de Oliveira Oliveira
• Geevarghese Philip
• Frances A. Rosamond

When modeling an application of practical relevance as an instance of a combinatorial problem X, we are often interested not merely in finding one optimal solution for that instance, but in finding a sufficiently diverse collection of good solutions. In this work we initiate a systematic study of diversity from the point of view of fixed-parameter tractability theory. We consider an intuitive notion of diversity of a collection of solutions which suits a large variety of combinatorial problems of practical interest. Our main contribution is an algorithmic framework which --automatically-- converts a tree-decomposition-based dynamic programming algorithm for a given combinatorial problem X into a dynamic programming algorithm for the diverse version of X. Surprisingly, our algorithm has a polynomial dependence on the diversity parameter.

TCS Journal 2015 Journal Article

On the parameterized complexity of dynamic problems

• Faisal N. Abu-Khzam
• Judith Egan
• Michael R. Fellows
• Frances A. Rosamond
• Peter Shaw

In a dynamic version of a (base) problem X it is assumed that some solution to an instance of X is no longer feasible due to changes made to the original instance, and it is required that a new feasible solution be obtained from what “remained” from the original solution at a minimal cost. In the parameterized version of such a problem, the changes made to an instance are bounded by an edit-parameter, while the cost of reconstructing a solution is bounded by some increment-parameter. Capitalizing on the recent initial work of Downey et al. on the Dynamic Dominating Set problem, we launch a study of the dynamic versions of a number of problems including Vertex Cover, Maximum Clique, Connected Vertex Cover and Connected Dominating Set. In particular, we show that Dynamic Vertex Cover is W [ 1 ] -hard, and the connected versions of both Dynamic Vertex Cover and Dynamic Dominating Set become fixed-parameter tractable with respect to the edit-parameter while they remain W [ 2 ] -hard with respect to the increment-parameter. Moreover, we show that Dynamic Independent Dominating Set is W [ 2 ] -hard with respect to the edit-parameter. We introduce the reoptimization parameter, which bounds the difference between the cardinalities of initial and target solutions. We prove that, while Dynamic Maximum Clique is fixed-parameter tractable with respect to the edit-parameter, it becomes W [ 1 ] -hard if the increment-parameter is replaced with the reoptimization parameter. Finally, we establish that Dynamic Dominating Set becomes W [ 2 ] -hard when the target solution is required not to be larger than the initial one, even if the edit parameter is exactly one.

TCS Journal 2015 Journal Article

Tractability and hardness of flood-filling games on trees

• Michael R. Fellows
• Uéverton dos Santos Souza
• Fábio Protti
• Maise Dantas da Silva

This work presents new results on flood-filling games, Flood-It and Free-Flood-It, in which the player aims to make the board monochromatic with a minimum number of flooding moves. A flooding move consists of changing the color of the monochromatic component containing a vertex p (the pivot of the move). These games are originally played on grids; however, when played on trees, we have interesting applications and significant effects on problem complexity. In this paper, a complete mapping of the complexity of flood-filling games on trees is made, charting the consequences of single and aggregate parameterizations by: number of colors, number of moves, maximum distance from the pivot, number of occurrences of a color, number of leaves, and difference between number of moves and number of colors. We show that Flood-It on trees and Restricted Shortest Common Supersequence (RSCS) are analogous problems, in the sense that they can be translated from one to another, preserving complexity issues; this implies interesting FPT and W[1]-hard cases to Flood-It. Restricting attention to phylogenetic colored trees (where each color occurs at most once in any root-leaf path, in order to model phylogenetic sequences), we also show some impressive NP-hard and FPT results for both games. In addition, we prove that Flood-It and Free-Flood-It remain NP-hard when played on 3-colored trees, which closes an open question posed by Fleischer and Woeginger. Finally, we present a general framework for reducibility from Flood-It to Free-Flood-It; some NP-hard cases for Free-Flood-It can be derived using this approach.

I&C Journal 2011 Journal Article

On the complexity of some colorful problems parameterized by treewidth

• Michael R. Fellows
• Fedor V. Fomin
• Daniel Lokshtanov
• Frances Rosamond
• Saket Saurabh
• Stefan Szeider
• Carsten Thomassen

In this paper, we study the complexity of several coloring problems on graphs, parameterized by the treewidth of the graph. 1. The List Coloring problem takes as input a graph G, together with an assignment to each vertex v of a set of colors C v. The problem is to determine whether it is possible to choose a color for vertex v from the set of permitted colors C v, for each vertex, so that the obtained coloring of G is proper. We show that this problem is W [ 1 ] -hard, parameterized by the treewidth of G. The closely related Precoloring Extension problem is also shown to be W [ 1 ] -hard, parameterized by treewidth. 2. An equitable coloring of a graph G is a proper coloring of the vertices where the numbers of vertices having any two distinct colors differs by at most one. We show that the problem is hard for W [ 1 ], parameterized by the treewidth plus the number of colors. We also show that a list-based variation, List Equitable Coloring is W [ 1 ] -hard for forests, parameterized by the number of colors on the lists. 3. The list chromatic number χ l ( G ) of a graph G is defined to be the smallest positive integer r, such that for every assignment to the vertices v of G, of a list L v of colors, where each list has length at least r, there is a choice of one color from each vertex list L v yielding a proper coloring of G. We show that the problem of determining whether χ l ( G ) ⩽ r, the List Chromatic Number problem, is solvable in linear time on graphs of constant treewidth.

TCS Journal 2010 Journal Article

Clustering with partial information

• Hans L. Bodlaender
• Michael R. Fellows
• Pinar Heggernes
• Federico Mancini
• Charis Papadopoulos
• Frances Rosamond

The Correlation Clustering problem, also known as the Cluster Editing problem, seeks to edit a given graph by adding and deleting edges to obtain a collection of vertex-disjoint cliques, such that the editing cost is minimized. The Edge Clique Partitioning problem seeks to partition the edges of a given graph into edge-disjoint cliques, such that the number of cliques is minimized. Both problems are known to be NP-hard, and they have been previously studied with respect to approximation and fixed-parameter tractability. In this paper we study these two problems in a more general setting that we term fuzzy graphs, where the input graphs may have missing information, meaning that whether or not there is an edge between some pairs of vertices of the input graph can be undecided. For fuzzy graphs the Correlation Clustering and Edge Clique Partitioning problems have previously been studied only with respect to approximation. Here we give parameterized algorithms based on kernelization for both problems. We prove that the Correlation Clustering problem is fixed-parameter tractable on fuzzy graphs when parameterized by ( k, r ), where k is the editing cost and r is the minimum number of vertices required to cover the undecided edges. In particular we show that it has a polynomial-time reduction to a problem kernel on O ( k 2 + r ) vertices. We provide an analogous result for the Edge Clique Partitioning problem on fuzzy graphs. Using ( k, r ) as parameters, where k bounds the size of the partition, and r is the minimum number of vertices required to cover the undecided edges, we describe a polynomial-time kernelization to a problem kernel on O ( k 4 ⋅ 3 r ) vertices. This implies fixed-parameter tractability for this parameterization. Furthermore we also show that parameterizing only by the number of cliques k, is not enough to obtain fixed-parameter tractability. The problem remains, in fact, NP-hard for each fixed k > 2.

IJCAI Conference 2009 Conference Paper

• Michael R. Fellows
• Frances A. Rosamond
• Fedor V. Fomin
• Daniel Lokshtanov
• Saket Saurabh
• Yngve Villanger

Many local search algorithms are based on searching in the k-exchange neighborhood. This is the set of solutions that can be obtained from the current solution by exchanging at most k elements. As a rule of thumb, the larger k is, the better are the chances of finding an improved solution. However, for inputs of size n, a naı̈ve brute-force search of the k-exchange neighborhood requires nO(k) time, which is not practical even for very small values of k. We show that for several classes of sparse graphs, like planar graphs, graphs of bounded vertex degree and graphs excluding some fixed graph as a minor, an improved solution in the k-exchange neighborhood for many problems can be found much more efficiently. Our algorithms run in time O(τ(k) · nc ), where τ is a function depending on k only and c is a constant independent of k. We demonstrate the applicability of this approach on different problems like r-CENTER, VERTEX COVER, ODD CYCLE TRANSVERSAL, MAX-CUT, and MIN-BISECTION. In particular, on planar graphs, all our algorithms searching for a klocal improvement run in time O(2O(k) ·n2 ), which is polynomial for k = O(log n). We also complement the algorithms with complexity results indicating that—brute force search is unavoidable—in more general classes of sparse graphs.

MFCS Conference 2009 Conference Paper

A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems

• Michael R. Fellows
• Jiong Guo
• Hannes Moser
• Rolf Niedermeier

Abstract We investigate the computational complexity of a general “compression task” centrally occurring in the recently developed technique of iterative compression for exactly solving NP-hard minimization problems. The core issue (particularly but not only motivated by iterative compression) is to determine the computational complexity of, given an already inclusion-minimal solution for an underlying (typically NP-hard) vertex deletion problem in graphs, to find a better disjoint solution. The complexity of this task is so far lacking a systematic study. We consider a large class of vertex deletion problems on undirected graphs and show that, except for few cases which are polynomial-time solvable, the others are NP-complete. This class includes problems such as Vertex Cover (here the corresponding compression task is decidable in polynomial time) or Undirected Feedback Vertex Set (here the corresponding compression task is NP-complete).

TCS Journal 2009 Journal Article

Fixed-parameter algorithms for Kemeny rankings

• Nadja Betzler
• Michael R. Fellows
• Jiong Guo
• Rolf Niedermeier
• Frances A. Rosamond

The computation of Kemeny rankings is central to many applications in the context of rank aggregation. Given a set of permutations (votes) over a set of candidates, one searches for a “consensus permutation” that is “closest” to the given set of permutations. Unfortunately, the problem is NP-hard. We provide a broad study of the parameterized complexity for computing optimal Kemeny rankings. Besides the three obvious parameters “number of votes”, “number of candidates”, and solution size (called Kemeny score), we consider further structural parameterizations. More specifically, we show that the Kemeny score (and a corresponding Kemeny ranking) of an election can be computed efficiently whenever the average pairwise distance between two input votes is not too large. In other words, Kemeny Score is fixed-parameter tractable with respect to the parameter “average pairwise Kendall–Tau distance d a ”. We describe a fixed-parameter algorithm with running time 1 6 ⌈ d a ⌉ ⋅ poly. Moreover, we extend our studies to the parameters “maximum range” and “average range” of positions a candidate takes in the input votes. Whereas Kemeny Score remains fixed-parameter tractable with respect to the parameter “maximum range”, it becomes NP-complete in the case of an average range of two. This excludes fixed-parameter tractability with respect to the parameter “average range” unless P=NP. Finally, we extend some of our results to votes with ties and incomplete votes, where in both cases one no longer has permutations as input.

AAMAS Conference 2009 Conference Paper

How Similarity Helps to Efficiently Compute Kemeny Rankings

• Nadja Betzler
• Michael R. Fellows
• Jiong Guo
• Rolf Niedermeier
• Frances A. Rosamond

The computation of Kemeny rankings is central to many applications in the context of rank aggregation. Unfortunately, the problem is NP-hard. We show that the Kemeny score (and a corresponding Kemeny ranking) of an election can be computed efficiently whenever the average pairwise distance between two input votes is not too large. In other words, Kemeny Score is fixed-parameter tractable with respect to the parameter “average pairwise Kendall-Tau distance da”. We describe a fixed-parameter algorithm with running time 16 da · poly. Moreover, we extend our studies to the parameters “maximum range” and “average range” of positions a candidate takes in the input votes. Whereas Kemeny Score remains fixed-parameter tractable with respect to the parameter “maximum range”, it becomes NPcomplete in case of an average range value of two. This excludes fixed-parameter tractability with respect to the parameter “average range” unless P=NP.

TCS Journal 2009 Journal Article

On the parameterized complexity of multiple-interval graph problems

• Michael R. Fellows
• Danny Hermelin
• Frances Rosamond
• Stéphane Vialette

Multiple-interval graphs are a natural generalization of interval graphs where each vertex may have more than one interval associated with it. Many applications of interval graphs also generalize to multiple-interval graphs, often allowing for more robustness in the modeling of the specific application. With this motivation in mind, a recent systematic study of optimization problems in multiple-interval graphs was initiated. In this sequel, we study multiple-interval graph problems from the perspective of parameterized complexity. The problems under consideration are k -Independent Set, k -Dominating Set, and k -Clique, which are all known to be W[1]-hard for general graphs, and NP-complete for multiple-interval graphs. We prove that k -Clique is in FPT, while k -Independent Set and k -Dominating Set are both W[1]-hard. We also prove that k -Independent Dominating Set, a hybrid of the two above problems, is also W[1]-hard. Our hardness results hold even when each vertex is associated with at most two intervals, and all intervals have unit length. Furthermore, as an interesting byproduct of our hardness results, we develop a useful technique for showing W[1]-hardness via a reduction from the k -Multicolored Clique problem, a variant of k -Clique. We believe this technique has interest in its own right, as it should help in simplifying W[1]-hardness results which are notoriously hard to construct and technically tedious.

MFCS Conference 2008 Conference Paper

Clustering with Partial Information

• Hans L. Bodlaender
• Michael R. Fellows
• Pinar Heggernes
• Federico Mancini 0001
• Charis Papadopoulos
• Frances A. Rosamond

Abstract The Correlation Clustering problem, also known as the Cluster Editing problem, seeks to edit a given graph by adding and deleting edges to obtain a collection of vertex-disjoint cliques, such that the editing cost is minimized. The Edge Clique Partitioning problem seeks to partition the edges of a given graph into edge-disjoint cliques, such that the number of cliques is minimized. Both problems are known to be NP-hard, and they have been previously studied with respect to approximation and fixed parameter tractability. In this paper we study these two problems in a more general setting that we term fuzzy graphs, where the input graphs may have missing information, meaning that whether or not there is an edge between some pairs of vertices of the input graph can be undecided. For fuzzy graphs the Correlation Clustering and Edge Clique Partitioning problems have previously been studied only with respect to approximation. Here we give parameterized algorithms based on kernelization for both problems. We prove that the Correlation Clustering problem is fixed-parameter tractable on fuzzy graphs when parameterized by ( k, r ), where k is the editing cost and r is the minimum number of vertices required to cover the undecided edges. In particular we show that it has a polynomial-time reduction to a problem kernel on O ( k 2 + r ) vertices. We provide an analogous result for the Edge Clique Partitioning problem on fuzzy graphs. Using ( k, r ) as parameters, where k bounds the size of the partition, and r is the minimum number of vertices required to cover the undecided edges, we describe a polynomial-time kernelization to a problem kernel on O ( k 4 ·3 r ) vertices. This implies fixed-parameter tractability for this parameterization. Furthermore we also show that parameterizing only by the number of cliques k, is not enough to obtain fixed-parameter tractability. The problem remains, in fact, NP-hard for each fixed k > 2.

STOC Conference 2006 Conference Paper

Clique-width minimization is NP-hard

• Michael R. Fellows
• Frances A. Rosamond
• Udi Rotics
• Stefan Szeider

Clique-width is a graph parameter that measures in a certain sense the complexity of a graph. Hard graph problems (e.g., problems expressible in Monadic Second Order Logic with second-order quantification on vertex sets, that includes NP-hard problems) can be solved efficiently for graphs of small clique-width. It is widely believed that determining the clique-width of a graph is NP-hard; in spite of considerable efforts, no NP-hardness proof has been found so far. We give the first hardness proof. We show that the clique-width of a given graph cannot be absolutely approximated in polynomial time unless P=NP. We also show that, given a graph G and an integer k, deciding whether the clique-width of G is at most k is NPhy complete. This solves a problem that has been open since the introduction of clique-width in the early 1990s.

TCS Journal 2006 Journal Article

On finding short resolution refutations and small unsatisfiable subsets

• Michael R. Fellows
• Stefan Szeider
• Graham Wrightson

We consider the parameterized problems of whether a given set of clauses can be refuted within k resolution steps, and whether a given set of clauses contains an unsatisfiable subset of size at most k. We show that both problems are complete for the class W [ 1 ], the first level of the W-hierarchy of fixed-parameter intractable problems. Our results remain true if restricted to 3-SAT instances and/or to various restricted versions of resolution including tree-like resolution, input resolution, and read-once resolution. Applying a metatheorem of Frick and Grohe, we show that, restricted to classes of sets of clauses of locally bounded treewidth, the considered problems are fixed-parameter tractable. For example, the problems are fixed-parameter tractable for planar CNF formulas.

TCS Journal 2003 Journal Article

On the parametric complexity of schedules to minimize tardy tasks

• Michael R. Fellows
• Catherine McCartin

Given a set T of tasks, each of unit length and having an individual deadline d(t)∈Z +, a set of precedence constraints on T, and a positive integer k⩽|T|, we can ask “Is there a one-processor schedule for T that obeys the precedence constraints and contains no more than k late tasks? ” This is a well-known NP-complete problem. We might also inquire “Is there a one-processor schedule for T that obeys the precedence constraints and contains at least k tasks that are on time i. e. no more than |T|−k late tasks? ” Within the framework of classical complexity theory, these two questions are merely different instances of the same problem. Within the recently developed framework of parameterized complexity theory, however, they give rise to two separate problems that may be studied independently of one another. We investigate these problems from the parameterized point of view. We show that, in the general case, both these problems are hard for the parameterized complexity class W[1]. In contrast, in the case where the set of precedence constraints can be modelled by a partial order of bounded width, we show that both these problems are fixed parameter tractable.

MFCS Conference 2003 Conference Paper

Starting with Nondeterminism: The Systematic Derivation of Linear-Time Graph Layout Algorithms

• Hans L. Bodlaender
• Michael R. Fellows
• Dimitrios M. Thilikos

Abstract This paper investigates algorithms for some related graph parameters. Each asks for a linear ordering of the vertices of the graph (or can be formulated as such), and there are constructive linear time algorithms for the fixed parameter versions of the problems. Examples are cutwidth, pathwidth, and directed or weighted variants of these. However, these algorithms have complicated technical details. This paper attempts to present these algorithms in a different more easily accessible manner, by showing that the algorithms can be obtained by a stepwise modification of a trivial hypothetical non-deterministic algorithm. The methodology is applied for a generalisation of the cutwidth problem to weighted mixed graphs. As a consequence, we obtain new algorithmic results for various problems like modified cutwidth, and rederive known results for other related problems with simpler proofs.

MFCS Conference 2001 Conference Paper

Refined Search Tree Technique for DOMINATING SET on Planar Graphs

• Jochen Alber
• Hongbing Fan
• Michael R. Fellows
• Henning Fernau
• Rolf Niedermeier
• Frances A. Rosamond
• Ulrike Stege

Abstract We establish refined search tree techniques for the parameterized DOMINATING SET problem on planar graphs. We derive a fixed parameter algorithm with running time O(8 k n), where k is the size of the dominating set and n is the number of vertices in the graph. For our search tree, we firstly provide a set of reduction rules. Secondly, we prove an intricate branching theorem based on the Euler formula. In addition, we give an example graph showing that the bound of the branching theorem is optimal with respect to our reduction rules. Our final algorithm is very easy (to implement); its analysis, however, is involved.

TCS Journal 2000 Journal Article

On computing graph minor obstruction sets

• Kevin Cattell
• Michael J. Dinneen
• Rodney G. Downey
• Michael R. Fellows
• Michael A. Langston

The Graph Minor Theorem of Robertson and Seymour establishes nonconstructively that many natural graph properties are characterized by a finite set of forbidden substructures, the obstructions for the property. We prove several general theorems regarding the computation of obstruction sets from other information about a family of graphs. The methods can be adapted to other partial orders on graphs, such as the immersion and topological orders. The algorithms are in some cases practical and have been implemented. Two new technical ideas are introduced. The first is a method of computing a stopping signal for search spaces of increasing pathwidth. This allows obstruction sets to be computed without the necessity of a prior bound on maximum obstruction width. The second idea is that of a second order congruence for a graph property. This is an equivalence relation defined on finite sets of graphs that generalizes the recognizability congruence that is defined on single graphs. It is shown that the obstructions for a graph ideal can be effectively computed from an oracle for the canonical second-order congruence for the ideal and a membership oracle for the ideal. It is shown that the obstruction set for a union F = F 1 ∪ F 2 of minor ideals can be computed from the obstruction sets for F 1 and F 2 if there is at least one tree that does not belong to the intersection of F 1 and F 2. As a corollary, it is shown that the set of intertwines of an arbitrary graph and a tree are effectively computable.

TCS Journal 2000 Journal Article

The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs

• Hans L. Bodlaender
• Michael R. Fellows
• Michael T. Hallett
• H.Todd Wareham
• Tandy J. Warnow

In this paper, we consider the complexity of a number of combinatorial problems; namely, Intervalizing Colored Graphs (DNA physical mapping), Triangulating Colored Graphs (perfect phylogeny), (Directed) (Modified) Colored Cutwidth, Feasible Register Assignment and Module Allocation for graphs of bounded pathwidth. Each of these problems has as a characteristic a uniform upper bound on the tree or path width of the graphs in “yes”-instances. For all of these problems with the exceptions of Feasible Register Assignment and Module Allocation, a vertex or edge coloring is given as part of the input. Our main results are that the parameterized variant of each of the considered problems is hard for the complexity classes W[t] for all t∈ N. We also show that Intervalizing Colored Graphs, Triangulating Colored Graphs, and Colored Cutwidth are NP-Complete.

TCS Journal 1998 Journal Article

Parameterized circuit complexity and the W hierarchy

• Rodney G. Downey
• Michael R. Fellows
• Kenneth W. Regan

A parameterized problem 〈L, k〉 belongs to W[t] if there exists k′ computed from k such that 〈L, k〉 reduces to the weight-k′ satisfiability problem for weft-t circuits. We relate the fundamental question of whether the W[t] hierarchy is proper to parameterized problems for constant-depth circuits. We define classes G[t] as the analogues of AC0 depth-t for parameterized problems, and N[t] by weight-k′ existential quantification on G[t], by analogy with NP = ∃ · P. We prove that for each t, W[t] equals the closure under fixed-parameter reductions of N[t]. Then we prove, using Sipser's results on the AC0 depth-t hierarchy, that both the G[t] and the N[t] hierarchies are proper. If this separation holds up under parameterized reductions, then the W[t] hierarchy is proper. We also investigate the hierarchy H[t] defined by alternating quantification over G[t]. By trading weft for quantifiers we show that H[t] coincides with H[1]. We also consider the complexity of unique solutions, and show a randomized reduction from W[t] to Unique W[t].

TCS Journal 1998 Journal Article

Threshold dominating sets and an improved characterization of W[2]

• Rodney G. Downey
• Michael R. Fellows

The threshold dominating set problem is that of determining for a graph G = (V, E) whether there is a subset V′ ⊆ V of size k, such that for each vertex v ϵ V there are at least r elements of the closed neighborhood N[v] that belong to V′. We consider the complexity of the problem parameterized by the pair (k, r). It is trivial to observe that this is hard for W[2]. It can also be easily shown to belong to a natural extension W∗[2] of W[2] defined in terms of circuit families of depth bounded by a function of the parameter. We prove membership in W[2] and thus W[2]-completeness. Using this as a starting point, we prove that W∗[2] = W[2].

TCS Journal 1995 Journal Article

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

• Rod G. Downey
• Michael R. Fellows

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 ⩾ 2. Our main result shows that INDEPENDENT SET is complete for W[1].

TCS Journal 1995 Journal Article

The parameterized complexity of sequence alignment and consensus

• Hans L. Bodlaender
• Rodney G. Downey
• Michael R. Fellows
• Harold T. Wareham

The longest common subsequence 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 ƒ(k) · nα where α 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 longest common subsequence (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.

STOC Conference 1994 Conference Paper

Beyond NP-completeness for problems of bounded width: hardness for the W hierarchy

• Hans L. Bodlaender
• Michael R. Fellows
• Michael T. Hallett

FOCS Conference 1989 Conference Paper

An Analogue of the Myhill-Nerode Theorem and Its Use in Computing Finite-Basis Characterizations (Extended Abstract)

• Michael R. Fellows
• Michael A. Langston

A theorem that is a graph-theoretic analog of the Myhill-Nerode characterization of regular languages is proved. The theorem is used to establish that for many applications obstruction sets are computable by known algorithms. The focus is exclusively on what is computable (by a known algorithm) in principle, as opposed to what is computable in practice. >

STOC Conference 1989 Conference Paper

On Search, Decision and the Efficiency of Polynomial-Time Algorithms (Extended Abstract)

• Michael R. Fellows
• Michael A. Langston

FOCS Conference 1989 Conference Paper

On the Complexity of Fixed Parameter Problems (Extended Abstract)

• Karl R. Abrahamson
• John A. Ellis
• Michael R. Fellows
• Manuel E. Mata

The authors address the question of why some fixed-parameter problem families solvable in polynomial time seem to be harder than others with respect to fixed-parameter tractability: whether there is a constant alpha such that all problems in the family are solvable in time O(n/sup alpha /). The question is modeled by considering a class of polynomially indexed relations. The main results show that (1) this setting supports notions of completeness that can be used to explain the apparent hardness of certain problems with respect to fixed-parameter tractability, and (2) some natural problems are complete. >