(Subject List)
Books  
[1] 
Casey, N., and Fellows, M. R.
This is MegaMathematics!
Los Alamos National Labs, 1992.
Available at http://www.c3.lanl..gov/ captors/megamath. See also
www.ccs3.lanl.gov/megamath/write.html.
[ bib ]
A collection of classroom lessons in mathematics and computer science. Each lesson contains extensive background material that assumes that the topic of the lesson is new to the teacher. Topics include map coloring, graph theory, knot theory, finite state machines, algorithms, logic and infinity.

[2] 
Bell, T., Fellows, M. R., and Witten, I.
Computer Science Unplugged ... offline activities and games for
all ages: Teacher Edition.
Computer Science Unplugged, 1996.
There are currently two versions of the book. The "Teachers'
Edition" which is aimed at people with less of a technical background. It
has 12 activities, and a lot more illustrations and handouts. Both books are
available in Download from http://www.lulu.com.
[ bib ]
Many important topics in computer science can be taught without using computers at all. This series of activities unplugs computer science by providing offline activities, games and puzzles that are suitable for people of all ages and backgrounds, but especially for elementary school children. The activities cover a wide range of topics, from algorithms to artificial intelligence, from binary numbers to boolean circuits, compression to cryptography.

[3] 
Fellows, M. R., Bell, T., and Witten, I.
Computer Science Unplugged ... offline activities and games for
all ages: Original Activities Book.
Computer Science Unplugged, 1996.
[ bib ]
There are currently two versions of the book. This original edition is aimed for people with some technical interest. This 232page book includes photocopy masters and detailed explanations and 20 activities. Both books have been translated into about a dozen languages. Both books are available in Download from http://www.lulu.com.

[4]  Downey, R. G., and Fellows, M. R. Parameterized Complexity. SpringerVerlag, 1999. 530 pp. [ bib ] 
Graph Minors and WellQuasiOrdering  
[5]  Fellows, M. R., Hermelin, D., and Rosamond, F. A. Wellquasiordering bounded treewidth graphs. In Proceedings of International Workshop on Parameterized and Exact Computation, IWPEC'09 (2009), Lecture Notes in Computer Science, SpringerVerlag. To Appear. [ bib  link ] 
[6]  Cattell, K., Dinneen, M. J., and Fellows, M. R. Forbidden minors to graphs with small feedback sets. Discrete Mathematics 230, 13 (2001), 215252. [ bib  link ] 
[7]  Cattell, K., Dinneen, M. J., Downey, R. G., and Fellows, M. R. On computing graph minor obstruction sets. Theoretical Computer Science 233, 1 (2000), 107127. [ bib  link ] 
[8] 
Courcelle, B., Downey, R. G., and Fellows, M. R.
A note on the computability of graph minor obstruction sets for
monadic second order ideals.
Journal of Universal Computer Science 3, 11 (1997), 11941198.
[ bib 
link ]
The major results of Robertson and Seymour on graph wellquasiordering establish nonconstructively that many natural graph properties that constitute ideals in the minor or immersion orders are characterized by a finite set of forbidden substructures termed the obstructions for the property. This raises the question of what general kinds of information about an ideal are sufficient, or insufficient, to allow the obstruction set for the ideal to be effectively computed. It has been previously shown that it is not possible to compute the obstruction set for an ideal from a description of a Turing machine that recognizes the ideal. This result is significantly strengthened in the case of the minor ordering. It is shown that the obstruction set for an ideal in the minor order cannot be computed from a description of the ideal in monadic secondorder logic.

[9] 
Cattell, K., Dinneen, M. J., and Fellows, M. R.
A simple lineartime algorithm for finding pathdecompositions of
small width.
Information Processing Letters 57, 4 (1996), 197203.
[ bib 
link ]
We describe a simple algorithm running in linear time for each fixed constant k, that either establishes that the pathwidth of a graph G is greater than k, or finds a pathdecomposition of G of width at most O(2^{k}). This provides a simple proof of the result by Bodlaender that many families of graphs of bounded pathwidth can be recognized in linear time.

[10]  Cattell, K., Dinneen, M. J., and Fellows, M. R. Forbidden minors to graphs with small feedback sets. Tech. rep., 1996. Preprint. Journal publication is “Discrete Mathematics” (2000),. [ bib  link ] 
[11] 
Fellows, M., Kratochvil, J., Middendorf, M., and Pfeiffer, F.
The complexity of induced minors and related problems.
Algorithmica 13, 3 (1995), 266282.
[ bib 
link ]
The computational complexity of a number of problems concerning induced structures in graphs is studied, and compared with the complexity of corresponding problems concerning noninduced structures. The effect on these problems of restricting the input to planar graphs is also considered. The principal results include: (1) Induced maximum matching and induced directed path are NPcomplete for planar graphs, (2) for every fixed graph H, induced Hminor testing can be accomplished for planar graphs O(n), and (3) there are graphs H for which induced Hminor testing is NPcomplete for unrestricted input. Some useful structural theorems concerning induced minors are presented, including a bound on the treewidth of planar graphs that exclude a planar induced minor.

[12] 
Cattell, K., Dinneen, M. J., and Fellows, M. R.
Obstructions to within a few vertices or edges of acyclic.
In Proceedings of the 4th International Workshop on Algorithms
and Data Structures, WADS'95 (1995), S. G. Akl, F. Dehne, J.R. Sack, and
N. Santoro, Eds., vol. 955 of Lecture Notes in Computer Science,
SpringerVerlag, pp. 415427.
[ bib 
link ]
Finite obstruction sets for lower ideals in the minor order are guaranteed to exist by the Graph Minor Theorem. It has been known for several years that, in principle, obstruction sets can be mechanically computed for most natural lower ideals. In this paper, we describe a generalpurpose method for finding obstructions by using a bounded treewidth (or pathwidth) search. We illustrate this approach by characterizing certain families of cyclecover graphs based on the two wellknown problems: kFeedback Vertex Set and kFeedback Edge Set. Our search is based on a number of algorithmic strategies by which large constants can be mitigated, including a randomized strategy for obtaining proofs of minimality. 1 Introduction One of the most famous results in graph theory is the characterization of planar graphs due to Kuratowski: a graph is planar if and only if it does not contain either of K 3;3 or K 5 as a minor.

[13]  Fellows, M. R., and Langston, M. A. On search, decision and the efficiency of polynomialtime algorithms. Journal of Computer and System Sciences (1994), 769779. [ bib  link ] 
[14]  Abrahamson, K. R., and Fellows, M. R. Finite automata, bounded treewidth and wellquasiordering. In Proceedings of the Joint Summer Research Conference on Graph Minors: Graph Structure Theory, Seattle, June, 1991 (1993), N. Robertson and P. Seymour, Eds., vol. 147 of Contemporary Mathematics, American Mathematical Society, pp. 539564. [ bib ] 
[15]  Fellows, M. R., and Langston, M. A. On wellpartialorder theory and its application to combinatorial problems of VLSI design. SIAM Journal on Discrete Mathematics 5, 1 (1992), 117126. [ bib ] 
[16]  Fellows, M. R. The RobertsonSeymour theorems: A survey of applications. In CMGA: Graphs and Algorithms: Contemporary Mathematics (1989), vol. 89, AMS, pp. 118. [ bib ] 
[17]  Brown, D. J., Fellows, M. R., and Langston, M. A. Polynomialtime selfreducibility: Theoretical motivations and practical results. International Journal of Computer Mathematics 31 (1989), 19. [ bib ] 
[18]  Fellows, M. R., and Stueckle, S. The immersion order, forbidden subgraphs and the complexity of network integrity. Journal of Combinatorial Mathematics and Combinatorial Computing 6 (1989), 2332. [ bib ] 
[19] 
Fellows, M., and Langston, M.
An analogue of the MyhillNerode theorem and its use in computing
finitebasis characterizations.
In Proceedings of the 30th Annual IEEE Symposium on Foundations
of Computer Science, FOCS'89 (1989), IEEE Computer Society Press,
pp. 520525.
[ bib ]
A theorem is proved that is a graphtheoretic analog of the MyhillNerode characterization of regular languages. 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.

[20]  Fellows, M., Kinnersley, N., and Langston, M. Finitebasis theorems and a computationintegrated approach to obstruction set isolation. In Proceedings of the Third Conference on Computers and Mathematics (1989), E. Kaltofen and S. M. Watt, Eds., SpringerVerlag, pp. 3745. [ bib ] 
[21]  Fellows, M. R., and Langston, M. A. Nonconstructive tools for proving polynomialtime decidability. Journal of the ACM 35, 3 (1988), 727739. [ bib  link ] 
[22]  Fellows, M. R., and Langston, M. A. Layout permutation problems and wellpartiallyordered sets. In Proceedings of the fifth MIT conference on Advanced research in VLSI (Cambridge, MA, USA, 1988), MIT Press, pp. 315327. [ bib ] 
[23]  Fellows, M. R., and Langston, M. A. Fast selfreduction algorithms for combinatorial problems of VLSI design. In Proceedings of the 3rd Aegean Workshop on Computing: VLSI Algorithms and Architectures, AWOC'88. Corfu, Greece (1988), J. H. Reif, Ed., vol. 319 of Lecture Notes in Computer Science, SpringerVerlag, pp. 278287. [ bib ] 
[24]  Fellows, M. R., and Langston, M. A. Nonconstructive advances in polynomialtime complexity. Information Processing Letters 26, 3 (1987), 157162. [ bib ] 
[25]  R. L. Bryant, N. G. Kinnersley, M. R. F., and Langston, M. A. On finding obstruction sets and polynomialtime algorithms for gate matrix layout. In Proceedings of the 25th Allerton Conference on Communication, Control and Computing (1987), pp. 397398. [ bib ] 
Surveys about Parameterized Complexity  
[26]  Fellows, M. R., Fomin, F. V., and Gutin, G. Special Issue on Parameterized Complexity. Discrete Optimization (2010). To Appear. [ bib ] 
[27]  Fellows, M. R. The complexity ecology of parameters: Some new developments and research directions. In Proceedings of IWOCA (2009), Lecture Notes in Computer Science, SpringerVerlag. To Appear. [ bib  link ] 
[28]  Downey, R., Fellows, M., and Langston, M. The Computer Journal Special Issue on Parameterized Complexity: Foreword by the Guest Editors. The Computer Journal 51, 1 (2008), 16. The Computer Journal published a twoissue special on Parameterized Complexity that includes 15 survey articles, as well as an Introduction and Overview. The issues are Volume 51, 2008, Issue 1 and Issue 3. [ bib  link ] 
[29]  Bodlaender, H. L., Demaine, E. D., Fellows, M. R., Guo, J., Hermelin, D., Lokshtanov, D., Müller, M., Venkatesh Raman, J. v. R., and Rosamond, F. A. Open problems in parameterized and exact computation from iwpec 2008. Tech. Rep. UUCS2008017, Department of Information and Computing Sciences, Utrecht University, 2008. [ bib  link ] 
[30]  Fellows, M. R., and Rosamond, F. A. The complexity ecology of parameters: An illustration using bounded max leaf number. In Proceedings of Computation and Logic in the Real World, Third Conference on Computability in Europe, CiE, Siena, Italy (2007), S. B. Cooper, B. Löwe, and A. Sorbi, Eds., vol. 4497 of Lecture Notes in Computer Science, Springer, pp. 268277. [ bib  link ] 
[31]  Fellows, M., and Rosamond, F. Why is P Not Equal to NP? In Computation and Logic in the Real World: Third Conference on Computability in Europe, CiE 2007: Local Proceedings (2007). [ bib  link ] 
[32]  Fellows, M. The lost continent of polynomial time. In Proceedings of IWPEC'06 (2006), vol. 4169 of Lecture Notes in Computer Science, SpringerVerlag, p. 276 – 277. [ bib  link ] 
[33]  Dehne, F. K., Fellows, M. R., Rosamond, F. A., and Shaw, P. Greedy localization, iterative compression, modeled crown reductions: New FPT techniques, an improved algorithm for set splitting, and a novel 2k kernelization for vertex cover. In Proceedings of Parameterized and Exact Computation, First International Workshop, IWPEC 2004, Bergen, Norway (2004), R. G. Downey, M. R. Fellows, and F. K. Dehne, Eds., vol. 3162 of Lecture Notes in Computer Science, Springer, pp. 271280. [ bib  link ] 
[34]  Fellows, M. R. A survey of FPT algorithm design techniques with an emphasis on recent advances and connections to practical computing. In Proceedings of 12th Annual European Symposium ESA, Bergen, Norway (2004), S. Albers and T. Radzik, Eds., vol. 3221 of Lecture Notes in Computer Science, SpringerVerlag, pp. 12. [ bib  link ] 
[35]  Chen, J., and Fellows, M. Foreword from the Guest Editors. Journal of Computer and System Sciences 67 (2003), 653654. Special Issue on Parameterized Complexity,. [ bib ] 
[36] 
Fellows, M. R.
Blowups, win/win's, and crown rules: Some new directions in FPT.
In Proceedings of the 29th International Workshop on
GraphTheoretic Concepts in Computer Science, WG'2003, Elspeet, The
Netherlands (2003), H. L. Bodlaender, Ed., vol. 2880 of Lecture Notes
in Computer Science, SpringerVerlag, pp. 112.
[ bib 
link ]
This survey reviews the basic notions of parameterized complexity, and describes some new approaches to designing FPT algorithms and problem reductions for graph problems.

[37]  Fellows, M. R. New directions and new challenges in algorithm design and complexity, parameterized. In Proceedings of Algorithms and Data Structures, 8th International Workshop WADS (2003), F. K. H. A. Dehne, J.R. Sack, and M. H. M. Smid, Eds., vol. 2748 of Lecture Notes in Computer Science, SpringerVerlag, pp. 505520. [ bib  link ] 
[38]  Fellows, M. R. Parameterized complexity: The main ideas and connections to practical computing. In Experimental Algorithmics (2002), R. Fleischer, B. M. E. Moret, and E. M. Schmidt, Eds., vol. 2547 of Lecture Notes in Computer Science, SpringerVerlag, pp. 5177. [ bib  link ] 
[39]  Fellows, M. R. Parameterized complexity: New developments and research frontiers. In Aspects of Complexity (2001), De Gruyter, pp. 5172. [ bib  link ] 
[40]  Fellows, M. R. Some new developments in parameterized complexity. In Proceedings of the 12th Australasian Workshop on Combinatorial Algorithms (2001), E. T. Baskoro, Ed., pp. 4344. [ bib  link ] 
[41]  Fellows, M. R. Parameterized complexity: Main ideas, connections to heuristics and research frontiers. In Proceedings of ISAAC (2001), vol. 2223 of Lecture Notes in Computer Science, SpringerVerlag, pp. 291307. [ bib  link ] 
[42] 
Downey, R. G., Fellows, M. R., and Stege, U.
Parameterized complexity: A framework for systematically
confronting computational intractability.
In Contemporary Trends in Discrete Mathematics: From DIMACS and
DIMATIA to the Future, vol. 49 of DIMACS Series in Discrete Mathematics
and Theoretical Computer Science. DIMACS, 1999, pp. 4999.
[ bib 
link ]
In this paper we give a programmatic overview of parameterized computational complexity in the broad context of the problem of coping with computational intractability. We give some examples of how fixedparameter tractability techniques can deliver practical algorithms in two different ways: (1) by providing useful exact algorithms for small parameter ranges, and (2) by providing guidance in the design of heuristic algorithms. In particular, we describe an improved FPT kernelization algorithm for Vertex Cover, a practical FPT algorithm for the Maximum Agreement Subtree (MAST) problem parameterized by the number of species to be deleted, and new general heuristics for these problems based on FPT techniques. In the course of making this overview, we also investigate some structural and hardness issues. We prove that an important naturally parameterized problem in artificial intelligence, STRIPS Planning (where the parameter is the size of the plan) is complete for W [1]. As a corollary, this implies that kStep Reachability for Petri Nets is complete for W [1]. We describe how the concept of treewidth can be applied to STRIPS Planning and other problems of logic to obtain FPT results. We describe a surprising structural result concerning the top end of the parameterized complexity hierarchy: the naturally parameterized Graph kColoring problem cannot be resolved with respect to XP either by showing membership in XP, or by showing hardness for XP without settling the P = NP question one way or the other.

[43]  Downey, R. G., Fellows, M. R., and Stege, U. Computational Tractability: A View from Mars. Tech. rep., 1999. [ bib  link ] 
[44]  Downey, R. G., and Fellows, M. R. Parameterized complexity after (almost) 10 years: Review and open questions. In Proceedings of Combinatorics, Computation and Logic, DMTCS'99 and CATS'99 (Singapore, 1999), vol. 21 of Australian Computer Science Communications, SpringerVerlag, pp. 133. [ bib  link ] 
[45]  Abrahamson, K., Downey, R. G., and Fellows, M. R. Fixedparameter tractability and completeness IV: On completeness for W[P] and PSPACE analogs. Annals of Pure and Applied Logic 73 (1995), 235276. [ bib  link ] 
[46] 
Cai, L., Chen, J., Downey, R., and Fellows, M.
On the structure of parameterized problems in NP.
Information and Computation 123, 1 (1995), 3849.
[ bib ]
Fixedparameter intractability of optimization problems in NP is studied based on computational models with limited nondeterminism. Strong evidence is shown that many NP optimization problems are not fixedparameter tractable and that the fixedparameter intractability hierarchy (the Whierarchy) does not collapse.

[47] 
Downey, R. G., and Fellows, M. R.
Parameterized computational feasibility.
In Proceedings of the Second Cornell Workshop on Feasible
Mathematics. Feasible Mathematics II (Boston, 1995), P. Clote and
J. Remmel, Eds., Birkhäuser, pp. 219244.
[ bib 
link ]
Many natural computational problems have input consisting of two or more parts. For example, the input might consist of a graph and a positive integer. For many natural problems we may view one of the inputs as a parameter and study how the complexity of the problem varies if the parameter is held fixed. For many applications of computational problems involving such a parameter, only a small range of parameter values is of practical significance, so that fixed parameter complexity is a natural concern. In studying the complexity of such problems, it is therefore important to have a framework in which we can make qualitative distinctions about the contribution of the parameter to the complexity of the problem. In this paper we survey one such framework for investigating parameterized computational complexity and present a number of new results for this theory.

[48]  Downey, R., and Fellows, M. R. Fixedparameter tractability and completeness II: Completeness for W[1]. Theoretical Computer Science A 141 (1995), 109131. Preliminary versions of some of the results of this paper were presented at the 21st Manitoba Conference on Numerical Mathematics and Computation, 1991. [ bib  link ] 
[49]  Downey, R., and Fellows, M. R. Fixedparameter tractability and completeness I: Basic theory. Siam Journal of Computing 24 (1995), 873921. Preliminary versions of some of the results of this paper were presented at the 21st Manitoba Conference on Numerical Mathematics and Computation, 1991. [ bib  link ] 
[50]  Abrahamson, K., Downey, R., and Fellows, M. R. Fixedparameter intractability II. In Proceedings of the 10th Symposium on Theoretical Aspects of Computer Sciences, STACS'93 (1993), vol. 665 of Lecture Notes in Computer Science, SpringerVerlag, pp. 374385. [ bib ] 
Bioinformatics  
[51]  Fellows, M. R., Fertin, G., Hermelin, D., and Vialette, S. Sharp tractability borderlines for finding connected motifs in vertexcolored graphs. Computer and System Sciences (2010). To Appear. [ bib ] 
[52]  Fellows, M. R., Hermelin, D., Rosamond, F. A., and Vialette, S. On the parameterized complexity of multipleinterval graph problems. Journal of Theoretical Computer Science 410, 1 (2009), 5361. [ bib  link ] 
[53]  Fellows, M. R., Guo, J., Komusiewicz, C., Niedermeier, R., and Uhlmann, J. Graphbased data clustering with overlaps. In Proceedings of COCOON (2009), vol. 5609 of Lecture Notes in Computer Science, Springer, pp. 516526. [ bib  link ] 
[54]  Fellows, M. R., Guo, J., and Kanj, I. The parameterized complexity of some minimum label problems. In Proceedings of WG (2009), Lecture Notes in Computer Science, SpringerVerlag. To Appear. [ bib  link ] 
[55]  Fellows, M. R., Hartman, T., Hermelin, D., Landau, G. M., Rosamond, F. A., and Rozenberg, L. Haplotype inference constrained by plausible haplotype data. In Proceedings of the of the 20th Combinatorial Pattern Matching conference, CPM (2009), pp. 339352. [ bib  link ] 
[56]  Betzler, N., Fellows, M. R., Komusiewicz, C., and Niedermeier, R. Parameterized algorithms and hardness results for some graph motif problems. In Proceedings of Combinatorial Pattern Matching, 19th Annual Symposium, CPM, (2008), P. Ferragina and G. M. Landau, Eds., vol. 5029 of Lecture Notes in Computer Science, Springer, pp. 3143. [ bib  link ] 
[57]  Fellows, M. R., Fertin, G., Hermelin, D., and Vialette, S. Sharp tractability borderlines for finding connected motifs in vertexcolored graphs. In Proceedings of Automata, Languages and Programming, 34th International Colloquium, ICALP (2007), L. Arge, C. Cachin, T. Jurdzinski, and A. Tarlecki, Eds., vol. 4596 of Lecture Notes in Computer Science, Springer, pp. 340351. [ bib  link ] 
[58]  Fellows, M. R., Langston, M. A., Rosamond, F. A., and Shaw, P. Efficient parameterized preprocessing for cluster editing. In Fundamentals of Computation Theory, 16th International Symposium, FCT, Budapest, Hungary (2007), E. CsuhajVarjú and Z. Ésik, Eds., vol. 4639 of Lecture Notes in Computer Science, Springer, pp. 312321. [ bib  link ] 
[59]  Fellows, M. R., Gramm, J., and Niedermeier, R. On the parameterized intractability of motif search problems. Combinatorica 26, 2 (2006), 141167. [ bib  link ] 
[60]  Fellows, M. R., Hallett, M., and Stege, U. Analogs & duals of the MAST problem for sequences & trees. Journal of Algorithms 49 (2003), 192  216. [ bib  link ] 
[61] 
Fellows, M. R., Gramm, J., and Niedermeier, R.
On the parameterized intractability of closest substring and related
problems.
In Proceedings of the 19th Annual Symposium on Theoretical
Aspects of Computer Science, STACS'02 (2002), H. Alt and A. Ferreira,
Eds., vol. 2285 of Lecture Notes in Computer Science, SpringerVerlag,
pp. 262273.
[ bib 
link ]
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) 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 NPcomplete 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.

[62] 
Bodlaender, H. L., Fellows, M. R., Hallett, M. T., Wareham, H. T., and
Warnow, T. J.
The hardness of perfect phylogeny, feasible register assignment and
other problems on thin colored graphs.
Theoretical Computer Science A 244, 12 (2000), 167188.
[ bib 
link ]
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 2 N. We also show that Intervalizing Colored Graphs, Triangulating Colored Graphs, and Colored Cutwidth are NPComplete.

[63] 
Fellows, M., Hallett, M. T., Korostensky, C., and Stege, U.
Analogs and duals of the MAST problem for sequences and trees.
In Proceedings of the 6th Annual European Symposium on
Algorithms (1998), G. Bilardi, G. F. Italiano, A. Pietracaprina, and G. P.
cci, Eds., no. 1461 in Lecture Notes in Computer Science, SpringerVerlag,
Berlin, pp. 103114.
[ bib 
link ]
Two natural kinds of problems about "structured collections of symbols" can be generally refered to as the Largest Common Subobject and the Smallest Common Superobject problems, which we consider here as the dual problems of interest. For the case of rooted binary trees where the symbols occur as leaflabels and a subobject is defined by labelrespecting hereditary topological containment, both of these problems are NPcomplete, as are the analogous problems for sequences (the wellknown Longest Common Subsequence and Shortest Common Supersequence problems). However, when the trees are restricted by allowing each symbol to occur as a leaflabel at most once (which we call a phylogenetic tree or ptree), then the Largest Common Subobject problem, better known as the Maximum Agreement Subtree (MAST) problem, is solvable in polynomial time. We explore the complexity of the basic subobject and superobject problems for sequences and binary trees.

[64] 
Fellows, M., Hallett, M., and Stege, U.
On the multiple gene duplication problem.
In Proceedings of the 9th International Symposium on Algorithms
and Computation, ISAAC'98 (1998), K.Y. Chwa and O. H. Ibarra, Eds.,
vol. 1533 of Lecture Notes in Computer Science, SpringerVerlag,
pp. 347356.
[ bib 
link ]
A fundamental problem in computational biology is the determination of the correct species tree for a set of taxa given a set of (possibly contradictory) gene trees. In recent literature, the Duplication/ Loss model has received considerable attention. Here one measures the similarity/dissimilarity between a set of gene trees by counting the number of paralogous gene duplications and subsequent gene losses which need to be postulated in order to explain (in an evolutionarily meaningful way) how the gene trees could have arisen with respect to the species tree. Here we count the number of multiple gene duplication events (duplication events in the genome of the organism involving one or more genes) without regard to gene losses. Multiple Gene Duplication asks to find the species tree S which requires the fewest number of multiple gene duplication events to be postulated in order to explain a set of gene trees G1 ; G2 ; : : : ; Gk . We also examine related problems.

[65]  Bailey, I., Cattell, K., Fellows, M. R., Koop, B., Olafson, R., Olafson, R., and Upton, C. Approaches to detection of distantly related proteins by database searches. BioTechniques 21 (1996), 1118  1125. [ bib ] 
[66]  Bodlaender, H. L., Downey, R. G., Fellows, M. R., Hallett, M. T., and Wareham, H. T. Parameterized complexity analysis in computational biology. Computer Applications in the Biosciences 11, 1 (1995), 4957. [ bib  link ] 
[67]  Bodlaender, H. L., Downey, R. G., Fellows, M. R., and Wareham, H. T. The parameterized complexity of sequence alignment and consensus. Theoretical Computer Science 147, 1&2 (1995), 3154. [ bib  link ] 
[68]  Bodlaender, H. L., Downey, R. G., Fellows, M. R., and Wareham, H. T. The parameterized complexity of sequence alignment and consensus. In Proceedings of Combinatorial Pattern Matching, 5th Annual Symposium, CPM (1994), M. Crochemore and D. Gusfield, Eds., vol. 807 of Lecture Notes in Computer Science, Springer, pp. 1530. [ bib ] 
[69]  Bodlaender, H. L., Downey, R. G., Fellows, M. R., Hallett, M. T., and Wareham, H. T. Parameterized complexity analysis in computational biology. Proceedings of the IEEE Computer Society Workshop on Shape and Pattern Recognition in Computational Biology (1994), 99116. IBM TJ Watson Research Center Publication. [ bib ] 
[70]  Fellows, M. R., Hallett, M. T., and Wareham, H. T. DNA physical mapping: Three ways difficult. In Proceedings of the 1st Annual European Symposium on Algorithms, ESA '93, T. Lengauer, Ed., vol. 726 of Lecture Notes in Computer Science. SpringerVerlag, 1993, pp. 157168. [ bib ] 
[71]  Bodlaender, H. L., Fellows, M. R., and Warnow, T. J. Two strikes against perfect phylogeny. In Proceedings of the 19th International Colloquium on Automata, Languages and Programming, ICALP'92 (1992), W. Kuich, Ed., vol. 623 of Lecture Notes in Computer Science, SpringerVerlag, pp. 273283. [ bib  link ] 
Social Choice  
[72]  Betzler, N., Fellows, M. R., Guo, J., Niedermeier, R., and Rosamond, F. Fixedparameter algorithms for Kemeny Rankings. Theoretical Computer Science (2009). Accepted for publication, August 2009, 30 pages. [ bib  link ] 
[73]  Betzler, N., Fellows, M. R., Guo, J., Niedermeier, R., and Rosamond, F. A. How similarity helps to efficiently compute Kemeny Rankings. In Proceedings of the 8th International Conference on Autonomous Agents and Multiagent Systems AAMAS (2009), pp. 657664. [ bib  link ] 
[74]  Betzler, N., Fellows, M. R., Guo, J., Niedermeier, R., and Rosamond, F. A. Fixedparameter algorithms for Kemeny scores. In Proceedings of Algorithmic Aspects in Information and Management, 4th International Conference, AAIM (2008), R. Fleischer and J. Xu, Eds., vol. 5034 of Lecture Notes in Computer Science, SpringerVerlag, pp. 6071. [ bib  link ] 
[75]  Betzler, N., Fellows, M. R., Guo, J., Niedermeier, R., and Rosamond, F. A. Computing Kemeny Rankings, parameterized by the average KT distance. In Proceedings of the 2nd International Workshop on Computational Social Choice, COMSOC (2008). [ bib  link ] 
[76]  Christian, R., Fellows, M. R., Rosamond, F., and Slinko, A. On the complexity of lobbying in multiple referenda. Review of Economic Design 11 (2007), 217224. [ bib  link ] 
[77]  Fellows, M. R., Rosamond, F., and Slinko, A. Sensing God's Will is fixed parameter tractable. Tech. rep., University of Auckland, New Zealand, 2008. University of Auckland, NZ Mathematics Research Report, 9 pages. [ bib  link ] 
Structural Parameterized Complexity  
[78]  Fellows, M., Hromkovic, J., Rosamond, F., and Steinova, M. Fixedparameter tractability, relative kernelization and the effectivization of structural connections. In Proceedings of CiE'09 (2009), Lecture Notes in Computer Science, SpringerVerlag. To Appear. [ bib  link ] 
[79]  Fellows, M. R., Guo, J., Moser, H., and Niedermeier, R. A complexity dichotomy for finding disjoint solutions of vertex deletion problems. In Proceedings of MFCS'09 (2009), vol. 5734 of Lecture Notes in Computer Science, SpringerVerlag, pp. 319330. [ bib  link ] 
[80]  Enciso, R., Fellows, M. R., Guo, J., Kanj, I., Rosamond, F., and Suchy, A. What makes equitable connected partition easy? In Proceedings of International Workshop of Parameterized and Exact Computation, IWPEC'09 (2009), Lecture Notes in Computer Science, SpringerVerlag. To Appear. [ bib ] 
[81]  Fellows, M., Fomin, F. V., Lokshtanov, D., Rosamond, F., Saurabh, S., and Villanger, Y. Local search: Is brute force avoidable? In Proceedings International Joint Conference on Artificial Intelligence, IJCAI'09 (2009). To Appear. [ bib  link ] 
[82]  Fellows, M. R., Fomin, F. V., Lokshtanov, D., Losievskaja, E., Rosamond, F. A., and Saurabh, S. Distortion is fixed parameter tractable. In Proceedings of ICALP'09 (Track A) (2009), pp. 463474. [ bib  link ] 
[83] 
Fellows, M., Fomin, F., Lokshtanov, D., Losievskaja, E., Rosamond, F. A.,
and Saurabh, S.
Parameterized lowdistortion embeddings  graph metrics into lines
and trees.
Tech. rep., 2009.
Manuscript.
[ bib ]
We describe algorithms for finding a low distortion noncontracting embedding of M into line and tree metrics. We give an O(nd^{4}(2d+1)^{2d}) time algorithm that for an unweighted graph metric M and integer d either constructs an embedding of M into the line with distortion at most d, or concludes that no such embedding exists. We find the result surprising, because the considered problem bears a strong resemblance to the notoriously hard Bandwidth Minimization problem which does not admit any FPT algorithm unless an unlikely collapse of parameterized complexity classes occurs. We show that our algorithm can also be applied to construct small distortion embeddings of weighted graph metrics. The running time of our algorithm is O(n(dW)^{4}(2d+1)^{2dW}) where W is the largest edge weight of the input graph. We also show that deciding whether a weighted graph metric M(G) with maximum weight W < V(G) can be embedded into the line with distortion at most d is NPComplete for every fixed rational d >=2. This rules out any possibility of an algorithm with running time O((nW)^{h(d)}) where h is a function of d alone. We generalize the result on embedding into the line by proving that for any tree T with maximum degree Δ, embedding of M into a shortest path metric of T is FPT, parameterized by (Δ,d).

[84]  Fellows, M. R., Hermelin, D., Müller, M., and Rosamond, F. A. A purely democratic characterization of W[1]. In Proceedings of Parameterized and Exact Computation, Third International Workshop IWPEC'08 (2008), M. Grohe and R. Niedermeier, Eds., vol. 5018 of Lecture Notes in Computer Science, SpringerVerlag, pp. 103114. [ bib  link ] 
[85]  Bodlaender, H. L., Downey, R. G., Fellows, M. R., and Hermelin, D. On problems without polynomial kernels. In Automata, Languages and Programming, 35th International Colloquium, ICALP'08, Part I: Track A: Algorithms, Automata, Complexity, and Games (2008), L. Aceto, I. Damgård, L. A. Goldberg, M. M. Halldórsson, A. Ingólfsdóttir, and I. Walukiewicz, Eds., vol. 5125 of Lecture Notes in Computer Science, Springer, pp. 563574. [ bib  link ] 
[86] 
Fellows, M., Flum, J., Hermelin, D., Muller, M., and Rosamond, F.
Whierarchies defined by symmetric gates.
Theory of Computing Systems (2008).
[ bib 
link ]
Originally defined via the weighted satisfiability problem for Boolean circuits, the classes of the Whierarchy are the most important classes of intractable problems in parameterized complexity. Here, besides the Boolean connectives, we consider connectives such as majority, notallequal, and unique. For example, a gate labelled by the majority connective outputs true if more than half of its inputs are true. For any finite set of connectives we construct the corresponding W(x)hierarchy. We derive some general conditions which guarantee that the Whierarchy and the W(x)hierarchy coincide levelwise. If only contains the majority connective then the first levels of the hierarchies coincide. We use this to show that a variant of the parameterized vertex cover problem, the majority vertex cover problem, is W[1]complete.

[87]  Fellows, M., and Fernau, H. Facility location problems: A parameterized view. In Proceedings of AAIM'08 (2008), vol. 5034 of Lecture Notes in Computer Science, Springer, pp. 188199. [ bib  link ] 
[88] 
Fellows, M., Fomin, F. V., Lokshtanov, D., Rosamond, F., Saurabh, S.,
Szeider, S., and Thomassen., C.
On the complexity of some colorful problems parameterized by
treewidth. (invited paper).
In Proceedings of First International Conference on
Combinatorial Optimization and Applications COCOA'07 (2007), vol. 4616 of
Lecture Notes in Computer Science, SpringerVerlag, pp. 366377.
[ bib 
link ]
We study the complexity of several coloring problems on graphs, parameterized by the treewidth of the graph: 1) 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 for every fixed treewidth bound t. The method by which this is shown is new and of general applicability. 2) 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. 3) 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 (t, r). We also show that a listbased variation, LIST EQUITABLE COLORING is W[1]hard for trees, parameterized by the number of colors on the lists.

[89] 
Cai, L., Fellows, M., Juedes, D., and Rosamond, F.
The complexity of polynomialtime approximation.
Theory of Computing Systems 41, 3 (2007), 459477.
[ bib 
link ]
In 1996, Khanna and Motwani proposed three logicbased optimization problems constrained by planar structure, and offered the hypothesis that these putatively fundamental problems might provide insight intocharacterizing the class of optimization problems that admit a polynomialtime approximation scheme (PTAS). This paper explores this program from the point of view of parameterized complexity. Problems of optimization are naturally parameterized by the parameter k = 1/ε. We show that there are EPTASs for some subproblems described by syntactic restrictions, and establish some limits on how far these positive results can be extended.

[90]  Fellows, M., Flum, J., Hermelin, D., Müller, M., and Rosamond, F. Parameterized complexity via combinatorial circuits. In Algorithms and Complexity in Durham 2007, Proceedings of the third ACiD Workshop (2007), H. Broersma, S. Dantchev, M. Johnson, and S. Szeider, Eds., vol. 9 of Texts in Algorithmics, College Publications London, pp. 5567. [ bib  link ] 
[91]  Chen, J., Chor, B., Fellows, M., Huang, X., Juedes, D. W., Kanj, I. A., and Xia, G. Tight lower bounds for certain parameterized NPhard problems. Information and Computation 201, 2 (2005), 216231. [ bib  link ] 
[92]  Downey, R. G., EstivillCastro, V., Fellows, M. R., Prieto, E., and Rosamond, F. A. Cutting up is hard to do: the parameterized complexity of kcut and related problems. Electronic Notes in Theoretical Computer Science 78 (2003), 205218. [ bib  link ] 
[93]  Downey, R. G., and Fellows, M. R. Index sets and parametric reductions. Archive for Mathematical Logic 40, 5 (2001), 329348. [ bib  link ] 
[94]  Downey, R. G., and Fellows, M. R. Threshold dominating sets and an improved characterization of W[2]. Theoretical Computer Science 209, 12 (1998), 123140. [ bib  link ] 
[95]  Downey, R. G., Fellows, M. R., and Regan, K. W. Parameterized circuit complexity and the W hierarchy. Theoretical Computer Science A 191, 12 (1998), 97115. [ bib  link ] 
[96]  Cai, L., Chen, J., Downey, R. G., and Fellows, M. R. Advice classes of parameterized tractability. Annals of Pure and Applied Logic 84, 1 (1997), 119138. [ bib  link ] 
[97] 
Cai, L., Chen, J., Downey, R. G., and Fellows, M. R.
The parameterized complexity of short computation and factorization.
Archive for Mathematical Logic 36 (1997), 321338.
[ bib 
link ]
We study the parameterized complexity of: (1) problems concerning parameterized computations of Turing machines, such as determining whether a nondeterministic machine can reach an accept state in steps (the Short TM Computation Problem), and (2) problems concerning derivations and factorizations, such as determining whether a word can be derived in a grammar in steps, or whether a permutation has a factorization of length over a given set of generators. We show hardness and completeness for these problems for various levels of the hierarchy.

[98]  Downey, R., Fellows, M., and Regan, K. Descriptive complexity and the W hierarchy. In Proof Complexity and Feasible Arithmetics, P. Beame and S. Buss, Eds., AMSDIMACS Series in Discrete Mathematics and Theoretical Computer Science. American Mathematical Society, 1997, pp. 119134. [ bib  link ] 
[99]  Downey, R. G., Fellows, M. R., and Taylor, U. The parameterized complexity of relational database queries and an improved characterization of W[1]. In Combinatorics, Complexity, and Logic – Proceedings of DMTCS ’96 (1996), D. Bridges, C. Calude, J. Gibbons, S. Reeves, and I. Witten, Eds., SpringerVerlag, pp. 194213. [ bib  link ] 
[100]  Cesati, M., and Fellows, M. Sparse parameterized problems. Annals of Pure and Applied Logic 82 (1996), 115. [ bib  link ] 
[101]  Abrahamson, K., Downey, R. G., and Fellows, M. R. Fixedparameter tractability and completeness IV: On completeness for W[P] and PSPACE analogs. Annals of Pure and Applied Logic 73 (1995), 235276. [ bib  link ] 
[102]  Downey, R. G., and Fellows, M. R. Fixedparameter tractability and completeness II: On completeness for W[1]. Theoretical Computer Science 141, 1&2 (1995), 109131. [ bib  link ] 
[103]  Downey, R., and Fellows, M. Fixedparameter tractability and completeness III: Some structural aspects of the W hierarchy. In Complexity Theory: Current Research  Proceedings of the 1992 Dagstuhl Workshop on Structural Complexity (Cambridge, 1993), K. AmbosSpies, S. Homer, and U. Schöning, Eds., Cambridge University Press, pp. 191225. [ bib ] 
[104] 
Cai, L., Chen, J., Downey, R., and Fellows, M.
On the structure of parameterized problems in NP.
Information and Computation 123, 1 (1995), 3849.
[ bib ]
Fixedparameter intractability of optimization problems in NP is studied based on computational models with limited nondeterminism. Strong evidence is shown that many NP optimization problems are not fixedparameter tractable and that the fixedparameter intractability hierarchy (the Whierarchy) does not collapse.

[105]  Downey, R. G., and Fellows, M. R. Fixedparameter tractability and completeness I: Basic results. SIAM Journal of Computing 24, 4 (1995), 873921. [ bib  link ] 
[106]  Cai, L., Chen, J., Downey, R. G., and Fellows, M. R. On the structure of parameterized problems in NP. In Proceedings of 11th Annual Symposium on Theoretical Aspects of Computer Science, STACS'94, Caen, France (1994), P. Enjalbert, E. W. Mayr, and K. W. Wagner, Eds., vol. 775 of Lecture Notes in Computer Science, Springer, pp. 509520. [ bib ] 
[107]  Abrahamson, K. A., Downey, R. G., and Fellows, M. R. Fixedparameter intractability II. In Proceedings of the 10th Annual Symposium on Theoretical Aspects of Computer Science, STACS'93 (1993), P. Enjalbert, A. Finkel, and K. W. Wagner, Eds., vol. 665 of Lecture Notes in Computer Science, SpringerVerlag, pp. 374385. [ bib ] 
[108]  Downey, R., and Fellows, M. Fixedparameter intractability. In Proceedings of the Seventh Annual IEEE Conference on Structure in Complexity Theory (1992), pp. 3649. [ bib ] 
[109]  Downey, R., and Fellows, M. Fixedparameter tractability and completeness. Congressus Numerantium 87 (1992), 161178. [ bib ] 
[110] 
Fellows, M. R., and Langston, M.
An analogue of the MyhillNerode theorem and its use in computing
finitebasis characterizations.
In Proceedings of 30th annual Symposium on Foundations of
Computer Science FOCS'89 (1989), IEEE Computer Society Press,
pp. 520525.
[ bib 
link ]
A theorem that is a graphtheoretic analog of the MyhillNerode 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.

[111] 
Abrahamson, K. R., Fellows, M. R., Ellis, J. A., and Mata, M. E.
On the complexity of fixed parameter problems.
In Proceedings of 30th annual Symposium on Foundations of
Computer Science FOCS'89 (1989), IEEE Computer Society Press,
pp. 210215.
[ bib 
link ]
The paper addresses the question of why some fixedparameter problem families solvable in polynomial time seem to be harder than others with respect to fixedparameter tractability: whether there is a constant α such that all problems in the family are solvable in time O(nα). 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 fixedparameter tractability, and (2) some natural problems are complete.

[112]  Downey, R., Fellows, M., and Mccartin, C. Parameterized approximation problems. Tech. rep. [ bib ] 
Computational Geometry  
[113]  Fellows, M., Giannopoulos, P., Knauer, C., Paul, C., Rosamond, F., Whitesides, S., and Yu, N. On the parameterized complexity of the discrete milling problem with turn costs. In Proceedings of FST TCS'09 (2009), SpringerVerlag. To Appear. [ bib ] 
[114]  M. Dom, M. F., and Rosamond, F. Parameterized complexity of stabbing rectangles and squares in the plane. In Proceedings of the 3rd Workshop on Algorithms and Computation, WALCOM'09 (2009), vol. 5431 of Lecture Notes in Computer Science, SpringerVerlag, pp. 298309. [ bib  link ] 
[115]  Fellows, M. R., Knauer, C., Nishimura, N., Ragde, P., Rosamond, F., Stege, U., Thilikos, D., and Whitesides, S. Faster fixed parameter tractable algorithms for matching and packing problems. Algorithmica 52, 2 (2008), 167176. [ bib  link ] 
[116]  Dujmovic, V., Fellows, M. R., Kitching, M., Liotta, G., McCartin, C., Nishimura, N., Ragde, P., Rosamond, F., Whitesides, S., and Wood, D. R. On the parameterized complexity of layered graph drawing. Algorithmica 52, 2 (2008), 267292. [ bib  link ] 
[117]  Dujmovic, V., Fellows, M. R., Hallett, M. T., Kitching, M., Liotta, G., McCartin, C., Nishimura, N., Ragde, P., Rosamond, F. A., Suderman, M., Whitesides, S., and Wood, D. R. A fixedparameter approach to 2layer planarization. Algorithmica 45, 2 (2006), 159182. [ bib  link ] 
[118]  Dujmovic, V., Fellows, M. R., Hallett, M. T., Kitching, M., Liotta, G., McCartin, C., Nishimura, N., Ragde, P., Rosamond, F. A., Suderman, M., Whitesides, S., and Wood, D. R. A fixedparameter approach to twolayer planarization. In Proceedings of the 9th International Symposium on Graph Drawing GD'01 (2001), vol. 2265 of Lecture Notes in Computer Science, SpringerVerlag, pp. 115. [ bib  link ] 
[119]  Dujmović, V., Fellows, M., Hallett, M., Kitching, M., Liotta, G., McCartin, C., Nishimura, N., Ragde, P., Rosamond, F., Suderman, M., Whitesides, S., and Wood, D. R. On the parameterized complexity of layered graph drawing. In Proceedings of the 9th Annual European Symposium on Algorithms, ESA '01 (2001), vol. 2161 of Lecture Notes in Computer Science, SpringerVerlag, pp. 488499. [ bib ] 
Cryptography and Coding Theory  
[120]  Bell, T., Fellows, M., Witten, I., and Koblitz, N. Explaining cryptographic systems to the general public. Computers and Education 40 (2003), 199215. [ bib ] 
[121] 
Downey, R. G., Fellows, M. R., Vardy, A., and Whittle, G.
The parametrized complexity of some fundamental problems in coding
theory.
SIAM Journal of Computing 29, 2 (1999), 545570.
[ bib 
link ]
The parametrized complexity of a number of fundamental problems in the theory of linear codes and integer lattices is explored. Concerning codes, the main results are that MAXIMUMLIKELIHOOD DECODING and WEIGHT DISTRUBUTION are hard for the parametrized complexity class W[1]. The NPcompleteness of these two problems was established by Berlekamp, McEliece, and van Tilborg in 1978 using by means of a reduction from THREEDIMENSIONAL MATCHING. On the other hand, our proof of hardness for W[1] is based on a parametric polynomialtime transformation from PERFECT CODE in graphs. An immediate consequence of our results is that boundeddistance decoding is likely to be hard for binary linear codes. Concerning lattices, we prove here for the first time that THETA SERIES is NPcomplete and show that it is also hard for W[1]. Furthermore, we prove that the NEAREST VECTOR problem for integer lattices is hard for W[1]. These problems are the counterparts of WEIGHT DISTRUBUTION and MAXIMUMLIKELIHOOD DECODING for lattices. Relations between all these problems and combinatorial problems in graphs are discussed.

[122]  Downey, R. G., Fellows, M. R., Vardy, A., and Whittle, G. The parametrized complexity of some fundamental problems of linear codes and integral lattices. Tech. rep., 1997. Manuscript. [ bib  link ] 
[123]  Fellows, M., and Koblitz, N. Combinatorial cryptosystems galore! In Proceedings of the Second International Symposium on Finite Fields, Las Vegas, Nevada, August, 1993 (1994), vol. 168 of Contemporary Mathematics, American Mathematical Society, pp. 5161. [ bib  link ] 
[124]  Fellows, M. R., and Koblitz, N. Fixedparameter complexity and cryptography. In Proceedings of 10th International Symposium Applied Algebra, Algebraic Algorithms and ErrorCorrecting Codes, AAECC'93, San Juan de Puerto Rico, Puerto Rico (1993), G. D. Cohen, T. Mora, and O. Moreno, Eds., vol. 673 of Lecture Notes in Computer Science, Springer, pp. 121131. [ bib ] 
[125]  Downey, R. G., Evans, P. A., and Fellows, M. R. Parameterized learning complexity. In Proceedings of the Sixth Annual ACM Conference on Computational Learning Theory (1993), ACM Press, pp. 5157. [ bib  link ] 
[126]  Fellows, M. R., and Koblitz, N. Selfwitnessing polynomialtime complexity and prime factorization. In Proceedings of the 7th Annual Conference on Structure in Complexity Theory, CSCT'92 (1992), IEEE Computer Society Press, pp. 107110. [ bib  link ] 
[127]  Fellows, M. R., and Koblitz, N. Selfwitnessing polynomialtime complexity and prime factorization. Designs, Codes and Cryptography 2, 3 (1992), 231235. [ bib ] 
[128]  Dinneen, M. J., Fellows, M. R., and Faber, V. Algebraic constructions of efficient broadcast networks. In Proceedings of Applied Algebra, Algebraic Algorithms and ErrorCorrecting Codes AAECC'91 (Berlin, Germany, 1991), H. F. Mattson, T. Mora, and T. R. N. Rao, Eds., vol. 539 of LNCS, SpringerVerlag, pp. 152158. [ bib ] 
Math and Science Popularization and Education  
[129]  Bell, T., Fellows, M., Koblitz, N., and Witten, I. Explaining cryptographic ideas to the general public. Computers and Education 40 (2003), 199—215. [ bib  link ] 
[130]  Bell, T., Fellows, M., Koblitz, N., and Witten, I. Explaining cryptographic systems to the general public. In Proceedings of the First IFIP World Conference on Information Security Education (WISE) (1999), L. Yngstgröm and S. FischerHübner, Eds., vol. 99008, Stockholm University Report Series, p. 221—233. [ bib ] 
[131]  Casey, N., and Fellows, M. Implementing the standards: Let’s focus on the first four. DIMACS Series: Discrete Mathematics in the Schools. How Can We Have an Impact? (1997). [ bib  link ] 
[132]  Fellows, M. The heart of puzzling: Mathematics and computer games. In Proceedings of the 1996 Computer Games Developers Conference (1996), Miller Freeman, p. 109—120. [ bib  link ] 
[133]  Fellows, M., Hibner, A., and Koblitz, N. Cultural aspects of mathematics education reform. Notices of the American Mathematics Society 41 (1994), 5—9. [ bib ] 
[134]  Fellows, M., and Koblitz, N. Kid krypto. In Proceedings of Crypto 1992 (1993), vol. 740 of Lecture Notes in Computer Science, SpringerVerlag, New York, Inc., p. 371—389. [ bib  link ] 
[135]  Fellows, M. Computer science in the elementary schools. In Proceedings of the Mathematicians and Education Reform Workshop, Seattle, 1991 (1993), N. Fisher, H. Keynes, and P. Wagreich, Eds., vol. 3 of Issues in Mathematics Education, Conference Board of the Mathematical Sciences, p. 143 –163. [ bib  link ] 
[136] 
Casey, N., and Fellows, M. R.
This is MegaMathematics!
Los Alamos National Labs, 1992.
Available at http://www.c3.lanl.gov/ captors/megamath. See also
www.ccs3.lanl.gov/megamath/write.html.
[ bib 
link ]
A collection of classroom lessons in mathematics and computer science. Each lesson contains extensive background material that assumes that the topic of the lesson is new to the teacher. Topics include map coloring, graph theory, knot theory, finite state machines, algorithms, logic and infinity.

Hypergraph Algorithms and Complexity  
[137]  Fellows, M., Lokshtanov, D., Misra, N., Mnich, M., Rosamond, F., and Saurabh, S. The complexity ecology of parameters: An illustration using bounded max leaf number. Theory of Computing Systems 45 (2009), 822848. [ bib  link ] 
[138]  Fellows, M., Guo, J., Moser, H., and Niedermeier, R. A generalization of Nemhauser and Trotter's local optimization algorithm. In Proceedings of STACS'09 (2009), pp. 409420. [ bib  link ] 
[139]  Fellows, M. R., Meister, D., Rosamond, F. A., Sritharan, R., and Telle, J. A. Leaf powers and their properties: Using the trees. In Proceedings of Algorithms and Computation, 19th International Symposium, ISAAC 2008, Gold Coast, Australia (2008), S.H. Hong, H. Nagamochi, and T. Fukunaga, Eds., vol. 5369 of Lecture Notes in Computer Science, SpringerVerlag, pp. 402413. [ bib  link ] 
[140]  Fellows, M. R., Lokshtanov, D., Misra, N., Rosamond, F. A., and Saurabh, S. Graph layout problems parameterized by vertex cover. In Proceedings of Algorithms and Computation, 19th International Symposium, ISAAC 2008, Gold Coast, Australia (2008), S.H. Hong, H. Nagamochi, and T. Fukunaga, Eds., vol. 5369 of Lecture Notes in Computer Science, SpringerVerlag, pp. 294305. [ bib  link ] 
[141]  Bodlaender, H. L., Fellows, M. R., Heggernes, P., Mancini, F., Papadopoulos, C., and Rosamond, F. A. Clustering with partial information. In Proceedings of Mathematical Foundations of Computer Science, 33rd International Symposium, MFCS 2008, Torun, Poland (2008), E. Ochmanski and J. Tyszkiewicz, Eds., vol. 5162 of Lecture Notes in Computer Science, SpringerVerlag, pp. 144155. [ bib  link ] 
[142]  Fellows, M. R., and Fernau, H. Facility location problems: A parameterized view. In Proceedings of Algorithmic Aspects in Information and Management, 4th International Conference, AAIM'08 (2008), R. Fleischer and J. Xu, Eds., vol. 5034 of Lecture Notes in Computer Science, SpringerVerlag, pp. 188199. [ bib  link ] 
[143]  Bodlaender, H. L., Fellows, M. R., Langston, M. A., Ragan, M. A., Rosamond, F. A., and Weyer, M. Quadratic kernelization for convex recoloring of trees. In Proceedings of Computing and Combinatorics, 13th Annual International Conference, COCOON'07 (2007), G. Lin, Ed., vol. 4598 of Lecture Notes in Computer Science, SpringerVerlag, pp. 8696. [ bib  link ] 
[144]  Fellows, M. R., Fomin, F. V., Lokshtanov, D., Rosamond, F. A., Saurabh, S., Szeider, S., and Thomassen, C. On the complexity of some colorful problems parameterized by treewidth. In Proceedings of Combinatorial Optimization and Applications, COCOA'07 (2007), A. W. M. Dress, Y. Xu, and B. Zhu, Eds., vol. 4616 of Lecture Notes in Computer Science, SpringerVerlag, pp. 366377. [ bib  link ] 
[145]  Chor, B., Fellows, M. R., Ragan, M. A., Razgon, I., Rosamond, F. A., and Snir, S. Connected coloring completion for general graphs: Algorithms and complexity. In Proceedings of Computing and Combinatorics, 13th Annual International Conference, COCOON'07 (2007), G. Lin, Ed., vol. 4598 of Lecture Notes in Computer Science, SpringerVerlag, pp. 7585. [ bib  link ] 
[146]  Fellows, M. R., Langston, M. A., Rosamond, F. A., and Shaw, P. Efficient parameterized preprocessing for cluster editing. In Proceedings of 16th International Symposium Fundamentals of Computation Theory FCT'07 (2007), E. CsuhajVarjú and Z. Ésik, Eds., vol. 4639 of Lecture Notes in Computer Science, SpringerVerlag, pp. 312321. [ bib  link ] 
[147] 
Cai, L., Fellows, M., Juedes, D., and Rosamond, F.
The complexity of polynomialtime approximation.
Theory of Computing Systems 41, 3 (2007), 459477.
[ bib 
link ]
We show that Planar TMIN, Planar TMAX and Planar MPSAT, parameterized by k = 1/ε, are hard for W[1], and thus unlikely that they admit EPTASs. We show that there are EPTASs for some subproblems described by syntactic restrictions, and establish some limits on how far these positive results can be extended.

[148] 
AbuKhzam, F. N., Fellows, M. R., Langston, M. A., and Suters, W. H.
Crown structures for vertex cover kernelization.
Theory of Computing Systems 41, 3 (2007), 411430.
[ bib 
link ]
Crown structures in a graph are defined and shown to be useful in kernelization algorithms for the classic vertex cover problem. Two vertex cover kernelization methods are discussed. One, based on linear programming, has been in prior use and is known to produce predictable results, although it was not previously associated with crowns. The second, based on crown structures, is newer and much faster, but produces somewhat variable results. These two methods are studied and compared both theoretically and experimentally with each other and with older, more primitive kernelization algorithms. Properties of crowns and methods for identifying them are discussed. Logical connections between linear programming and crown reductions are established. It is shown that the problem of finding an induced crownfree subgraph, and the problem of finding a crown of maximum size in an arbitrary graph, are solvable in polynomial time.

[149] 
Dehne, F., Fellows, M., Langston, M., Rosamond, F., and Stevens, K.
An o(2^{O(k)}n^{3}) FPT algorithm for the undirected feedback
vertex set problem.
Theory of Computing Systems 41, 3 (2007), 479492.
[ bib 
link ]
Our algorithm is based on the new FPT technique of iterative compression. Our result holds for a more general form of the problem, where a subset of the vertices may be marked as forbidden to belong to the feedback set. We also establish "exponential optimality" for our algorithm.

[150]  Fellows, M. R., Gramm, J., and Niedermeier, R. On the parameterized intractability of motif search problems. Combinatorica 26, 2 (2006), 141167. [ bib  link ] 
[151]  Dehne, F., Fellows, M. R., Fernau, H., Prieto, E., and Rosamond, F. A. NONBLOCKER: Parameterized algorithmics for minimum dominating set. In Proceedings of Theory and Practice of Computer Science, 32nd Conference on Current Trends in Theory and Practice of Computer Science SOFSEM'06 (2006), J. Wiedermann, G. Tel, J. Pokorný, M. Bieliková, and J. Stuller, Eds., vol. 3831 of Lecture Notes in Computer Science, SpringerVerlag, pp. 237245. [ bib  link ] 
[152]  Fellows, M. R., Rosamond, F. A., Rotics, U., and Szeider, S. Cliquewidth minimization is NPhard. In Proceedings of the 38th Annual Symposium on Theory of Computing, ACM'06 (2006), J. M. Kleinberg, Ed., ACM, pp. 354362. [ bib  link ] 
[153]  Burrage, K., EstivillCastro, V., Fellows, M. R., Langston, M. A., Mac, S., and Rosamond, F. A. The undirected feedback vertex set problem has a poly(k) kernel. In Proceedings of Parameterized and Exact Computation, Second International Workshop, IWPEC'06 (2006), H. L. Bodlaender and M. A. Langston, Eds., vol. 4169 of Lecture Notes in Computer Science, SpringerVerlag, pp. 192202. [ bib  link ] 
[154]  Bodlaender, H. L., Fellows, M. R., Langston, M. A., Ragan, M. A., Rosamond, F. A., and Weyer, M. Kernelization for convex recoloring. In Proceedings of Algorithms and Complexity in Durham, ACiD'06 (2006), H. Broersma, S. S. Dantchev, M. J. 0002, and S. Szeider, Eds., vol. 7 of Texts in Algorithmics, King's College, London, pp. 2336. Accepted to Algorithmica. [ bib  link ] 
[155]  Alber, J., Fan, H., Fellows, M. R., Fernau, H., Niedermeier, R., Rosamond, F., and Stege, U. A refined search tree technique for dominating set on planar graphs. Journal of Computer and System Sciences 71, 4 (2005), 385405. [ bib  link ] 
[156]  Dehne, F. K. H. A., Fellows, M. R., Langston, M. A., Rosamond, F. A., and Stevens, K. An O(2^{O(k)}n^{3}) FPT algorithm for the undirected feedback vertex set problem. In Proceedings of Computing and Combinatorics, 11th Annual International Conference, COCOON'05 (2005), L. Wang, Ed., vol. 3595 of Lecture Notes in Computer Science, SpringerVerlag, pp. 859869. [ bib  link ] 
[157]  EstivillCastro, V., Fellows, M. R., Langston, M. A., and Rosamond, F. A. Fixedparameter tractability is polynomialtime extremal structure theory I: The case of max leaf. In Proceedings of Algorithms and Complexity in Durham, ACiD 2005 (2005), H. Broersma, M. J. 0002, and S. Szeider, Eds., vol. 4 of Texts in Algorithmics, King's College, London, pp. 141. [ bib  link ] 
[158] 
Alber, J., Fellows, M. R., and Niedermeier, R.
Polynomialtime data reduction for dominating set.
Journal of the ACM 51, 3 (2004), 363384.
[ bib 
link ]
We demonstrate the power of data reduction by preprocessing from a theoretical as well as a practical side. In particular, we prove that Dominating Set restricted to planar graphs has a problem kernel of linear size, achieved by two easytoimplement reduction rules. Our first experiments indicate practical potential of these rules. Thus, this work seems to open up a new and way of coping with one of the most important problems in graph theory and combinatorial optimization.

[159] 
Ellis, J., Fan, H., and Fellows, M.
The dominating set problem is fixed parameter tractable for graphs of
bounded genus.
Journal of Algorithms 52, 2 (2004), 152168.
[ bib ]
We describe an algorithm for the dominating set problem with time complexity O((4g+40)^{k} n^{2}) for graphs of bounded genus g >=1, where k is the size of the set. It has previously been shown that this problem is fixed parameter tractable for planar graphs. We give a simpler proof for the previous O(8^{k} n^{2}) result for planar graphs.. Our method is a refinement of the earlier techniques.

[160]  AbuKhzam, F. N., Collins, R. L., Fellows, M. R., Langston, M. A., Suters, W. H., and Symons, C. T. Kernelization algorithms for the Vertex Cover problem: Theory and experiments. In Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the first Workshop on Analytic Algorithmics and Combinatorics ALENEX'04 (2004), L. Arge, G. F. Italiano, and R. Sedgewick, Eds., Siam Proceedings Series, Society of Industrial and Applied Mathematics, pp. 6269. [ bib ] 
[161]  Fellows, M. R., Knauer, C., Nishimura, N., Ragde, P., Rosamond, F. A., Stege, U., Thilikos, D. M., and Whitesides, S. Faster fixedparameter tractable algorithms for matching and packing problems. In Proceedings of 12th Annual European Symposium on Algorithms ESA'04 (2004), S. Albers and T. Radzik, Eds., vol. 3221 of Lecture Notes in Computer Science, SpringerVerlag, pp. 311322. [ bib  link ] 
[162]  Fellows, M., Heggernes, P., Rosamond, F. A., Sloper, C., and Telle, J. A. Finding k disjoint triangles in an arbitrary graph. In Proceedings of GraphTheoretic Concepts in Computer Science, 30th International Workshop,WG'04 (2004), J. Hromkovic, M. Nagl, and B. Westfechtel, Eds., vol. 3353 of Lecture Notes in Computer Science, SpringerVerlag, pp. 235244. [ bib  link ] 
[163]  Chor, B., Fellows, M., and Juedes, D. W. Linear kernels in linear time, or how to save k colors in O(n^{2}) steps. In Proceedings of GraphTheoretic Concepts in Computer Science, 30th International Workshop,WG'04 (2004), J. Hromkovic, M. Nagl, and B. Westfechtel, Eds., vol. 3353 of Lecture Notes in Computer Science, SpringerVerlag, pp. 257269. [ bib  link ] 
[164]  Fellows, M. R., Hallett, M., and Stege, U. Analogs and duals of the MAST problem for sequences & trees. Journal of Algorithms 49 (2003), 192  216. [ bib  link ] 
[165]  Downey, R. G., EstivillCastro, V., Fellows, M. R., Prieto, E., and Rosamond, F. A. Cutting up is hard to do: the parameterized complexity of kcut and related problems. Electronic Notes in Theoretical Computer Science 78 (2003), 205218. [ bib  link ] 
[166] 
Fellows, M. R.
Blowups, win/win's, and crown rules: Some new directions in FPT.
In Proceedings of the 29th International Workshop on
GraphTheoretic Concepts in Computer Science, WG'03 (2003), H. L.
Bodlaender, Ed., vol. 2880 of LNCS, SpringerVerlag, pp. 112.
[ bib 
link ]
This survey reviews the basic notions of parameterized complexity, and describes some new approaches to designing FPT algorithms and problem reductions for graph problems.

[167] 
Dehne, F., Fellows, M. R., and Rosamond, F. A.
An FPT algorithm for set splitting.
In Proceedings of the 29th International Workshop on
GraphTheoretic Concepts in Computer Science, WG'03 (2003), H. L.
Bodlaender, Ed., vol. 2880 of Lecture Notes in Computer Science,
SpringerVerlag, pp. 180191.
[ bib 
link ]
An FPT algorithm with a running time of O(n ^{4} + 2^{O(k)} n^{2.5}) is described for the Set Splitting problem, parameterized by the number k of sets to be split. It is also shown that there can be no FPT algorithm for this problem with a running time of the form 2^{o(k)} n^{c} unless the satisfiability of nvariable 3SAT instances can be decided in time 2^{o(n)}.

[168]  Bodlaender, H. L., Fellows, M. R., and Thilikos, D. M. Starting with nondeterminism: The systematic derivation of lineartime graph layout algorithms. In Proceedings of Mathematical Foundations of Computer Science MFCS'03 (2003), B. Rovan and P. Vojtás, Eds., vol. 2747 of Lecture Notes in Computer Science, Springer, pp. 239248. [ bib  link ] 
[169]  Alber, J., Fellows, M. R., and Niedermeier, R. Efficient data reduction for DOMINATING SET: A linear problem kernel for the planar case. In Proceedings of 8th Scandinavian Workshop on Algorithm Theory SWAT'02 (2002), M. Penttonen and E. M. Schmidt, Eds., vol. 2368 of Lecture Notes in Computer Science, Springer, pp. 150159. [ bib  link ] 
[170]  Ellis, J., Fan, H., and Fellows, M. R. The dominating set problem is fixed parameter tractable for graphs of bounded genus. In Proceedings of SWAT 2002: Scandinavian Workshop on Algorithm Theory (2002), M. Penttonen and E. M. Schmidt, Eds., vol. 2368 of LNCS, Springer, pp. 180189. [ bib  link ] 
[171] 
Alber, J., Fan, H., Fellows, M. R., Fernau, H., Niedermeier, R., Rosamond,
F. A., and Stege, U.
A refined search tree technique for DOMINATING SET on planar
graphs.
In Proceedings of 26th International Symposium Mathematical
Foundations of Computer Science, MFCS'01 (2001), J. Sgall, A. Pultr, and
P. Kolman, Eds., vol. 2136 of Lecture Notes in Computer Science,
SpringerVerlag, pp. 111122.
[ bib 
link ]
We establish refined search tree techniques for the parameterized Dominating Set problem on planar graphs. We prove an intricate branching theorem based on the Euler formula. In addition, we give a family of example graphs showing that the bound of the branching theorem is optimal with respect to our reduction rules. Our final algorithm is easy to implement; its analysis, however, is involved.

[172]  Downey, R. G., Fellows, M. R., and Raman, V. The complexity of irredundant sets parameterized by size. Discrete Applied Mathematics 100, 3 (2000), 155167. [ bib  link ] 
[173] 
Bodlaender, H. L., Fellows, M. R., Hallett, M. T., Wareham, H. T., and
Warnow, T. J.
The hardness of perfect phylogeny, feasible register assignment and
other problems on thin colored graphs.
Theoretical Computer Science A 244, 12 (2000), 167188.
[ bib 
link ]
We consider the complexity of 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 a uniform upper bound on the tree or pathwidth 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 W [t] for all t 2 N. We also show that Intervalizing Colored Graphs, Triangulating Colored Graphs, and Colored Cutwidth are NPComplete.

[174]  Fellows, M. R., McCartin, C., Rosamond, F. A., and Stege, U. Coordinatized kernels and catalytic reductions: An improved FPT algorithm for max leaf spanning tree and other problems. In Proceedings of Foundations of Software Technology and Theoretical Computer Science, 20th Conference, FST TCS '00 (2000), S. Kapoor and S. Prasad, Eds., vol. 1974 of Lecture Notes in Computer Science, SpringerVerlag, pp. 240251. [ bib  link ] 
[175] 
Fellows, M., Hallett, M. T., Korostensky, C., and Stege, U.
Analogs and duals of the MAST problem for sequences and trees.
In Proceedings of the 6th Annual European Symposium on
Algorithms (1998), G. Bilardi, G. F. Italiano, A. Pietracaprina, and G. P.
cci, Eds., no. 1461 in Lecture Notes in Computer Science, SpringerVerlag,
Berlin, pp. 103114.
[ bib 
link ]
Two natural kinds of problems about "structured collections of symbols" can be generally refered to as the Largest Common Subobject and the Smallest Common Superobject problems, which we consider here as the dual problems of interest. For the case of rooted binary trees where the symbols occur as leaflabels and a subobject is defined by labelrespecting hereditary topological containment, both of these problems are NPcomplete, as are the analogous problems for sequences (the wellknown Longest Common Subsequence and Shortest Common Supersequence problems). However, when the trees are restricted by allowing each symbol to occur as a leaflabel at most once (which we call a phylogenetic tree or ptree), then the Largest Common Subobject problem, better known as the Maximum Agreement Subtree (MAST) problem, is solvable in polynomial time. We explore the complexity of the basic subobject and superobject problems for sequences and binary trees.

[176]  Balasubramanian, Fellows, and Raman. An improved fixedparameter algorithm for vertex cover. IPL: Information Processing Letters 65, 3 (1998), 163168. [ bib  link ] 
[177]  Downey, R. G., and Fellows, M. R. Threshold dominating sets and an improved characterization of W[2]. Theoretical Computer Science 209, 12 (1998), 123140. [ bib  link ] 
[178]  Alon, N., Fellows, M. R., and Hare, D. R. Vertex transversals that dominate. Journal of Graph Theory 21, 1 (1996), 2132. [ bib  link ] 
[179] 
Cattell, K., Dinneen, M. J., and Fellows, M. R.
A simple lineartime algorithm for finding pathdecompositions of
small width.
Information Processing Letters 57, 4 (1996), 197203.
[ bib 
link ]
We describe a simple algorithm running in linear time for each fixed constant k, that either establishes that the pathwidth of a graph G is greater than k, or finds a pathdecomposition of G of width at most O(2^{k}). This provides a simple proof of the result by Bodlaender that many families of graphs of bounded pathwidth can be recognized in linear time.

[180]  Downey, R. G., Fellows, M. R., and Taylor, U. The parameterized complexity of relational database queries and an improved characterization of W[1]. In Proceedings of Combinatorics, Complexity, and Logic, DMTCS'96 (1996), D. Bridges, C. Calude, J. Gibbons, S. Reeves, and I. Witten, Eds., SpringerVerlag, pp. 194213. [ bib  link ] 
[181]  Fellows, M., Fricke, G., Hedetniemi, S., and Jacobs, D. The private neighbor cube. SIAM Journal on Discrete Mathematics 7, 1 (1994), 4147. [ bib ] 
[182]  Bodlaender, H. L., Fellows, M. R., and Hallett, M. T. Beyond NPcompleteness for problems of bounded width: Hardness for the W hierarchy. In Proceedings of the 26th Annual ACM Symposium on Theory of Computing, STOC'94 (New York, 1994), ACM Press, pp. 449458. [ bib  link ] 
[183]  Fellows, M. R., and Langston, M. A. On wellpartialorder theory and its application to combinatorial problems of VLSI design. SIAM Journal on Discrete Mathematics 5, 1 (1992), 117126. [ bib ] 
[184]  Abello, Fellows, and Stillwell. On the complexity and combinatorics of covering finite complexes. AJC: Australasian Journal of Combinatorics 4 (1991), 103112. [ bib ] 
[185]  Fellows, M. R., and Kaschube, P. A. Searching for k_{3,3} in linear time. Linear and Multilinear Algebra 29, 3 (1991), 279290. [ bib ] 
[186]  Fellows, M. R., and Hoover, M. Perfect domination. AJC: Australasian Journal of Combinatorics 3 (1991), 141150. [ bib ] 
[187]  Barefoot, C. A., Clark, L. H., Douthett, J., Entringer, R. C., and Fellows, M. R. Cycles of length 0 modulo 3 in graphs. Annals of Discrete Mathematics (1991), 87101. An earlier paper was presented at Graph theory, Combinatorics, and Applications, Volume 1. Proceedings of the Sixth Quadrennial International Conference on the Theory and Applications of Graphs. [ bib ] 
[188]  Fellows, M. R., and Wojciechowski, J. M. Counting spanning trees in directed regular multigraphs. Journal of the Franklin Institute 326 (1989), 889896. [ bib ] 
[189]  Brown, D. J., Fellows, M. R., and Langston, M. A. Polynomialtime selfreducibility: Theoretical motivations and practical results. International Journal of Computer Mathematics 31 (1989), 19. [ bib ] 
[190]  Fellows, M. R., and Stueckle, S. The immersion order, forbidden subgraphs and the complexity of network integrity. Journal of Combinatorial Mathematics and Combinatorial Computing 6 (1989), 2332. [ bib ] 
[191]  Fellows, M. R., Friesen, D. K., and Langston, M. A. On finding optimal and nearoptimal lineal spanning trees. Algorithmica 3, 4 (1988), 549560. [ bib ] 
[192] 
Fellows, M., Hoover, M., and Harary, F.
On the galactic number of a hypercube.
Mathematical and Computer Modelling 11 (1988), 212  215.
[ bib ]
A galaxy is a union of vertex disjoint stars. The galactic number of a graph is the minimum number of galaxies which partition the edge set. The galactic number of complete graphs is determined. This result is used to give bounds on the galactic number of binary cube graphs. The problem of determining the galactic number of a graph is shown to be NPcomplete.

[193]  Bryant, R. L., Fellows, M. R., Kinnersley, N. G., and Langston, M. A. On finding obstruction sets and polynomialtime algorithms for gate matrix layout. In Proceedings of the 25th Allerton Conference on Communication, Control and Computing (1987), pp. 397398. [ bib ] 
[194]  Fellows, M., Hickling, F., and Syslo, M. A topological parameterization and hard graph problems. Congressus Numerantium 59 (1987), 6978. [ bib ] 
[195]  Clark, L. H., Entringer, R. C., and Fellows, M. Computational complexity of integrity. Journal of Combinatorial Mathematics and Combinatorial Computing 2 (1987), 179191. [ bib ] 
Kernelization  
[196]  Bodlaender, H. L., Downey, R. G., Fellows, M. R., and Hermelin, D. On problems without polynomial kernels. Journal of Computer and System Sciences (2010). To Appear. [ bib ] 
[197]  Fellows, M., Hromkovic, J., Rosamond, F., and Steinova, M. Fixedparameter tractability, relative kernelization and the effectivization of structural connections. In Proceedings of CiE'09 (2009), Lecture Notes in Computer Science, SpringerVerlag. To Appear. [ bib  link ] 
[198]  Fellows, M. R. The complexity ecology of parameters: Some new developments and research directions. In Proceedings of IWOCA'09 (2009), Lecture Notes in Computer Science, SpringerVerlag. To Appear. [ bib  link ] 
[199]  Fellows, M., Lokshtanov, D., Misra, N., Mnich, M., Rosamond, F., and Saurabh, S. The complexity ecology of parameters: An illustration using bounded max leaf number. Theory of Computing Systems 45 (2009), 822848. [ bib  link ] 
[200]  Bodlaender, H., Fellows, M., Langston, M., Ragan, M., Rosamond, F., and Weyer, M. Quadratic kernelization for convex recoloring of trees. Algorithmica (2009). Accepted to Algorithmica. [ bib  link ] 
[201]  Bodlaender, H. L., Downey, R. G., Fellows, M. R., and Hermelin, D. On problems without polynomial kernels. In Automata, Languages and Programming, 35th International Colloquium, ICALP'08, Part I: Track A: Algorithms, Automata, Complexity, and Games (2008), L. Aceto, I. Damgård, L. A. Goldberg, M. M. Halldórsson, A. Ingólfsdóttir, and I. Walukiewicz, Eds., vol. 5125 of Lecture Notes in Computer Science, SpringerVerlag, pp. 563574. [ bib  link ] 
[202] 
AbuKhzam, F. N., Fellows, M. R., Langston, M. A., and Suters, W. H.
Crown structures for vertex cover kernelization.
Theory of Computing Systems 41, 3 (2007), 411431.
[ bib 
link ]
Crown structures in a graph are defined and shown to be useful in kernelization algorithms for the classic vertex cover problem. Two vertex cover kernelization methods are discussed. One, based on linear programming, has been in prior use and is known to produce predictable results, although it was not previously associated with crowns. The second, based on crown structures, is newer and much faster, but produces somewhat variable results. These two methods are compared both theoretically and experimentally with each other and with older kernelization algorithms. Properties of crowns and methods for identifying them are discussed. Logical connections between linear programming and crown reductions are established. It is shown that the problem of finding an induced crownfree subgraph, and the problem of finding a crown of maximum size in an arbitrary graph, are solvable in polynomial time.

[203]  Fellows, M. R., Langston, M. A., Rosamond, F. A., and Shaw, P. Efficient parameterized preprocessing for cluster editing. In Proceedings of Fundamentals of Computation Theory, 16th International Symposium, FCT'07 (2007), E. CsuhajVarjú and Z. Ésik, Eds., vol. 4639 of Lecture Notes in Computer Science, SpringerVerlag, pp. 312321. [ bib  link ] 
[204]  Bodlaender, H. L., Fellows, M. R., Langston, M. A., Ragan, M. A., Rosamond, F. A., and Weyer, M. Quadratic kernelization for convex recoloring of trees. In Proceedings of Computing and Combinatorics, 13th Annual International Conference, COCOON'07 (2007), G. Lin, Ed., vol. 4598 of Lecture Notes in Computer Science, SpringerVerlag, pp. 8696. [ bib  link ] 
[205]  Burrage, K., EstivillCastro, V., Fellows, M. R., Langston, M. A., Mac, S., and Rosamond, F. A. The undirected feedback vertex set problem has a poly(k) kernel. In Proceedings of Parameterized and Exact Computation, Second International Workshop, IWPEC'06 (2006), H. L. Bodlaender and M. A. Langston, Eds., vol. 4169 of Lecture Notes in Computer Science, SpringerVerlag, pp. 192202. [ bib  link ] 
[206]  Fellows, M. The lost continent of polynomial time. In Proceedings of Parameterized and Exact Computation, Second International Workshop, IWPEC'06 (2006), vol. 4169 of Lecture Notes in Computer Science, SpringerVerlag, p. 276 – 277. [ bib  link ] 
[207]  EstivillCastro, V., Fellows, M. R., Langston, M. A., and Rosamond, F. A. Fixedparameter tractability is polynomialtime extremal structure theory I: The case of max leaf. In Algorithms and Complexity in Durham 2005  Proceedings of the First ACiD (2005), H. Broersma, M. J. 0002, and S. Szeider, Eds., vol. 4 of Texts in Algorithmics, King's College, London, pp. 141. [ bib  link ] 
[208] 
Alber, J., Fellows, M. R., and Niedermeier, R.
Polynomialtime data reduction for dominating set.
Journal of the ACM 51, 3 (2004), 363384.
[ bib 
link ]
We prove that Dominating Set restricted to planar graphs has a kernel of linear size, achieved by two easytoimplement reduction rules. First experiments indicate the practical potential of these rules. Thus, this work seems to open up a new way of coping with one of the most important problems in graph theory and combinatorial optimization.

[209]  AbuKhzam, F. N., Collins, R. L., Fellows, M. R., Langston, M. A., Suters, W. H., and Symons, C. T. Kernelization algorithms for the vertex cover problem: Theory and experiments. In Proceedings of the sixth Workshop on Algorithm Engineering and Experiments and the first Workshop on Analytic Algorithmics and Combinatorics ALENEX'04 (2004), L. Arge, G. F. Italiano, and R. Sedgewick, Eds., Siam Proceedings Series, Society of Industrial and Applied Mathematics, pp. 6269. [ bib ] 
[210]  Chor, B., Fellows, M., and Juedes, D. W. Linear kernels in linear time, or how to save k colors in O(n^{2}) steps. In GraphTheoretic Concepts in Computer Science, 30th International Workshop WG'04 (2004), J. Hromkovic, M. Nagl, and B. Westfechtel, Eds., vol. 3353 of Lecture Notes in Computer Science, SpringerVerlag, pp. 257269. [ bib  link ] 
[211]  Alber, J., Fellows, M. R., and Niedermeier, R. Efficient data reduction for DOMINATING SET: A linear problem kernel for the planar case. In Proceedings of the 8th Scandinavian Workshop on Algorithm Theory SWAT'02 (2002), M. Penttonen and E. M. Schmidt, Eds., vol. 2368 of Lecture Notes in Computer Science, SpringerVerlag, pp. 150159. [ bib  link ] 
[212]  Fellows, M. R., McCartin, C., Rosamond, F. A., and Stege, U. Coordinatized kernels and catalytic reductions: An improved FPT algorithm for max leaf spanning tree and other problems. In Proceedings Foundations of Software Technology and Theoretical Computer Science, 20th Conference, FST TCS'00 (2000), S. Kapoor and S. Prasad, Eds., vol. 1974 of Lecture Notes in Computer Science, SpringerVerlag, pp. 240251. [ bib  link ] 
[213]  Bodlaender, H. L., Fellows, M. R., and Hallett, M. T. Beyond NPcompleteness for problems of bounded width: Hardness for the W hierarchy. In Proceedings of the 26th Annual ACM Symposium on Theory of Computing, STOC'94 (1994), ACM Press, pp. 449458. [ bib  link ] 
The Complexity of Approximation  
[214] 
Cai, L., Fellows, M., Juedes, D., and Rosamond, F.
On the efficiency of polynomialtime approximation.
Theory of Computing Systems 41, 3 (2007), 459477.
[ bib 
link ]
We offer a number of results concerning the problems Planar TMIN, Planar TMAX and Planar MPSAT defined by Khanna and Motwani: (1) We show that each of these problems of approximation, naturally parameterized by k = 1/ε, is hard for W[1], and thus unlikely that they admit EPTASs. (2) We show that there are EPTASs for some subproblems described by syntactic restrictions, and establish some limits on how far these positive results can be extended.

[215]  Downey, R. G., Fellows, M. R., and McCartin, C. Parameterized approximation problems. In Proceedings of Parameterized and Exact Computation, Second International Workshop, IWPEC'06 (2006), H. L. Bodlaender and M. A. Langston, Eds., vol. 4169 of Lecture Notes in Computer Science, Springer, pp. 121129. [ bib ] 
The Complexity of Logic Problems  
[216] 
Fellows, M., Szeider, S., and Wrightson, G.
On finding short resolution refutations and small unsatisfiable
subsets.
Theoretical Computer Science 351 (2006), 351359.
[ bib 
link ]
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 W[1]. Our results remain true if restricted to 3SAT formulas and/or to various restricted versions of resolution including treelike resolution, input resolution, and readonce resolution. Applying a metatheorem of Frick and Grohe, we show that restricted to classes of locally bounded treewidth the considered problems are FPT. Hence, the problems are fixedparameter tractable for planar CNF formulas and CNF formulas of bounded genus, kSAT formulas with bounded number of occurrences per variable, and CNF formulas of bounded treewidth.

[217]  Fellows, M., Szeider, S., and Wrightson, G. On finding short resolution refutations and small unsatisfiable subsets. In Proceedings of the First International Workshop on Parameterized and Exact Computation IWPEC'04 (2004), vol. 3162 of Lecture Notes in Computer Science, SpringerVerlag, pp. 223234. [ bib  link ] 
[218]  Downey, R., and Fellows, M. Index sets and parametric reductions. Archive for Mathematical Logic 40, 5 (2001), 329348. [ bib  link ] 
[219]  Fellows, M., Downey, R., Kapron, B., Hallett, M., and Wareham, H. T. The parameterized complexity of some problems in logic and linguistics. In Proceedings of Symposium on Logical Foundations of Computer Science (LFCS) (1994), vol. 813 of Lecture Notes in Computer Science, SpringerVerlag, pp. 89  100. [ bib ] 
Scheduling Problems  
[220]  Fellows, M., and McCartin, C. On the parameterized complexity of minimizing tardy tasks. Theoretical Computer Science A 298 (2003), 317324. [ bib ] 
[221]  Bodlaender, H., and Fellows, M. On the complexity of kprocessor scheduling. Operations Research Letters 18 (1995), 93 – 98. [ bib  link ] 
[222]  Fellows, M., and Langston, M. A. Processor utilization in a linearly connected parallel processing system. IEEE Transactions on Computers 37 (1988), 594 – 603. [ bib ] 
Combinatorics  
[223]  Fellows, M., Flum, J., Hermelin, D., Müller, M., and Rosamond, F. Parameterized complexity via combinatorial circuits. In Algorithms and Complexity in Durham 2007, Proceedings of the third ACiD Workshop (2007), H. Broersma, S. Dantchev, M. Johnson, and S. Szeider, Eds., vol. 9 of Texts in Algorithmics, College Publications London, pp. 5567. [ bib  link ] 
[224]  Fellows, M., Hell, P., and Seyffarth, K. Constructions of dense planar networks. Networks 32 (1998), 275281. [ bib ] 
[225]  Alon, N., Fellows, M., and Hare, D. O. Vertex transversals that dominate. Journal of Graph Theory 21 (1996), 2132. [ bib  link ] 
[226]  Fellows, M., Hell, P., and Seyffarth, K. Large planar graphs with given diameter and maximum degree. Discrete Applied Math 61 (1995), 133153. [ bib ] 
[227]  Campbell, L., Carlsson, G. E., Dinneen, M. J., Faber, V., Fellows, M., Langston, M. A., Moore, J. W., Mullhaupt, A. P., and Sexton, H. B. Small diameter symmetric networks from linear groups. IEEE Transactions on Computers 40 (1992), 218220. [ bib ] 
[228]  Barefoot, C. A., Clark, L. H., Douthett, J., Entringer, R. C., and Fellows, M. R. Cycles of length 0 modulo 3 in graphs. Annals of Discrete Mathematics (1991), 87101. An earlier paper was presented at Graph theory, Combinatorics, and Applications, Volume 1. Proceedings of the Sixth Quadrennial International Conference on the Theory and Applications of Graphs. [ bib ] 
[229]  Dinneen, M., Faber, V., and Fellows, M. Algebraic constructions of efficient broadcast networks. In Proceedings of the Ninth International Symposium on Applied Algebra, Algebraic Algorithms and ErrorCorrecting Codes (AAECC'91) (1991), H. F. Mattson, T. Mora, and T. Rao, Eds., vol. 539 of Lecture Notes in Computer Science, SpringerVerlag, pp. 152158. [ bib ] 
[230]  Fellows, M., and Kleitman, D. J. Transversals of vertex partitions in graphs. SIAM Journal of Discrete Mathematics 3 (1990), 206215. [ bib ] 
[231]  Fellows, M., and Kleitman, D. J. Radius and diameter in manhattan lattices. Discrete Mathematics 73 (1989), 119125. [ bib ] 
Automata Theory  
[232]  Bodlaender, H. L., Evans, P. A., and Fellows, M. R. Finitestate computability of annotations of strings and trees. In Proceedings of the 7th Annual Symposium on Combinatorial Pattern Matching: CPM 2006 (1996), D. S. Hirschberg and E. W. Myers, Eds., vol. 1075 of Lecture Notes in Computer Science, Springer, pp. 384391. [ bib ] 
[233]  Abrahamson, K. R., and Fellows, M. R. Finite automata, bounded treewidth and wellquasiordering. In Proceedings of the Joint Summer Research Conference on Graph Minors: Graph Structure Theory, Seattle, June, 1991 (1993), N. Robertson and P. Seymour, Eds., vol. 147 of Contemporary Mathematics, American Mathematical Society, pp. 539564. [ bib ] 
[234]  Fellows, M., and Langston, M. An analogue of the MyhillNerode theorem and its use in computing finitebasis characterizations. In Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, FOCS'89 (Research Triangle Park, NC) (1989), IEEE Computer Society Press, pp. 520525. [ bib ] 
Classical Complexity Theory  
[235] 
Bodlaender, H., Fellows, M., and Thilikos, D.
Derivation of algorithms for cutwidth and related graph layout
parameters.
Journal of Computer and System Sciences 75 (2009).
[ bib ]
This paper shows algorithms for graph parameters that ask for a linear ordering of the vertices of the graph. Constructive linear time algorithms for the fixed parameter versions of the problems have been published for cutwidth, pathwidth, and directed or weighted variants of these and other problems. However, the algorithms have complicated technical details. This paper attempts to present ideas in these algorithms in a more easily accessible manner, by showing that the algorithms can be obtained by a stepwise modification of a nondeterministic algorithm. The methodology is applied to rederive known results for the cutwidth and the pathwidth problem, and obtain new results for variants.

[236] 
Fellows, M., Rosamond, F., Rotics, U., and Szeider, S.
Cliquewidth is NPComplete.
SIAM Journal on Discrete Mathematics (SIDMA) 23, 2 (2009).
A preliminary and shortened version of this paper appeared in the
proceedings of STOC 2006; 38th ACM Symposium on Theory of Computing, Seattle,
Washington, USA, pp. 354—362, ACM Press, 2006. This paper combines the
results of the technical reports: Proving NPHardness for CliqueWidth I:
Nonapproximability of Sequential Cliquewidth, and, Proving NPHardness for
CliqueWidth II: Nonapproximability of Cliquewidth; Electronic Colloquium
on Computational Complexity (ECCC).
[ bib 
link 
link ]
Cliquewidth 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 secondorder quantification on vertex sets, that includes NPhard problems) can be solved efficiently for graphs of certified small cliquewidth. We show that the cliquewidth 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 cliquewidth of G is at most k is NPcomplete. This solves a problem that has been open since the introduction of cliquewidth in the early 1990s

[237]  Abrahamson, K. R., Fellows, M. R., and Wilson, C. B. Parallel selfreducibility. In Proceedings of Computing and Information ICCI'92, Fourth International Conference on Computing and Information (1992), W. W. Koczkodaj, P. E. Lauer, and A. A. Toptsis, Eds., IEEE Computer Society, pp. 6770. [ bib ] 
[238]  Fellows, M. R., and Koblitz, N. Selfwitnessing polynomialtime complexity and certificates for primality. In Proceedings of the 7th Annual Conference on Structure in Complexity Theory, CSCT'92 (1992), IEEE Computer Society Press, pp. 107110. [ bib  link ] 
[239] 
Abrahamson, K., Fellows, M. R., Langston, M. A., and Moret, B. M. E.
Constructive complexity.
Discrete Applied Mathematics and Combinatorial Operations
Research and Computer Science 34 (1991), 316.
[ bib ]
Robinson and Seymour have provided tools for classifying decision problems as solvable in polynomial time that are powerful and widely applicable, yet inherently nonconstructive. These developments challenge the view that equates tractability with polynomial time solvability, since the existence of an inaccessible algorithm is of very little help in solving a problem. In this paper, we attempt to provide the foundations for a constructive theory of complexity, in which membership of a problem in some complexity class indeed implies that we can find out how to solve that problem within the stated bounds. Our approach is based on relations, rather than on sets; we make much use of selfreducibility and oracle machines, both conventional and "blind,".

[240]  Fellows, M. R., and Langston, M. A. Fast search algorithms for layout permutation problems. Integration, the VLSI Journal 12, 3 (1991), 321  337. [ bib ] 
[241]  Fellows, M. R., and Langston, M. A. On search, decision and the efficiency of polynomialtime algorithms. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing, STOC'89 (1989), ACM SIGACT, ACM Press, pp. 501512. [ bib  link ] 
[242]  Fellows, M. R., and Langston, M. A. Nonconstructive advances in polynomialtime complexity. Information Processing Letters 26, 3 (1987), 157162. [ bib ] 
[243]  Fellows, M. R., and Langston, M. A. Fast selfreduction algorithms for combinatorial problems of VLSI design. In Proceedings of the 3rd Aegean Workshop on Computing: VLSI Algorithms and Architectures, AWOC'88. Corfu, Greece (1988), J. H. Reif, Ed., vol. 319 of LNCS, SpringerVerlag, pp. 278287. [ bib ] 
Stringology  
[244]  Fellows, M. R., Fomin, F. V., Lokshtanov, D., Losievskaja, E., Rosamond, F. A., and Saurabh, S. Distortion is fixed parameter tractable. In Proceedings of ICALP 2009 (Track A) (2009), pp. 463474. [ bib  link ] 
[245] 
Fellows, M., Fomin, F., Lokshtanov, D., Losievskaja, E., Rosamond, F. A.,
and Saurabh, S.
Parameterized lowdistortion embeddings  graph metrics into lines
and trees.
Tech. rep., 2009.
Manuscript.
[ bib ]
We describe algorithms for finding a low distortion noncontracting embedding of M into line and tree metrics. We give an O(nd^{4}(2d+1)^{2d}) time algorithm that for an unweighted graph metric M and integer d either constructs an embedding of M into the line with distortion at most d, or concludes that no such embedding exists. We find the result surprising, because the considered problem bears a strong resemblance to the notoriously hard Bandwidth Minimization problem which does not admit any FPT algorithm unless an unlikely collapse of parameterized complexity classes occurs. We show that our algorithm can also be applied to construct small distortion embeddings of weighted graph metrics. The running time of our algorithm is O(n(dW)^{4}(2d+1)^{2dW}) where W is the largest edge weight of the input graph. We also show that deciding whether a weighted graph metric M(G) with maximum weight W < V(G) can be embedded into the line with distortion at most d is NPComplete for every fixed rational d >=2. This rules out any possibility of an algorithm with running time O((nW)^{h(d)}) where h is a function of d alone. We generalize the result on embedding into the line by proving that for any tree T with maximum degree Δ, embedding of M into a shortest path metric of T is FPT, parameterized by (Δ,d).

[246] 
Fellows, M. R., Gramm, J., and Niedermeier, R.
On the parameterized intractability of closest substring and related
problems.
In Proceedings of the 19th Annual Symposium on Theoretical
Aspects of Computer Science, STACS'02 (2002), H. Alt and A. Ferreira,
Eds., vol. 2285 of LNCS, SpringerVerlag, pp. 262273.
[ bib 
link ]
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) for any function f and constant c independent of k. Our result supports the intuition that Closest Substring is computationally much harder than the special case of Closest String, although both problems are NPcomplete 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 significance in computational biology.

[247]  Bodlaender, H. L., Evans, P. A., and Fellows, M. R. Finitestate computability of annotations of strings and trees. In Proceedings of the 7th Annual Symposium on Combinatorial Pattern Matching: CPM'96 (1996), D. S. Hirschberg and E. W. Myers, Eds., vol. 1075 of Lecture Notes in Computer Science, Springer, pp. 384391. [ bib ] 
[248]  Bodlaender, H. L., Downey, R. G., Fellows, M. R., and Wareham, H. T. The parameterized complexity of sequence alignment and consensus. Theoretical Computer Science 147, 1&2 (1995), 3154. [ bib  link ] 
[249]  Bodlaender, H. L., Downey, R. G., Fellows, M. R., Hallett, M. T., and Wareham, H. T. Parameterized complexity analysis in computational biology. Computer Applications in the Biosciences 11, 1 (1995), 4957. [ bib  link ] 
[250]  Bodlaender, H. L., Downey, R. G., Fellows, M. R., and Wareham, H. T. The parameterized complexity of sequence alignment and consensus. In Combinatorial Pattern Matching, 5th Annual Symposium, CPM'94 (1994), M. Crochemore and D. Gusfield, Eds., vol. 807 of Lecture Notes in Computer Science, Springer, pp. 1530. [ bib ] 