# My publications, in BibTeX format

@book{MegaMath_a,

author = {Nancy Casey and Michael R. Fellows},

title = {This is Mega-Mathematics!},

publisher = {Los Alamos National Labs},

year = {1992},

note = {Available at http://www.c3.lanl..gov/~captors/mega-math. See also www.ccs3.lanl.gov/mega-math/write.html},

abstract = {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.}

}

@book{Unplugged1,

author = {Tim Bell and Michael R. Fellows and Ian Witten},

title = {Computer Science Unplugged … offline activities and games for all ages: Teacher Edition},

publisher = {Computer Science Unplugged},

year = {1996},

abstract = {Many important topics in computer science can be taught without using computers at all. This series of activities

unplugs computer science by providing off-line 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.},

note = {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.}

}

@book{Unplugged2,

author = {Michael R. Fellows and Tim Bell and Ian Witten},

title = {Computer Science Unplugged … offline activities and games for all ages: Original Activities Book},

publisher = {Computer Science Unplugged},

year = {1996},

abstract = {There are currently two versions of the book. This original edition is aimed for people with some technical interest.

This 232-page 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.}

}

@book{ParameterizedComplexity,

author = {Rodney G. Downey and Michael R. Fellows},

title = {Parameterized Complexity},

publisher = {Springer-Verlag},

year = {1999},

note = {530 pp.}

}

@inproceedings{HermelinFellowsRosamond2009,

author = {Michael R. Fellows and

Danny Hermelin and

Frances A. Rosamond},

title = {Well-Quasi-Ordering Bounded Treewidth Graphs},

booktitle = {Proceedings of International Workshop on Parameterized and Exact Computation, IWPEC’09},

year = {2009},

publisher = {Springer-Verlag},

series = {Lecture Notes in Computer Science},

note = {To Appear},

url = {http://www.mrfellows.net/papers/C98-wqo-iwpec.pdf}

}

@article{CattellDinneenFellows2001,

title = {Forbidden minors to graphs with small feedback sets},

author = {Kevin Cattell and Michael J. Dinneen and Michael R. Fellows},

journal = {Discrete Mathematics},

year = {2001},

number = {1-3},

volume = {230},

pages = {215–252},

url = {http://www.mrfellows.net/papers/CDF01_MinorsSmallFVS.pdf}

}

@article{CattellDinneenDowneyFellowsLangston2000,

title = {On Computing Graph Minor Obstruction Sets},

author = {Kevin Cattell and Michael J. Dinneen and Rodney G. Downey

and Michael R. Fellows},

journal = {Theoretical Computer Science},

year = {2000},

number = {1},

volume = {233},

pages = {107–127},

url = {http://www.mrfellows.net/papers/J48-TCS-2000.pdf}

}

@article{CourcelleDowneyFellows1997,

author = {B. Courcelle and R. G. Downey and M. R. Fellows},

title = {A Note on the Computability of Graph Minor Obstruction Sets

for Monadic Second Order Ideals},

abstract = {The major results of Robertson and Seymour on graph

well-quasi-ordering 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

second-order logic.},

journal = {Journal of Universal Computer Science},

volume = {3},

number = {11},

pages = {1194–1198},

year = {1997},

url = {http://www.mrfellows.net/papers/J42-noteGMOS.pdf}

}

@article{CattellDinneenFellows1996a,

author = {Kevin Cattell and Michael J. Dinneen and Michael R.

Fellows},

title = {A simple linear-time algorithm for finding

path-decompositions of small width},

journal = {Information Processing Letters},

pages = {197–203},

year = {1996},

number = {4},

volume = {57},

publisher = {North-Holland Publishing Company},

abstract = {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

path-decomposition 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.},

url = {http://www.mrfellows.net/papers/CDF96_PathDecompOfSmallWidth.pdf}

}

@techreport{CattellDinneenFellows1996b,

title = {Forbidden minors to graphs with small feedback sets},

author = {Kevin Cattell and Michael J. Dinneen and Michael R. Fellows},

note = {Preprint. Journal publication is “Discrete Mathematics” (2000),},

year = {1996},

url = {http://www.mrfellows.net/papers/J52-preprint96}

}

@article{FellowsKratochvilMiddendorfPfeiffer1995,

author = {M. Fellows and J. Kratochvil and M. Middendorf and F. Pfeiffer},

title = {The Complexity of Induced Minors and Related Problems},

journal = {Algorithmica},

volume = {13},

number = {3},

pages = {266–282},

publisher = {Springer-Verlag, New York, Inc.},

year = {1995},

abstract = {The computational complexity of a number of problems

concerning induced structures in graphs is studied, and

compared with the complexity of corresponding problems

concerning non-induced 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 NP-complete for planar graphs, (2) for every

fixed graph H, induced H-minor testing can be

accomplished for planar graphs $O(n)$, and (3) there

are graphs H for which induced H-minor testing is

NP-complete 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.},

url = {http://www.mrfellows.net/papers/J27-inducedMinors-95.ps}

}

@inproceedings{CattellDinneenFellows1995,

author = {Kevin Cattell and Michael J. Dinneen and Michael R. Fellows},

title = {Obstructions to Within a Few Vertices or Edges of Acyclic},

abstract = {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 cycle-cover graphs

based on the two well-known problems: $k$-Feedback Vertex

Set and k-Feedback 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.},

booktitle = {Proceedings of the 4th International Workshop on

Algorithms and Data Structures, WADS’95},

pages = {415–427},

year = {1995},

volume = {955},

series = {Lecture Notes in Computer Science},

editor = {Selim G. Akl and Frank Dehne and J{\”o}rg-R{\”u}diger

Sack and Nicola Santoro},

publisher = {Springer-Verlag},

url = {http://www.mrfellows.net/papers/C29-Acyclic-WADS95.ps}

}

@article{FellowsLangston1994,

author = {Michael R. Fellows and Michael A. Langston},

title = {On search, decision and the efficiency of polynomial-time

algorithms},

journal = {Journal of Computer and System Sciences},

pages = {769–779},

year = {1994},

url = {http://www.mrfellows.net/papers/FL89_Search,Decision,Efficiency.pdf}

}

@inproceedings{AbrahamsonFellows1993a,

title = {Finite Automata, Bounded Treewidth and Well-Quasiordering},

author = {Karl R. Abrahamson and Michael R. Fellows},

publisher = {American Mathematical Society },

editor = {N. Robertson and P. Seymour },

booktitle = {Proceedings of the Joint Summer Research Conference on

Graph Minors: Graph Structure Theory, Seattle, June, 1991},

series = {Contemporary Mathematics},

volume = {147},

year = {1993},

pages = {539–564}

}

@article{FellowsLangston1992,

author = {Michael R. Fellows and Michael A. Langston},

title = {On Well-Partial-Order Theory and Its Application to

Combinatorial Problems of {VLSI} Design},

journal = {SIAM Journal on Discrete Mathematics},

volume = {5},

number = {1},

pages = {117–126},

year = {1992}

}

@inproceedings{Fellows1989,

author = {Michael R. Fellows},

title = {The {R}obertson-{S}eymour Theorems: {A} Survey of

Applications},

booktitle = {CMGA: Graphs and Algorithms: Contemporary Mathematics},

volume = {89},

publisher = {AMS},

year = {1989},

pages = {1–18}

}

@article{BrownFellowsLangston1989,

author = {D. J. Brown and M. R. Fellows and M. A. Langston},

title = {Polynomial-Time Self-Reducibility: Theoretical Motivations

and Practical Results},

journal = {International Journal of Computer Mathematics},

volume = {31},

year = {1989},

pages = {1–9}

}

@article{FellowsStueckle1989,

author = {M. R. Fellows and S. Stueckle},

title = {The Immersion Order, Forbidden Subgraphs and the Complexity

of Network Integrity},

journal = {Journal of Combinatorial Mathematics and Combinatorial Computing},

volume = {6},

year = {1989},

pages = {23–32}

}

@inproceedings{FellowsLangston1989a,

author = {M. Fellows and M. Langston},

title = {An analogue of the {M}yhill-{N}erode theorem and its use in

computing finite-basis characterizations},

booktitle = {Proceedings of the 30th Annual IEEE Symposium on

Foundations of Computer Science, FOCS’89},

pages = {520–525},

year = {1989},

publisher = {IEEE Computer Society Press},

abstract = {A theorem is proved that is a graph-theoretic analog of the Myhill-Nerode 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.}

}

@inproceedings{FellowsKinnersleyLangston1989,

author = {M. Fellows and N.G. Kinnersley and M.A. Langston},

title = {Finite-Basis Theorems and a Computation-Integrated

Approach to Obstruction Set Isolation},

booktitle = {Proceedings of the Third Conference on Computers and

Mathematics},

pages = {37–45},

year = {1989},

publisher = {Springer-Verlag},

editor = {E. Kaltofen and S. M. Watt}

}

@article{FellowsLangston1988,

author = {Michael R. Fellows and Michael A. Langston},

title = {Nonconstructive tools for proving polynomial-time decidability},

journal = {Journal of the ACM},

pages = {727–739},

year = {1988},

number = {3},

volume = {35},

publisher = {ACM Press},

address = {New York},

url = {http://www.mrfellows.net/papers/FL88_NonconstructiveTools.pdf}

}

@inproceedings{FellowsLangston1988a,

author = {Michael R. Fellows and Michael A. Langston},

title = {Layout permutation problems and well-partially-ordered sets},

booktitle = {Proceedings of the fifth MIT conference on Advanced

research in VLSI},

year = {1988},

pages = {315–327},

publisher = {MIT Press},

address = {Cambridge, MA, USA}

}

@inproceedings{FellowsLangston1988b,

author = {Michael R. Fellows and Michael A. Langston},

title = {Fast self-reduction algorithms for combinatorial problems

of {VLSI} design},

booktitle = {Proceedings of the 3rd Aegean Workshop on Computing:

VLSI Algorithms and Architectures, AWOC’88. Corfu, Greece},

pages = {278–287},

year = {1988},

volume = {319},

series = {Lecture Notes in Computer Science},

editor = {J. H. Reif},

publisher = {Springer-Verlag}

}

@article{FellowsLangston1987,

author = {Michael R. Fellows and Michael A. Langston},

title = {Nonconstructive advances in polynomial-time complexity},

journal = {Information Processing Letters},

pages = {157–162},

year = {1987},

number = {3},

volume = {26},

publisher = {North-Holland Publishing Company}

}

@inproceedings{BryantFellowsKinnersleyLangston1987,

author = {R. L. Bryant, N. G. Kinnersley, M. R. Fellows and

M. A. Langston},

title = {On Finding Obstruction Sets and Polynomial-Time Algorithms

for Gate Matrix Layout},

booktitle = {Proceedings of the 25th Allerton Conference on

Communication, Control and Computing},

pages = {397–398},

year = {1987}

}

@article{FellowsFominGutin2010,

title = {Special {I}ssue on {P}arameterized {C}omplexity},

author = {Michael R. Fellows and Fedor V. Fomin and Gregory Gutin},

journal = {Discrete Optimization},

year = {2010},

note = {To Appear}

}

@inproceedings{Fellows2009a,

title = {The Complexity Ecology of Parameters: Some New Developments and Research Directions},

author = {Michael R. Fellows},

booktitle = {Proceedings of IWOCA},

publisher = {Springer-Verlag},

year = {2009},

note = {To Appear},

series = {Lecture Notes in Computer Science},

url = {http://www.mrfellows.net/papers/C101-IWOCA-09.pdf}

}

@article{DowneyFellowsLangston2008,

author = {R. Downey and M. Fellows and M. Langston},

title = {The {C}omputer {J}ournal {S}pecial {I}ssue on {P}arameterized {C}omplexity: {F}oreword by the {G}uest {E}ditors},

journal = {The Computer Journal},

year = {2008},

volume = {51},

number = {1},

pages = {1–6},

note = {{The Computer Journal} published a two-issue 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. },

url = {http://www.mrfellows.net/papers/J71-CJforward08.pdf}

}

@techreport{BodlaenderDemaineFellowsGuoHermelinLokshtanovMüllerRamanvanRooijRosamond2008,

author = {Hans L. Bodlaender and Erik D. Demaine and Michael R. Fellows and Jiong Guo and Danny Hermelin and Daniel

Lokshtanov and Moritz Müller and Venkatesh Raman, Johan van Rooij and Frances A. Rosamond},

year = 2008,

title = {Open Problems in Parameterized and Exact Computation from IWPEC 2008},

number = {UU-CS-2008-017},

institution = {Department of Information and Computing Sciences, Utrecht University},

url = {http://www.mrfellows.net/papers/OpenProbsIWPEC08.pdf}

}

@inproceedings{FellowsRosamond2007b,

title = {The Complexity Ecology of Parameters: An Illustration Using

Bounded Max Leaf Number},

author = {Michael R. Fellows and Frances A. Rosamond},

booktitle = {Proceedings of Computation and Logic in the Real World, Third

Conference on Computability in Europe, {C}i{E}, Siena, Italy},

publisher = {Springer},

year = {2007},

volume = {4497},

editor = {S. Barry Cooper and Benedikt L{\”o}we and Andrea Sorbi},

pages = {268–277},

series = {Lecture Notes in Computer Science},

url = {http://www.mrfellows.net/papers/FR07EcologyMaxLeaf.pdf}

}

@inproceedings{FellowsRosamond2007,

author = {M. Fellows and F. Rosamond},

title = {Why Is {P} {N}ot {E}qual to {NP}?},

booktitle = {Computation and Logic in the Real World: Third

Conference on Computability in Europe, CiE 2007: Local Proceedings},

year = {2007},

url = {http://www.mrfellows.net/papers/C73.pdf}

}

@inproceedings{Fellows2006a,

author = {M. Fellows},

title = {The Lost Continent of Polynomial Time},

booktitle = {Proceedings of IWPEC’06},

publisher = {Springer-Verlag},

series = {Lecture Notes in Computer Science},

volume = {4169},

pages = {276 – 277},

year = {2006},

url = {http://www.mrfellows.net/papers/C70-LostContinent.pdf}

}

@inproceedings{DehneFellowsRosamondShaw2004,

title = {Greedy Localization, Iterative Compression, Modeled

Crown Reductions: New {FPT} Techniques, an Improved

Algorithm for Set Splitting, and a Novel 2$k$

Kernelization for Vertex Cover},

author = {Frank K. Dehne and Michael R. Fellows and Frances A.

Rosamond and Peter Shaw},

booktitle = {Proceedings of Parameterized and Exact Computation, First

International Workshop, {IWPEC} 2004, Bergen, Norway},

publisher = {Springer},

year = {2004},

volume = {3162},

editor = {Rodney G. Downey and Michael R. Fellows and Frank K. Dehne},

pages = {271–280},

series = {Lecture Notes in Computer Science},

url = {http://www.mrfellows.net/papers/DFRS04_IterativeCompresCrown.pdf}

}

@inproceedings{Fellows2004,

title = {A Survey of {FPT} Algorithm Design Techniques with an

Emphasis on Recent Advances and Connections to Practical Computing},

author = {Michael R. Fellows},

booktitle = {Proceedings of 12th Annual European

Symposium ESA, Bergen, Norway},

publisher = {Springer-Verlag},

year = {2004},

volume = {3221},

editor = {Susanne Albers and Tomasz Radzik},

pages = {1–2},

series = {Lecture Notes in Computer Science},

url = {http://www.mrfellows.net/papers/C59-SurveyFPTalgDesignESA04.pdf}

}

@article{ChenFellows2003,

author = {J. Chen and M. Fellows},

title = {Foreword from the {G}uest {E}ditors},

journal = {Journal of Computer and System Sciences},

year = {2003},

volume = {67},

pages = {653–654},

note = {Special Issue on Parameterized Complexity,}

}

@inproceedings{Fellows2003,

author = {Michael R. Fellows},

title = {Blow-ups, win/win’s, and crown rules: Some new directions in {FPT}},

booktitle = {Proceedings of the 29th International Workshop on

Graph-Theoretic Concepts in Computer Science, WG’2003, Elspeet, The

Netherlands},

pages = {1–12},

year = {2003},

volume = {2880},

series = {Lecture Notes in Computer Science},

abstract = {This survey reviews the basic notions of parameterized

complexity, and describes some new approaches to designing FPT

algorithms and problem reductions for graph problems.},

editor = {Hans L. Bodlaender},

publisher = {Springer-Verlag},

url = {http://www.mrfellows.net/papers/C52-WG03.pdf}

}

@inproceedings{Fellows2003b,

title = {New Directions and New Challenges in Algorithm Design and

Complexity, Parameterized},

author = {Michael R. Fellows},

booktitle = {Proceedings of Algorithms and Data Structures, 8th International

Workshop {WADS} },

publisher = {Springer-Verlag},

year = {2003},

volume = {2748},

editor = {Frank K. H. A. Dehne and J{\”o}rg-R{\”u}diger Sack and

Michiel H. M. Smid},

pages = {505–520},

series = {Lecture Notes in Computer Science},

url = {http://www.mrfellows.net/papers/C54-wads03.pdf}

}

@inproceedings{Fellows2002b,

title = {Parameterized Complexity: The Main Ideas and Connections to

Practical Computing},

author = {Michael R. Fellows},

publisher = {Springer-Verlag},

year = {2002},

volume = {2547},

booktitle = {Experimental Algorithmics},

editor = {Rudolf Fleischer and Bernard M. E. Moret and Erik Meineche Schmidt},

pages = {51–77},

series = {Lecture Notes in Computer Science},

url = {http://www.mrfellows.net/papers/F02_Practical.pdf}

}

@inproceedings{Fellows2001,

author = {Michael R. Fellows},

title = {Parameterized Complexity: New Developments and

Research Frontiers},

booktitle = {Aspects of Complexity},

year = {2001},

publisher = {De Gruyter},

pages = {51–72},

url = {http://www.mrfellows.net/papers/C44-Kaikoura-2000.pdf}

}

@inproceedings{Fellows2001a,

author = {Michael R. Fellows},

title = {Some New Developments in Parameterized Complexity},

booktitle = {Proceedings of the 12th Australasian Workshop on

Combinatorial Algorithms},

year = {2001},

editor = {Edy Tri Baskoro},

pages = {43–44},

url = {http://www.mrfellows.net/papers/C45-awoca.pdf}

}

@inproceedings{Fellows2001b,

title = {Parameterized Complexity: Main Ideas, Connections to

Heuristics and Research Frontiers},

author = {Michael R. Fellows},

booktitle = {Proceedings of ISAAC},

publisher = {Springer-Verlag},

year = {2001},

volume = {2223},

pages = {291–307},

series = {Lecture Notes in Computer Science},

url = {http://www.mrfellows.net/papers/C46.pdf}

}

@incollection{DowneyFelllowsStege99a,

author = {Rodney G. Downey and Michael R. Fellows and Ulrike Stege},

title = {Parameterized Complexity: {A} Framework for Systematically Confronting Computational Intractability},

booktitle = {Contemporary Trends in Discrete Mathematics: From DIMACS and DIMATIA to the Future},

year = {1999},

volume = {49},

series = {DIMACS Series in Discrete Mathematics and Theoretical Computer Science},

publisher = {DIMACS},

pages = {49–99},

abstract = {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 fixed-parameter 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 $k$-Step 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 $k$-Coloring 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.},

url = {http://www.mrfellows.net/papers/DFS99_Framework.pdf}

}

@techreport{DowneyFellowsStege99b,

author = {Rodney G. Downey and Michael R. Fellows and Ulrike Stege},

title = {Computational {T}ractability: {A} {V}iew From {M}ars},

url = {http://www.mrfellows.net/papers/ViewFromMars.ps},

year = {1999}

}

@inproceedings{DowneyFellows1999,

title = {Parameterized Complexity After (Almost) 10 Years: Review

and Open Questions},

author = {Rodney G. Downey and Michael R. Fellows},

booktitle = {Proceedings of Combinatorics, Computation and Logic,

DMTCS’99 and CATS’99},

publisher = {Springer-Verlag},

address = {Singapore},

year = {1999},

volume = {21},

pages = {1–33},

series = {Australian Computer Science Communications},

url = {http://www.mrfellows.net/papers/DF99_AfterTenYears.pdf}

}

@article{DowneyFellows1995e,

author = {K.. Abrahamson and Rodney G. Downey and Michael R. Fellows},

title = {Fixed-Parameter Tractability and Completeness {IV}: On

Completeness for {W[P]} and {PSPACE} Analogs},

journal = {Annals of Pure and Applied Logic},

volume = {73},

year = {1995},

pages = {235-276},

url = {http://www.mrfellows.net/papers/J31-fpt4-95.pdf}

}

@article{CaiChenDowneyFellows1995a,

title = {On the Structure of Parameterized Problems in {NP}},

author = {Liming Cai and Jianer Chen and Rodney Downey and Michael Fellows},

pages = {38–49},

journal = {Information and Computation},

year = {1995},

volume = {123},

number = {1},

abstract = {Fixed-parameter 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 fixed-parameter tractable and that the

fixed-parameter intractability hierarchy (the $W$-hierarchy) does not

collapse.}

}

@inproceedings{DowneyFellows1995a,

author = {R. G. Downey and M. R. Fellows},

title = {Parameterized Computational Feasibility},

abstract = {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.},

booktitle = {Proceedings of the Second Cornell Workshop on

Feasible Mathematics. Feasible Mathematics II},

editor = {P. Clote and J.. Remmel},

pages = {219–244},

publisher = {Birkh{\”a}user},

address = {Boston},

year = {1995},

url = {http://www.mrfellows.net/papers/C17-feasibility95.ps}

}

@article{DowneyFellows1995b,

author = {Rodney Downey and Michael R. Fellows},

title = {Fixed-Parameter Tractability and Completeness {II}: Completeness for {W[1]}},

journal = {Theoretical Computer Science A},

volume = {141},

year = {1995},

pages = {109-131},

note = {Preliminary versions of some of the results of this paper were presented at the 21st Manitoba Conference on Numerical

Mathematics and Computation, 1991.},

url = {http://www.mrfellows.net/papers/J30-CompletenessII-95.ps}

}

@article{DowneyFellows1995c,

author = {Rodney Downey and Michael R. Fellows},

title = {Fixed-Parameter Tractability and Completeness {I}: Basic Theory},

journal = {Siam Journal of Computing},

volume = {24},

year = {1995},

pages = {873-921},

note = {Preliminary versions of some of the results of this paper were presented at the 21st Manitoba Conference on Numerical

Mathematics and Computation, 1991.},

url = {http://www.mrfellows.net/papers/J29-completeness1-95.ps}

}

@inproceedings{AbrahamsonDowneyFellows1993a,

author = {Karl Abrahamson and Rodney Downey and Michael R. Fellows},

title = {Fixed-Parameter Intractability {II}},

booktitle = {Proceedings of the 10th Symposium on Theoretical Aspects of Computer Sciences, STACS’93},

volume = {665},

year = {1993},

pages = {374-385},

publisher = {Springer-Verlag},

series = {Lecture Notes in Computer Science}

}

@article{FellowsFertinHermelinVialette2010,

title = {Sharp Tractability Borderlines for Finding Connected Motifs

in Vertex-Colored Graphs},

author = {Michael R. Fellows and Guillaume Fertin and Danny Hermelin

and St{\’e}phane Vialette},

journal = {Computer and System Sciences},

year = {2010},

note = {To Appear}

}

@article{FellowsHermelinRosamondVialette2009,

author = {Michael R. Fellows and

Danny Hermelin and

Frances A. Rosamond and

St{\’e}phane Vialette},

title = {On the Parameterized Complexity of Multiple-Interval Graph

Problems},

journal = {Journal of Theoretical Computer Science},

volume = {410},

number = {1},

year = {2009},

pages = {53-61},

url = {http://www.mrfellows.net/papers/J77-TCS-later.pdf}

}

@inproceedings{FellowsGuoKomusiewiczNiedermeierUhlmann2009,

author = {Michael R. Fellows and

Jiong Guo and

Christian Komusiewicz and

Rolf Niedermeier and

Johannes Uhlmann},

title = {Graph-Based Data Clustering with Overlaps},

booktitle = {Proceedings of COCOON},

year = {2009},

pages = {516-526},

publisher = {Springer},

series = {Lecture Notes in Computer Science},

volume = {5609},

url = {http://www.mrfellows.net/papers/C95-overlap-clustering.pdf}

}

@inproceedings{FellowsGuoKanj2009,

author = {Michael R. Fellows and

Jiong Guo and

Iyad Kanj},

title = {The Parameterized Complexity of some Minimum Label Problems},

booktitle = {Proceedings of WG},

year = {2009},

publisher = {Springer-Verlag},

series = {Lecture Notes in Computer Science},

note = {To Appear},

url = {http://www.mrfellows.net/papers/C97.pdf}

}

@inproceedings{FellowsHartmanHermelinLandauRosamondRozenberg2009,

author = {Michael R. Fellows and

Tzvika Hartman and

Danny Hermelin and

Gad M. Landau and

Frances A. Rosamond and

Liat Rozenberg},

title = {Haplotype Inference Constrained by Plausible Haplotype Data},

booktitle = {Proceedings of the of the 20th Combinatorial Pattern Matching conference, CPM},

year = {2009},

pages = {339-352},

url = {http://www.mrfellows.net/papers/C93-Haplotype-CPM09.pdf}

}

@inproceedings{BetzlerFellowsKomusiewiczNiedermeier2008,

title = {Parameterized Algorithms and Hardness Results for Some

Graph Motif Problems},

author = {Nadja Betzler and Michael R. Fellows and Christian

Komusiewicz and Rolf Niedermeier},

booktitle = {Proceedings of Combinatorial Pattern Matching, 19th Annual Symposium,

CPM,},

publisher = {Springer},

year = {2008},

volume = {5029},

editor = {Paolo Ferragina and Gad M. Landau},

pages = {31–43},

series = {Lecture Notes in Computer Science},

url = {http://www.mrfellows.net/papers/C84-motifs.pdf}

}

@inproceedings{FellowsFertinHermelinVialette2007,

title = {Sharp Tractability Borderlines for Finding Connected Motifs

in Vertex-Colored Graphs},

author = {Michael R. Fellows and Guillaume Fertin and Danny Hermelin

and St{\’e}phane Vialette},

booktitle = {Proceedings of Automata, Languages and Programming, 34th International

Colloquium, ICALP},

publisher = {Springer},

year = {2007},

volume = {4596},

editor = {Lars Arge and Christian Cachin and Tomasz Jurdzinski and

Andrzej Tarlecki},

pages = {340–351},

series = {Lecture Notes in Computer Science},

url = {http://www.mrfellows.net/papers/C77-ICALP-07.pdf}

}

@inproceedings{FellowsLangstonRosamondShaw2007,

title = {Efficient Parameterized Preprocessing for Cluster Editing},

author = {Michael R. Fellows and Michael A. Langston and Frances A.

Rosamond and Peter Shaw},

booktitle = {Fundamentals of Computation Theory, 16th International

Symposium, {FCT}, Budapest, Hungary},

publisher = {Springer},

year = {2007},

volume = {4639},

editor = {Erzs{\’e}bet Csuhaj-Varj{\’u} and Zolt{\’a}n {\’E}sik},

pages = {312–321},

series = {Lecture Notes in Computer Science},

url = {http://www.mrfellows.net/papers/C78-FCT07.pdf}

}

@article{FellowsGrammNiedermeier2006,

author = {Michael R. Fellows and Jens Gramm and Rolf Niedermeier},

title = {On The Parameterized Intractability Of Motif Search Problems},

journal = {Combinatorica},

volume = {26},

number = {2},

year = {2006},

pages = {141–167},

publisher = {Springer-Verlag New York, Inc.},

url = {http://www.mrfellows.net/papers/FGN06_MotifSearch.pdf}

}

@article{FellowsHallettStege2003,

author = {M. R. Fellows and M. Hallett and U. Stege},

title = {Analogs \& Duals of the {MAST} Problem for Sequences \& Trees},

journal = {Journal of Algorithms},

volume = {49},

year = {2003},

pages = {192 — 216},

url = {http://www.mrfellows.net/papers/J54-MAST.pdf}

}

@inproceedings{FellowsGrammNiedermeier2002,

author = {Michael R. Fellows and Jens Gramm and Rolf Niedermeier},

title = {On the Parameterized Intractability of Closest Substring

and Related Problems},

abstract = {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 NP-complete and both

possess polynomial time approximation schemes. We also prove

$W[1]$-hardness for other parameterizations in the case of unbounded

alphabet size. Our main $W[1]$-hardness result generalizes to Consensus

Patterns, a problem of similar significance in computational

biology.},

booktitle = {Proceedings of the 19th Annual Symposium on Theoretical

Aspects of Computer Science, STACS’02},

pages = {262–273},

year = {2002},

volume = {2285},

series = {Lecture Notes in Computer Science},

editor = {Helmut Alt and Afonso Ferreira},

publisher = {Springer-Verlag},

url = {http://www.mrfellows.net/papers/C48-stacs02-substrings.pdf}

}

@article{BodlaenderFellowsHallettWarehamWarnow2000,

author = {Hans L. Bodlaender and Michael R. Fellows and Michael T.

Hallett and H. Todd Wareham and Tandy J. Warnow},

title = {The Hardness of Perfect Phylogeny, Feasible Register

Assignment and other problems on Thin Colored Graphs},

journal = {Theoretical Computer Science A},

abstract = {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 NP-Complete.},

volume = {244},

number = {1–2},

pages = {167–188},

year = {2000},

url = {http://www.mrfellows.net/papers/BFHWW00_PhylogenyThinColoredGraphs.pdf}

}

@inproceedings{FellowsHallettKorostenskyStege1998,

author = {M. Fellows and M. T. Hallett and C. Korostensky and U. Stege},

title = {Analogs and Duals of the {MAST} Problem for Sequences and Trees},

abstract = {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 leaf-labels and a

subobject is defined by label-respecting hereditary topological

containment, both of these problems are NP-complete, as are the

analogous problems for sequences (the well-known Longest Common

Subsequence and Shortest Common Supersequence problems). However, when

the trees are restricted by allowing each symbol to occur as a

leaf-label at most once (which we call a phylogenetic tree or p-tree),

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.},

booktitle = {Proceedings of the 6th Annual European Symposium on Algorithms},

editor = {G. Bilardi and G. F. Italiano and A. Pietracaprina and G. Pu cci},

series = {Lecture Notes in Computer Science},

number = {1461},

publisher = {Springer-Verlag, Berlin},

year = {1998},

pages = {103–114},

url = {http://www.mrfellows.net/papers/C36.pdf}

}

@inproceedings{FellowsHallettStege1998,

author = {Michael Fellows and Michael Hallett and Ulrike Stege},

title = {On the multiple gene duplication problem},

abstract = {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.},

booktitle = {Proceedings of the 9th International Symposium on

Algorithms and Computation, ISAAC’98},

pages = {347–356},

year = {1998},

volume = {1533},

series = {Lecture Notes in Computer Science},

editor = {Kyung-Yong Chwa and Oscar H. Ibarra},

publisher = {Springer-Verlag},

url = {http://www.mrfellows.net/papers/C37-multiplegene-ISAAC98.pdf}

}

@article{BaileyCattellFellowsKoopOlafsonOlafsonUpton1996,

author = {I. Bailey and K. Cattell and M. R. Fellows and B. Koop and

R. Olafson and R.W. Olafson and C. Upton},

title = {Approaches to Detection of Distantly Related Proteins by

Database Searches},

journal = {BioTechniques},

volume = {21},

year = {1996},

pages = {1118 — 1125}

}

@article{BodlaenderDowneyFellowsHallettWareham1995,

author = {Hans L. Bodlaender and Rodney G. Downey and Michael R..

Fellows and Michael T. Hallett and Harold T. Wareham},

title = {Parameterized Complexity Analysis in Computational Biology},

journal = {Computer Applications in the Biosciences},

volume = {11},

number = {1},

year = {1995},

pages = {49-57},

url = {http://www.mrfellows.net/papers/BDFHW95CompBio.pdf}

}

@article{BodlaenderDowneyFellowsWareham1995,

author = {Hans L. Bodlaender and Rodney G. Downey and Michael R.

Fellows and Harold T. Wareham},

title = {The Parameterized Complexity of Sequence Alignment and

Consensus},

journal = {Theoretical Computer Science},

volume = {147},

number = {1{\&}2},

year = {1995},

pages = {31-54},

url = {http://www.mrfellows.net/papers/C25-SeqAlign94.pdf}

}

@inproceedings{BodlaenderDowneyFellowsWareham1994,

title = {The Parameterized Complexity of Sequence Alignment and Consensus},

author = {Hans L. Bodlaender and Rodney G. Downey and Michael R.

Fellows and Harold T. Wareham},

booktitle = {Proceedings of Combinatorial Pattern Matching, 5th Annual Symposium,

{CPM} },

publisher = {Springer},

year = {1994},

volume = {807},

editor = {Maxime Crochemore and Dan Gusfield},

pages = {15–30},

series = {Lecture Notes in Computer Science}

}

@article{BodlaenderDowneyFellowsHallettWareham1994,

author = {Hans L. Bodlaender and Rodney G. Downey and Michael R..

Fellows and Michael T. Hallett and Harold T. Wareham},

title = {Parameterized Complexity Analysis in Computational Biology},

journal = {Proceedings of the IEEE Computer Society Workshop on

Shape and Pattern Recognition in Computational Biology},

year = {1994},

pages = {99-116},

publisher = {Plenum Press},

note = {IBM TJ Watson Research Center Publication}

}

@incollection{FellowsHallettWareham1993,

author = {Michael R. Fellows and Michael T. Hallett and H. Todd

Wareham},

title = {{DNA} Physical Mapping: Three Ways Difficult},

booktitle = {Proceedings of the 1st Annual European Symposium on

Algorithms, ESA ’93},

pages = {157–168},

year = {1993},

volume = {726},

series = {Lecture Notes in Computer Science},

editor = {Thomas Lengauer},

publisher = {Springer-Verlag}

}

@inproceedings{BodlaenderFellowsWarnow1992,

author = {Hans L. Bodlaender and Mike R. Fellows and Tandy J. Warnow},

title = {Two Strikes Against Perfect Phylogeny},

booktitle = {Proceedings of the 19th International Colloquium on

Automata, Languages and Programming, ICALP’92},

pages = {273–283},

year = {1992},

volume = {623},

series = {Lecture Notes in Computer Science},

editor = {W. Kuich},

publisher = {Springer-Verlag},

url = {http://www.mrfellows.net/papers/BFW92_Phylogeny.pdf}

}

@article{BetzlerFellowsGuoNiedermeierRosamond2009,

author = {N. Betzler and M. R. Fellows and J. Guo and R. Niedermeier and F. Rosamond},

title = {Fixed-Parameter Algorithms for {K}emeny {R}ankings},

journal = {Theoretical Computer Science},

year = {2009},

note = {Accepted for publication, August 2009, 30 pages},

url = {http://www.mrfellows.net/papers/J81-KemenyRankings09.pdf}

}

@inproceedings{BetzlerFellowsGuoNiedermeierRosamond2009b,

author = {Nadja Betzler and

Michael R. Fellows and

Jiong Guo and

Rolf Niedermeier and

Frances A. Rosamond},

title = {How Similarity Helps to Efficiently Compute {K}emeny {R}ankings},

booktitle = {Proceedings of the 8th International Conference on Autonomous Agents and Multiagent Systems AAMAS},

year = {2009},

pages = {657-664},

url = {http://www.mrfellows.net/papers/C92-Betzler-AAMAS09.pdf}

}

@inproceedings{BetzlerFellowsGuoNiedermeierRosamond2008,

title = {Fixed-Parameter Algorithms for {K}emeny Scores},

author = {Nadja Betzler and Michael R. Fellows and Jiong Guo and

Rolf Niedermeier and Frances A. Rosamond},

booktitle = {Proceedings of Algorithmic Aspects in Information and Management, 4th

International Conference, {AAIM}},

publisher = {Springer-Verlag},

year = {2008},

volume = {5034},

editor = {Rudolf Fleischer and Jinhui Xu},

pages = {60–71},

series = {Lecture Notes in Computer Science},

url = {http://www.mrfellows.net/papers/C81-AAIM08.pdf}

}

@inproceedings{BetzlerFellowsGuoNiedermeierRosamond2008a,

title = {Computing {K}emeny {R}ankings, Parameterized by the Average {K-T}

Distance},

author = {Nadja Betzler and Michael R. Fellows and Jiong Guo and

Rolf Niedermeier and Frances A. Rosamond},

booktitle = {Proceedings of the 2nd International Workshop on

Computational Social Choice, COMSOC},

year = {2008},

url = {http://www.mrfellows.net/papers/C87-AveKT-COMSOC08.pdf}

}

@article{ChristianFellowsRosamondSlinko2007,

author = {R. Christian and M. R. Fellows and F. Rosamond and A. Slinko},

title = {On the Complexity of Lobbying in Multiple Referenda},

journal = {Review of Economic Design},

year = {2007},

volume = {11},

pages = {217–224},

url = {http://www.mrfellows.net/papers/J68-CFRS-RevEcD07.pdf}

}

@techreport{FellowsRosamondSlinko2008,

author = {M. R. Fellows and F. Rosamond and A. Slinko},

title = {Sensing {G}od’s {W}ill is Fixed Parameter Tractable},

note = {University of Auckland, NZ Mathematics Research Report, 9 pages},

institution = {University of Auckland, New Zealand},

year = {2008},

url = {http://www.mrfellows.net/papers/C103-Slinko-Sensing.pdf}

}

@inproceedings{FellowsHromkovicRosamondSteinova2009a,

title = {Fixed-Parameter Tractability, Relative Kernelization and the Effectivization of Structural Connections},

author = {M. Fellows and J. Hromkovic and F. Rosamond and M. Steinova},

booktitle = {Proceedings of CiE’09},

publisher = {Springer-Verlag},

year = {2009},

note = {To Appear},

series = {Lecture Notes in Computer Science},

url = {http://www.mrfellows.net/papers/C102-Cie09abstract.pdf}

}

@inproceedings{FellowsGuoMoserNiedermeier2009a,

author = {Michael R. Fellows and

Jiong Guo and

Hannes Moser and

Rolf Niedermeier},

title = {A Complexity Dichotomy for Finding Disjoint Solutions of

Vertex Deletion Problems},

booktitle = {Proceedings of MFCS’09},

year = {2009},

pages = {319-330},

publisher = {Springer-Verlag},

series = {Lecture Notes in Computer Science},

volume = {5734},

url = {http://www.mrfellows.net/papers/C99-mfcs09-dichotomy.pdf}

}

@inproceedings{EncisoFellowsGuoKanjRosamondSuchy2009,

author = {R. Enciso and M. R. Fellows and

J. Guo and

I. Kanj and F. Rosamond and A. Suchy},

title = {What Makes Equitable Connected Partition Easy?},

booktitle = {Proceedings of International Workshop of Parameterized and Exact Computation, IWPEC’09},

year = {2009},

publisher = {Springer-Verlag},

series = {Lecture Notes in Computer Science},

note = {To Appear}

}

@inproceedings{FellowsFominLokshtanovRosamondSaurabhVillanger2009,

author = {M. Fellows and

F. V. Fomin and

D. Lokshtanov and

F. Rosamond and

S. Saurabh and Y. Villanger},

title = {Local Search: Is Brute Force Avoidable?},

booktitle = {Proceedings International Joint Conference on Artificial Intelligence, IJCAI’09},

year = {2009},

note = {To Appear},

url = {http://www.mrfellows.net/papers/C94-local-search.pdf}

}

@inproceedings{FellowsFominLokshtanovLosievskajaRosamondSaurabh2009a,

author = {Michael R. Fellows and

Fedor V. Fomin and

Daniel Lokshtanov and

Elena Losievskaja and

Frances A. Rosamond and

Saket Saurabh},

title = {Distortion Is Fixed Parameter Tractable},

booktitle = {Proceedings of ICALP’09 (Track A)},

year = {2009},

pages = {463-474},

url = {http://www.mrfellows.net/papers/C96.pdf}

}

@techreport{FellowsFominLokshtanovLosievskajaRosamondSaurabh2009b,

title = {Parameterized Low-distortion Embeddings – Graph Metrics

into Lines and Trees},

author = {Michael Fellows and Fedor Fomin and Daniel Lokshtanov and

Elena Losievskaja and Frances A. Rosamond and Saket Saurabh},

note = {Manuscript},

year = {2009},

abstract = {We describe algorithms for

finding a low distortion non-contracting 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 NP-Complete for every fixed

rational $d \geq 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 $\Delta$, embedding of $M$

into a shortest path metric of $T$ is FPT, parameterized by

$(\Delta,d)$.}

}

@inproceedings{FellowsHermelinMullerRosamond2008,

title = {A Purely Democratic Characterization of {W}[1]},

author = {Michael R. Fellows and Danny Hermelin and Moritz

M{\”u}ller and Frances A. Rosamond},

booktitle = {Proceedings of Parameterized and Exact Computation, Third

International Workshop IWPEC’08},

publisher = {Springer-Verlag},

year = {2008},

volume = {5018},

editor = {Martin Grohe and Rolf Niedermeier},

pages = {103–114},

series = {Lecture Notes in Computer Science},

url = {http://www.mrfellows.net/papers/C82-democratic.pdf}

}

@inproceedings{BodlaenderDowneyFellowsHermelin2008,

title = {On Problems Without Polynomial Kernels},

author = {Hans L. Bodlaender and Rodney G. Downey and Michael R.

Fellows and Danny Hermelin},

booktitle = {Automata, Languages and Programming, 35th International

Colloquium, ICALP’08, Part I: Track A: Algorithms, Automata, Complexity, and

Games},

publisher = {Springer},

year = {2008},

volume = {5125},

editor = {Luca Aceto and Ivan Damg{\aa}rd and Leslie Ann Goldberg

and Magn{\’u}s M. Halld{\’o}rsson and Anna Ing{\’o}lfsd{\’o}ttir and

Igor Walukiewicz},

pages = {563–574},

series = {Lecture Notes in Computer Science},

url = {http://www.mrfellows.net/papers/C85-ICALP-08.pdf}

}

@article{FellowsFlumHermelinMullerRosamond2008,

title = {W-Hierarchies Defined by Symmetric Gates},

author = {M. Fellows and J. Flum and D. Hermelin and

M. Muller and F. Rosamond},

journal = {Theory of Computing Systems},

abstract = {Originally defined via the weighted

satisfiability problem for Boolean circuits, the classes of the W-hierarchy are

the most important classes of intractable problems in parameterized

complexity. Here, besides the Boolean

connectives, we consider connectives such as majority, not-all-equal,

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 W-hierarchy

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.},

year = {2008},

url = {http://www.mrfellows.net/papers/J74-TOCS-comb-circs-revised.pdf}

}

@inproceedings{FellowsFernau2008a,

title = {Facility Location Problems: A Parameterized View},

author = {Michael Fellows and Henning Fernau},

booktitle = {Proceedings of AAIM’08},

pages = {188–199},

year = {2008},

publisher = {Springer},

series = {Lecture Notes in Computer Science},

volume = {5034},

url = {http://www.mrfellows.net/papers/C83-Facilities-AAIM08.pdf}

}

@inproceedings{FellowsFominLokshtanovRosamondSaurabhSzeiderThomassen2007a,

title = {On the Complexity of Some Colorful Problems Parameterized by Treewidth. (invited paper) },

author = {M. Fellows and F. V. Fomin and D. Lokshtanov and F. Rosamond and S. Saurabh and S. Szeider and C. Thomassen.

},

booktitle = {Proceedings of First International Conference on Combinatorial Optimization and Applications COCOA’07},

pages = {366–377},

year = {2007},

publisher = {Springer-Verlag},

series = {Lecture Notes in Computer Science},

volume = {4616},

abstract = {We study the complexity of several coloring problems on graphs, parameterized by the treewidth of the graph:

1) The list chromatic number $\chi_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 $\chi_l(G)\leq 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 list-based

variation, LIST EQUITABLE COLORING is W[1]-hard for trees, parameterized by the number of colors on the lists.},

url = {http://www.mrfellows.net/papers/ C79-COCOA-07.pdf}

}

@article{CaiFellowsJuedesRosamond2007,

title = {The Complexity of Polynomial-Time Approximation},

author = {Liming Cai and Michael Fellows and David Juedes and Frances Rosamond},

year = {2007},

journal = {Theory of Computing Systems},

volume = {41},

number = {3},

pages = {459–477},

publisher = {Springer-Verlag, New York, Inc.},

abstract = {In 1996, Khanna and Motwani proposed three logic-based

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 polynomial-time 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/{$\epsilon$}$. 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.},

url = {http://www.mrfellows.net/papers/J67-CFJR_jcss(old).pdf}

}

@inproceedings{FellowsFlumHermelinMullerRosamond2007a,

author = {Michael Fellows and J{\”o}rg Flum and Danny Hermelin and

Moritz M{\”u}ller and Frances Rosamond},

title = {Parameterized Complexity via Combinatorial Circuits},

booktitle = {Algorithms and Complexity in Durham 2007, Proceedings of

the third ACiD Workshop},

pages = {55–67},

year = {2007},

editor = {Hajo Broersma and Stefan Dantchev and Matthew Johnson

and Stefan Szeider},

volume = {9},

series = {Texts in Algorithmics},

publisher = {College Publications London},

url = {http://www.mrfellows.net/papers/C80-ACiD07-Circuits.pdf}

}

@article{ChenChorFellowsHuangJuedesKanjXia2005,

title = {Tight Lower Bounds for certain Parameterized {NP}-Hard Problems},

author = {Jianer Chen and Benny Chor and Mike Fellows and Xiuzhen

Huang and David W. Juedes and Iyad A. Kanj and Ge Xia},

journal = {Information and Computation},

year = {2005},

number = {2},

volume = {201},

pages = {216–231},

url = {http://www.mrfellows.net/papers/CCFHJKX05_TightLowerBounds.pdf}

}

@article{DowneyEstivill-CastroFellowsPrietoRosamond2003,

title = {Cutting Up is Hard to Do: the Parameterized Complexity of

{k}-Cut and Related Problems},

author = {Rodney G. Downey and Vladimir Estivill-Castro and Michael

R. Fellows and Elena Prieto and Frances A. Rosamond},

journal = {Electronic Notes in Theoretical Computer Science},

year = {2003},

volume = {78},

pages = {205–218},

url = {http://www.mrfellows.net/papers/DEPR03_kcut.pdf}

}

@article{DowneyFellows2001a,

title = {Index Sets and Parametric Reductions},

author = {Rodney G. Downey and Michael R. Fellows},

journal = {Archive for Mathematical Logic},

year = {2001},

number = {5},

volume = {40},

pages = {329–348},

url = {http://www.mrfellows.net/papers/J51-IndexSets01.pdf}

}

@article{DowneyFellows1998,

author = {Rodney G. Downey and Michael R. Fellows},

title = {Threshold Dominating Sets and an Improved Characterization

of {W}[2]},

journal = {Theoretical Computer Science},

pages = {123–140},

year = {1998},

number = {1-2},

volume = {209},

publisher = {Elsevier Science Publishers},

url = {http://www.mrfellows.net/papers/J46-wstar2.pdf}

}

@article{DowneyFellowsRegan1998,

author = {Rodney G. Downey and Michael R. Fellows and Kenneth W. Regan},

title = {Parameterized Circuit Complexity and the {W} Hierarchy},

journal = {Theoretical Computer Science A},

volume = {191},

number = {1–2},

pages = {97–115},

year = {1998},

url = {http://www.mrfellows.net/papers/DFR98_CircuitComplexity.pdf}

}

@article{CaiChenDowneyFellows1997,

title = {Advice Classes of Parameterized Tractability},

author = {Liming Cai and Jianer Chen and Rodney G. Downey and

Michael R. Fellows},

journal = {Annals of Pure and Applied Logic},

year = {1997},

number = {1},

volume = {84},

pages = {119–138},

url = {http://www.mrfellows.net/papers/CCDF97_AdviceClasses.pdf}

}

@article{CaiChenDowneyFellows1997b,

title = {The Parameterized Complexity of Short Computation and Factorization},

author = {Liming Cai and Jianer Chen and Rodney G. Downey and

Michael R. Fellows},

journal = {Archive for Mathematical Logic},

year = {1997},

volume = {36},

pages = {321–338},

abstract = {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.},

url = {http://www.mrfellows.net/papers/J41-shortcomp97.pdf}

}

@incollection{DowneyFellowsRegan1997,

title = {Descriptive Complexity and the {W} Hierarchy},

author = {R. Downey and M. Fellows and K. Regan},

booktitle = {Proof Complexity and Feasible Arithmetics},

editor = {P. Beame and S. Buss},

series = {AMS-DIMACS Series in Discrete Mathematics and Theoretical

Computer Science},

publisher = {American Mathematical Society},

year = {1997},

pages = {119-134},

url = {http://www.mrfellows.net/papers/C34-descriptive97.pdf}

}

@inproceedings{DowneyFellowsTaylor1996,

author = {Rod G. Downey and Michael R. Fellows and Udayan Taylor},

title = {The Parameterized Complexity of Relational Database

Queries and an Improved Characterization of {W[1]}},

booktitle = {Combinatorics, Complexity, and Logic – Proceedings of

DMTCS ’96},

year = {1996},

pages = {194–213},

publisher = {Springer-Verlag},

editor = {D. Bridges and C. Calude and J. Gibbons and S. Reeves

and I. Witten},

url = {http://www.mrfellows.net/papers/C33.ps}

}

@article{CesatiFellows1996,

author = {M. Cesati and M. Fellows},

title = {Sparse parameterized problems},

journal = {Annals of Pure and Applied Logic},

year = {1996},

volume = {82},

pages = {1–15},

url = {http://www.mrfellows.net/papers/CF96_SparseParameterizedProbs.pdf}

}

@article{AbrahamsonDowneyFellows1995b,

author = {Karl Abrahamson and Rodney G. Downey and Michael R. Fellows},

title = {Fixed-Parameter Tractability and Completeness {IV}: On

Completeness for {W[P]} and {PSPACE} Analogs},

journal = {Annals of Pure and Applied Logic},

volume = {73},

year = {1995},

pages = {235-276},

url = {http://www.mrfellows.net/papers/J31-fpt4-95.pdf}

}

@article{DowneyFellows1995d,

author = {Rodney G. Downey and Michael R. Fellows},

title = {Fixed-Parameter Tractability and Completeness {II}: On Completeness for {W[1]}},

journal = {Theoretical Computer Science},

volume = {141},

number = {1{\&}2},

year = {1995},

pages = {109-131},

url = {http://www.mrfellows.net/papers/DF95_FPTandCompletenessII.pdf}

}

@inproceedings{DowneyFellows1993,

author = {Rod Downey and Michael Fellows},

title = {Fixed-parameter tractability and completeness {III}: Some

structural aspects of the {W} hierarchy},

booktitle = {Complexity Theory: Current Research — Proceedings of

the 1992 Dagstuhl Workshop on Structural Complexity},

pages = {191–225},

year = {1993},

editor = {Klaus Ambos-Spies and Steven Homer and Uwe Sch{\”o}ning},

publisher = {Cambridge University Press},

address = {Cambridge}

}

@article{CaiChenDowneyFellows1995b,

title = {On the Structure of Parameterized Problems in {NP}},

author = {Liming Cai and Jianer Chen and Rodney Downey and Michael Fellows},

pages = {38–49},

journal = {Information and Computation},

year = {1995},

volume = {123},

number = {1},

abstract = {Fixed-parameter 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 fixed-parameter tractable and that the

fixed-parameter intractability hierarchy (the W-hierarchy) does not

collapse.}

}

@article{DowneyFellows1995f,

author = {Rodney G. Downey and Michael R. Fellows},

title = {Fixed-Parameter Tractability and Completeness {I}: Basic Results},

journal = {SIAM Journal of Computing},

volume = {24},

number = {4},

year = {1995},

pages = {873-921},

url = {http://www.mrfellows.net/papers/DF95_FPTandCompletenessI.pdf}

}

@inproceedings{CaiChenDowneyFellows1994,

title = {On the Structure of Parameterized Problems in {NP}},

author = {Liming Cai and Jianer Chen and Rodney G. Downey and

Michael R. Fellows},

booktitle = {Proceedings of 11th Annual Symposium on Theoretical

Aspects of Computer Science, STACS’94, Caen, France},

publisher = {Springer},

year = {1994},

volume = {775},

editor = {Patrice Enjalbert and Ernst W. Mayr and Klaus W. Wagner},

pages = {509–520},

series = {Lecture Notes in Computer Science}

}

@inproceedings{AbrahamsonDowneyFellows1993b,

author = {Karl A. Abrahamson and Rodney G. Downey and Michael R. Fellows},

title = {Fixed-parameter Intractability {II}},

booktitle = {Proceedings of the 10th Annual Symposium on Theoretical

Aspects of Computer Science, STACS’93},

pages = {374–385},

year = {1993},

volume = {665},

series = {Lecture Notes in Computer Science},

editor = {P. Enjalbert and A. Finkel and K. W. Wagner},

publisher = {Springer-Verlag}

}

@inproceedings{DowneyFellows1992,

author = {Rod Downey and Michael Fellows},

title = {Fixed-parameter Intractability},

booktitle = {Proceedings of the Seventh Annual IEEE Conference on

Structure in Complexity Theory},

pages = {36–49},

year = {1992}

}

@article{DowneyFellows1992b,

title = {Fixed-Parameter Tractability and Completeness},

author = {Rod Downey and Michael Fellows},

journal = {Congressus Numerantium},

year = {1992},

volume = {87},

pages = {161–178}

}

@inproceedings{FellowsLangston1989b,

author = {M. R. Fellows and M. Langston},

title = {An Analogue of the {M}yhill-{N}erode Theorem and Its Use in Computing Finite-Basis Characterizations},

booktitle = {Proceedings of 30th annual Symposium on Foundations of Computer

Science FOCS’89},

publisher = {IEEE Computer Society Press},

pages = {520-525},

year = {1989},

abstract = {A theorem that is a graph-theoretic analog of the Myhill-Nerode characterization of regular languages is proved. The

theorem is used to establish that for many applications obstruction sets are computable by known algorithms. The focus is

exclusively on what is computable (by a known algorithm) in principle, as opposed to what is computable in practice.},

url = {http://www.mrfellows.net/papers/C5-MyhillNerode-FOCS89.pdf}

}

@inproceedings{AbrahamsonFellowsEllisMata1989,

author = {K. R. Abrahamson and M. R. Fellows and J. A. Ellis and M. E. Mata},

title = {On the complexity of fixed parameter problems},

booktitle = {Proceedings of 30th annual Symposium on Foundations of Computer

Science FOCS’89},

publisher = {IEEE Computer Society Press},

pages = {210–215},

year = {1989},

abstract = {The paper addresses the question of why some fixed-parameter problem families solvable in polynomial time seem to be

harder than others with respect to fixed-parameter tractability: whether there is a constant α 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 fixed-parameter tractability, and (2) some natural problems are complete.},

url = {http://www.mrfellows.net/papers/C6-FOCS89.pdf}

}

@techreport{DowneyFellowsMcCartin,

author = {R. Downey and M.R. Fellows and C. Mccartin},

title = {Parameterized Approximation Problems}

}

@inproceedings{FellowsGiannopoulosKnauerPaulRosamondWhitesidesYu2009,

author = {M. Fellows and P. Giannopoulos and C. Knauer and C. Paul and F. Rosamond and S. Whitesides and N. Yu},

title = {On the Parameterized Complexity of the Discrete Milling Problem with Turn Costs},

journal = {Lecture Notes in Computer Science},

booktitle = {Proceedings of FST TCS’09},

publisher = {Springer-Verlag},

note = {To Appear},

year = {2009}

}

@inproceedings{DomiFellowsRosamond2009,

author = {M. Dom, M. Fellows and F. Rosamond},

title = {Parameterized Complexity of Stabbing Rectangles and

Squares in the Plane},

journal = {Lecture Notes in Computer Science},

booktitle = {Proceedings of the 3rd Workshop on Algorithms and Computation,

WALCOM’09},

volume = {5431},

pages = {298-309},

year = {2009},

series = {Lecture Notes in Computer Science},

publisher = {Springer-Verlag},

url = {http://www.mrfellows.net/papers/C90-rectstab_final.pdf}

}

@article{FellowsKnauerNishimuraRagdeRosamondStegeThilikosWhitesides2008,

author = {M. R. Fellows and C. Knauer and N. Nishimura and P. Ragde and F. Rosamond and U. Stege and D. Thilikos and S.

Whitesides},

title = {Faster Fixed Parameter Tractable Algorithms for Matching and Packing Problems},

journal = {Algorithmica},

volume = {52},

number = {2},

year = {2008},

pages = {167–176},

publisher = {Springer-Verlag New York, Inc.},

url = {http://www.mrfellows.net/papers/J72-MatchingPacking-Algorithmica.pdf}

}

@article{DujmovicFellowsKitchingLiottaMccartinNishimuraRagdeRosamondSudermanWhitesidesWood2008,

author = {Vida Dujmovic and Michael R. Fellows and Matthew Kitching

and Giuseppe Liotta and Catherine McCartin and Naomi Nishimura and

Prabhakar Ragde and Frances Rosamond and Sue Whitesides and David R.

Wood},

title = {On the Parameterized Complexity of Layered Graph Drawing},

journal = {Algorithmica},

volume = {52},

number = {2},

year = {2008},

pages = {267–292},

publisher = {Springer-Verlag New York, Inc.},

url = {http://www.mrfellows.net/papers/J70-Algorithmica08.pdf}

}

@article{DujmovicFellowsHallettKitchingLiottaMccartinNishimuraRagdeRosamondSudermanWhitesidesWood2006,

author = {Vida Dujmovic and Michael R. Fellows and Michael T.

Hallett and Matthew Kitching and Giuseppe Liotta and Catherine

McCartin and Naomi Nishimura and Prabhakar Ragde and Frances A.

Rosamond and Matthew Suderman and Sue Whitesides and David R. Wood},

title = {A Fixed-Parameter Approach to 2-Layer Planarization},

journal = {Algorithmica},

volume = {45},

number = {2},

year = {2006},

pages = {159-182},

url = {http://www.mrfellows.net/papers/C64.pdf}

}

@inproceedings{DujmovicFellowsHallettKitchingLiottaMccartinNishimuraRagdeRosamondSudermanWhitesidesWood2001,

author = {Vida Dujmovic and Michael R. Fellows and Michael T.

Hallett and Matthew Kitching and Giuseppe Liotta and Catherine

McCartin and Naomi Nishimura and Prabhakar Ragde and Frances A.

Rosamond and Matthew Suderman and Sue Whitesides and David R. Wood},

title = {A Fixed-Parameter Approach to Two-Layer Planarization},

booktitle = {Proceedings of the 9th International Symposium on Graph

Drawing GD’01},

pages = {1–15},

year = {2001},

volume = {2265},

series = {Lecture Notes in Computer Science},

publisher = {Springer-Verlag},

url = {http://www.mrfellows.net/papers/DFHKLMNRRSWW01_TwoLayerPlanarization.ps}

}

@inproceedings{DujmovicFellowsHallettKitchingLiottaMccartinNishimuraRagdeRosamondSudermanWhitesidesWood2001b,

author = {V. Dujmovi{\’c} and M. Fellows and M. Hallett and M.

Kitching and G.. Liotta and C. McCartin and N. Nishimura and P. Ragde

and F. Rosamond and M. Suderman and S. Whitesides and D. R. Wood},

title = {On the Parameterized Complexity of Layered Graph Drawing},

journal = {Lecture Notes in Computer Science},

booktitle = {Proceedings of the 9th Annual European Symposium on

Algorithms, ESA ’01},

volume = {2161},

pages = {488–499},

year = {2001},

series = {Lecture Notes in Computer Science},

publisher = {Springer-Verlag}

}

@article{BellFellowsWittenKoblitz2003,

title = {Explaining Cryptographic Systems to the General Public},

author = {Tim Bell and Mike Fellows and Ian Witten and Neil Koblitz},

year = {2003},

journal = {Computers and Education},

volume = {40},

pages = {199–215}

}

@article{DowneyFellowsVardyWhittle1999,

author = {Rod G. Downey and Michael R. Fellows and Alexander Vardy

and Geoff Whittle},

title = {The parametrized complexity of some fundamental problems in

coding theory},

journal = {SIAM Journal of Computing},

pages = {545–570},

year = {1999},

number = {2},

volume = {29},

editor = {M. Yannakakis},

publisher = {Society for Industrial and Applied Mathematics},

address = {Philadelphia, PA},

abstract = {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 MAXIMUM-LIKELIHOOD DECODING and WEIGHT DISTRUBUTION

are hard for the parametrized complexity class W[1]. The NP-completeness of these two problems was established by Berlekamp,

McEliece, and van Tilborg in 1978 using by means of a reduction from THREE-DIMENSIONAL MATCHING. On the other hand,

our proof of hardness for W[1] is based on a parametric polynomial-time transformation from PERFECT CODE in graphs. An

immediate consequence of our results is that bounded-distance decoding is likely to be hard for binary linear codes. Concerning

lattices, we prove here for the first time that THETA SERIES is NP-complete 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 MAXIMUM-LIKELIHOOD DECODING for lattices. Relations between all these problems and

combinatorial problems in graphs are discussed.},

url = {http://www.mrfellows.net/papers/DFVW99_CodingTheory.pdf}

}

@techreport{DowneyFellowsVardyWhittle1997,

author = {Rod G. Downey and Michael R. Fellows and Alexander Vardy

and Geoff Whittle},

title = {The parametrized complexity of some fundamental problems of Linear Codes and Integral Lattices},

year = {1997},

note = {Manuscript},

url = {http://www.mrfellows.net/papers/linearcodesIntegerLattices97.ps}

}

@inproceedings{FellowsKoblizt1994,

author = {Michael Fellows and Neal Koblitz},

booktitle = {Proceedings of the Second International Symposium on

Finite Fields, Las Vegas, Nevada, August, 1993},

title = {Combinatorial cryptosystems galore!},

volume = {168},

publisher = {American Mathematical Society},

pages = {51–61},

year = {1994},

series = {Contemporary Mathematics},

url = {http://www.mrfellows.net/papers/C23-galore.pdf}

}

@inproceedings{FellowsKoblitz1993,

title = {Fixed-Parameter Complexity and Cryptography},

author = {Michael R. Fellows and Neal Koblitz},

booktitle = {Proceedings of 10th International Symposium Applied Algebra, Algebraic Algorithms and

Error-Correcting Codes, AAECC’93, San

Juan de Puerto Rico, Puerto Rico},

publisher = {Springer},

year = {1993},

volume = {673},

editor = {G{\’e}rard D. Cohen and Teo Mora and Oscar Moreno},

pages = {121–131},

series = {Lecture Notes in Computer Science}

}

@inproceedings{DowneyEvansFellows1993,

title = {Parameterized Learning Complexity},

author = {Rodney G. Downey and Patricia A. Evans and Michael R. Fellows},

pages = {51–57},

booktitle = {Proceedings of the Sixth Annual {ACM} Conference on

Computational Learning Theory},

year = {1993},

publisher = {ACM Press},

url = {http://www.mrfellows.net/papers/DEF93_LearningComplexity.pdf}

}

@inproceedings{FellowsKoblitz1992,

author = {Michael R. Fellows and Neal Koblitz},

title = {Self-witnessing polynomial-time complexity and prime factorization},

booktitle = {Proceedings of the 7th Annual Conference on Structure

in Complexity Theory, CSCT’92},

pages = {107–110},

year = {1992},

publisher = {IEEE Computer Society Press},

url = {http://www.mrfellows.net/papers/C13-ccc92-primality.pdf}

}

@article{FellowsKoblitz1992a,

title = {Self-Witnessing Polynomial-Time Complexity and Prime Factorization},

author = {Michael R. Fellows and Neal Koblitz},

pages = {231–235},

journal = {Designs, Codes and Cryptography},

volume = {2},

number = {3},

year = {1992}

}

@inproceedings{DinneenFellowsFaber1991,

author = {M. J. Dinneen and M. R. Fellows and V. Faber},

title = {Algebraic Constructions of Efficient Broadcast Networks},

pages = {152–158},

editor = {Harold F. Mattson and Teo Mora and T. R. N. Rao},

booktitle = {Proceedings of Applied Algebra, Algebraic Algorithms

and Error–Correcting Codes AAECC’91},

series = {LNCS},

volume = {539},

publisher = {Springer-Verlag},

address = {Berlin, Germany},

year = {1991}

}

@article{BellFellowsKoblitzWitten2003,

author = {T. Bell and M. Fellows and N. Koblitz and I. Witten},

title = {Explaining Cryptographic Ideas to the General Public},

journal = {Computers and Education},

volume = {40},

pages = {199—215},

year = {2003},

url = {http://www.mrfellows.net/papers/krypto.ps}

}

@inproceedings{BellFellowsKoblitzWitten1999,

author = {T. Bell and M. Fellows and N. Koblitz and I. Witten},

title = {Explaining Cryptographic Systems to the General Public},

booktitle = {Proceedings of the First IFIP World Conference on

Information Security Education (WISE)},

publisher = {Stockholm University Report Series},

volume = {99-008},

editor = {L. Yngstgr\”{o}m and S. Fischer-H\”{u}bner},

pages = {221—233},

year = {1999}

}

@article{CaseyFellows1997,

author = {N. Casey and M. Fellows},

title = {Implementing the Standards: Let’s Focus on the First Four},

journal = {DIMACS Series: Discrete Mathematics in the Schools. How

Can We Have an Impact?},

publisher = {AMS},

address = {Providence, RI, USA},

editor = {D. Franzblau and F. Roberts and J. Rosenstein},

year = {1997},

url = {http://www.mrfellows.net/papers/C30-StandardsFirst4-CF.pdf}

}

@inproceedings{Fellows1996,

author = {M. Fellows},

title = {The Heart of Puzzling: Mathematics and Computer Games},

booktitle = {Proceedings of the 1996 Computer Games Developers Conference},

publisher = {Miller Freeman},

pages = {109—120},

year = {1996},

url = {http://www.mrfellows.net/papers/C32-games.pdf}

}

@article{FellowsHibnerKoblitz1994,

author = {M.. Fellows and A. Hibner and N. Koblitz},

title = {Cultural Aspects of Mathematics Education Reform},

journal = {Notices of the American Mathematics Society},

volume = {41},

pages = {5—9},

year = {1994}

}

@inproceedings{FellowsKoblitz1993b,

author = {M. Fellows and N. Koblitz},

title = {Kid Krypto},

booktitle = {Proceedings of Crypto 1992},

publisher = {Springer-Verlag, New York, Inc.},

series = {Lecture Notes in Computer Science},

volume = {740},

pages = {371—389},

year = {1993},

url = {http://www.mrfellows.net/papers/C15-kidcrypto.pdf}

}

@inproceedings{Fellows1993,

author = {M. Fellows},

title = {Computer Science in the Elementary Schools},

booktitle = {Proceedings of the Mathematicians and Education Reform

Workshop, Seattle, 1991},

editor = {N. Fisher and H. Keynes and P. Wagreich},

publisher = {Conference Board of the Mathematical Sciences},

series = {Issues in Mathematics Education},

volume = {3},

pages = {143 –163},

year = {1993},

url = {http://www.mrfellows.net/papers/C8.ps}

}

@book{MegaMath_b,

author = {Nancy Casey and Michael R. Fellows},

title = {This is Mega-Mathematics!},

publisher = {Los Alamos National Labs},

year = {1992},

note = {Available at

http://www.c3.lanl.gov/~captors/mega-math. See also

www.ccs3.lanl.gov/mega-math/write.html},

abstract = {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. },

url = {http://www.mrfellows.net/papers/MegaMath.pdf},

pages = {144}

}

@article{FellowsLokshtanovMisraMnichRosamondSaurabh2009,

title = {The Complexity Ecology of Parameters: An Illustration Using

Bounded Max Leaf Number},

author = {M. Fellows and D. Lokshtanov and N. Misra and M. Mnich and F. Rosamond and S. Saurabh},

journal = {Theory of Computing Systems},

year = {2009},

volume = {45},

pages = {822–848},

url = {http://www.mrfellows.net/papers/J76-TOCS-09.pdf}

}

@inproceedings{FellowsGuoMoserNiedermeier2009b,

title = {A Generalization of {N}emhauser and {T}rotter’s Local

Optimization Algorithm},

author = {Michael Fellows and Jiong Guo and Hannes Moser and Rolf

Niedermeier},

booktitle = {Proceedings of STACS’09},

pages = {409–420},

year = {2009},

url = {http://www.mrfellows.net/papers/BC91-STACS-09.pdf}

}

@inproceedings{FellowsMeisterRosamondSritharanTelle2008,

title = {Leaf Powers and Their Properties: Using the Trees},

author = {Michael R. Fellows and Daniel Meister and Frances A.

Rosamond and R. Sritharan and Jan Arne Telle},

booktitle = {Proceedings of Algorithms and Computation, 19th International

Symposium, {ISAAC} 2008, Gold Coast, Australia},

publisher = {Springer-Verlag},

year = {2008},

volume = {5369},

editor = {Seok-Hee Hong and Hiroshi Nagamochi and Takuro Fukunaga},

pages = {402–413},

series = {Lecture Notes in Computer Science},

url = {http://www.mrfellows.net/papers/C89-ISAAC-08.pdf}

}

@inproceedings{FellowsLokshtanovMisraRosamondSaurabh2008,

title = {Graph Layout Problems Parameterized by Vertex Cover},

author = {Michael R. Fellows and Daniel Lokshtanov and Neeldhara

Misra and Frances A. Rosamond and Saket Saurabh},

booktitle = {Proceedings of Algorithms and Computation, 19th International

Symposium, {ISAAC} 2008, Gold Coast, Australia},

publisher = {Springer-Verlag},

year = {2008},

volume = {5369},

editor = {Seok-Hee Hong and Hiroshi Nagamochi and Takuro Fukunaga},

pages = {294–305},

series = {Lecture Notes in Computer Science},

url = {http://www.mrfellows.net/papers/C88-ISAAC-08.pdf}

}

@inproceedings{BodlaenderFellowsHeggernesManciniPapadopoulosRosamond2008,

title = {Clustering with Partial Information},

author = {Hans L. Bodlaender and Michael R. Fellows and Pinar

Heggernes and Federico Mancini and Charis Papadopoulos and Frances A.

Rosamond},

booktitle = {Proceedings of Mathematical Foundations of Computer Science, 33rd

International Symposium, {MFCS} 2008, Torun, Poland},

publisher = {Springer-Verlag},

year = {2008},

volume = {5162},

editor = {Edward Ochmanski and Jerzy Tyszkiewicz},

pages = {144–155},

series = {Lecture Notes in Computer Science},

url = {http://www.mrfellows.net/papers/C86.pdf}

}

@inproceedings{FellowsFernau2008b,

title = {Facility Location Problems: {A} Parameterized View},

author = {Michael R. Fellows and Henning Fernau},

booktitle = {Proceedings of Algorithmic Aspects in Information and Management, 4th

International Conference, AAIM’08},

publisher = {Springer-Verlag},

year = {2008},

volume = {5034},

editor = {Rudolf Fleischer and Jinhui Xu},

pages = {188–199},

series = {Lecture Notes in Computer Science},

url = {http://www.mrfellows.net/papers/C83-Facilities-AAIM08.pdf}

}

@inproceedings{BodlaenderFellowsLangstonRaganRosamondWeyer2007,

title = {Quadratic Kernelization for Convex Recoloring of Trees},

author = {Hans L. Bodlaender and Michael R. Fellows and Michael A.

Langston and Mark A. Ragan and Frances A. Rosamond and Mark Weyer},

booktitle = {Proceedings of Computing and Combinatorics, 13th Annual International

Conference, COCOON’07},

publisher = {Springer-Verlag},

year = {2007},

volume = {4598},

editor = {Guohui Lin},

pages = {86–96},

series = {Lecture Notes in Computer Science},

url = {http://www.mrfellows.net/papers/C75-COCOON-07.pdf}

}

@inproceedings{FellowsFominLokshtanovRosamondSaurabhSzeiderThomassen2007b,

title = {On the Complexity of Some Colorful Problems Parameterized

by Treewidth},

author = {Michael R. Fellows and Fedor V. Fomin and Daniel

Lokshtanov and Frances A. Rosamond and Saket Saurabh and Stefan

Szeider and Carsten Thomassen},

booktitle = {Proceedings of Combinatorial Optimization and Applications, COCOA’07},

publisher = {Springer-Verlag},

year = {2007},

volume = {4616},

editor = {Andreas W. M. Dress and Yinfeng Xu and Binhai Zhu},

pages = {366–377},

series = {Lecture Notes in Computer Science},

url = {http://www.mrfellows.net/papers/J79-submitted.pdf}

}

@inproceedings{ChorFellowsRaganRazgonRosamondSnir2007,

title = {Connected Coloring Completion for General Graphs:

Algorithms and Complexity},

author = {Benny Chor and Michael R. Fellows and Mark A. Ragan and

Igor Razgon and Frances A. Rosamond and Sagi Snir},

booktitle = {Proceedings of Computing and Combinatorics, 13th Annual International

Conference, COCOON’07},

publisher = {Springer-Verlag},

year = {2007},

volume = {4598},

editor = {Guohui Lin},

pages = {75–85},

series = {Lecture Notes in Computer Science},

url = {http://www.mrfellows.net/papers/C76-COCOON-07.pdf}

}

@inproceedings{FellowsLangstonRosamondShaw2007a,

title = {Efficient Parameterized Preprocessing for Cluster Editing},

author = {Michael R. Fellows and Michael A.. Langston and Frances A.

Rosamond and Peter Shaw},

booktitle = {Proceedings of 16th International

Symposium Fundamentals of Computation Theory FCT’07},

publisher = {Springer-Verlag},

year = {2007},

volume = {4639},

editor = {Erzs{\’e}bet Csuhaj-Varj{\’u} and Zolt{\’a}n {\’E}sik},

pages = {312–321},

series = {Lecture Notes in Computer Science},

url = {http://www.mrfellows.net/papers/FLRS07_ClusterEdit.pdf}

}

@article{CaiFellowsJuedesRosamond2007a,

title = {The Complexity of Polynomial-Time Approximation},

author = {Liming Cai and Michael Fellows and David Juedes and

Frances Rosamond},

year = {2007},

journal = {Theory of Computing Systems},

volume = {41},

number = {3},

pages = {459–477},

publisher = {Springer-Verlag New York, Inc.},

abstract = {We show that Planar TMIN, Planar TMAX and Planar MPSAT,

parameterized by $k = 1/{$\epsilon$}$, 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.},

url = {http://www.mrfellows.net/papers/J67-CFJR_jcss(old).pdf}

}

@article{Abu-KhzamFellowsLangstonSuters2007,

title = {Crown Structures for Vertex Cover Kernelization},

author = {Faisal N. Abu-Khzam and Michael R. Fellows and Michael A.

Langston and W. Henry Suters},

publisher = {Springer-Verlag},

year = {2007},

abstract = {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

crown-free subgraph, and the problem of finding a crown of maximum

size in an arbitrary graph, are solvable in polynomial time.},

journal = {Theory of Computing Systems},

number = {3},

volume = {41},

pages = {411–430},

url = {http://www.mrfellows.net/papers/J66-TOCS-crowns.pdf}

}

@article{DehneFellowsLangstonRosamondStevens2007,

title = {An $O(2^{O(k)}n^3)$ {FPT} Algorithm for the Undirected

Feedback Vertex Set Problem},

author = {Frank Dehne and Michael Fellows and Michael Langston and

Frances Rosamond and Kim Stevens},

publisher = {Springer-Verlag},

year = {2007},

abstract = {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.},

journal = {Theory of Computing Systems},

number = {3},

volume = {41},

pages = {479–492},

url = {http://www.mrfellows.net/papers/J65-TCS-07.pdf}

}

@article{FellowsGrammNiedermeier2006b,

author = {Michael R. Fellows and Jens Gramm and Rolf Niedermeier},

title = {On The Parameterized Intractability Of Motif Search Problems},

journal = {Combinatorica},

volume = {26},

number = {2},

year = {2006},

pages = {141–167},

publisher = {Springer-Verlag New York, Inc.},

url = {http://www.mrfellows.net/papers/FGN06_MotifSearch.pdf}

}

@inproceedings{DehneFellowsFernauPrietoRosamond2006,

title = {{NONBLOCKER}: Parameterized Algorithmics for Minimum

Dominating Set},

author = {Frank Dehne and Michael R. Fellows and Henning

Fernau and Elena Prieto and Frances A. Rosamond},

booktitle = {Proceedings of Theory and Practice of Computer Science,

32nd Conference on Current Trends in Theory and Practice of Computer

Science SOFSEM’06},

publisher = {Springer-Verlag},

year = {2006},

volume = {3831},

editor = {Jir{\’i} Wiedermann and Gerard Tel and Jaroslav

Pokorn{\’y} and M{\’a}ria Bielikov{\’a} and Julius Stuller},

pages = {237–245},

series = {Lecture Notes in Computer Science},

url = {http://www.mrfellows.net/papers/DFFPR06_Nonblocker.pdf}

}

@inproceedings{FellowsRosamondRoticsSzeider2006,

title = {Clique-Width Minimization is {NP}-Hard},

author = {Michael R. Fellows and Frances A. Rosamond and Udi Rotics

and Stefan Szeider},

booktitle = {Proceedings of the 38th Annual Symposium on

Theory of Computing, ACM’06},

publisher = {ACM},

year = {2006},

editor = {Jon M. Kleinberg},

pages = {354–362},

url = {http://www.mrfellows.net/papers/FRRS06_CliquewidthNPhard.pdf}

}

@inproceedings{BurrageEstivill-CastroFellowsLangstonMacRosamond2006,

title = {The Undirected Feedback Vertex Set Problem Has a Poly($k$) Kernel},

author = {Kevin Burrage and Vladimir Estivill-Castro and Michael R.

Fellows and Michael A. Langston and Shev Mac and Frances A. Rosamond},

booktitle = {Proceedings of Parameterized and Exact Computation, Second

International Workshop, IWPEC’06},

publisher = {Springer-Verlag},

year = {2006},

volume = {4169},

editor = {Hans L. Bodlaender and Michael A. Langston},

pages = {192–202},

series = {Lecture Notes in Computer Science},

url = {http://www.mrfellows.net/papers/C68-IWPEC-06.pdf}

}

@inproceedings{BodlaenderFellowsLangstonRaganRosamondWeyer2006,

title = {Kernelization for Convex Recoloring},

author = {Hans L. Bodlaender and Michael R. Fellows and Michael A.

Langston and Mark A. Ragan and Frances A. Rosamond and Mark Weyer},

booktitle = {Proceedings of Algorithms and Complexity in Durham, {AC}i{D}’06},

publisher = {King’s College, London},

year = {2006},

volume = {7},

editor = {Hajo Broersma and Stefan S. Dantchev and Matthew Johnson

0002 and Stefan Szeider},

pages = {23–36},

series = {Texts in Algorithmics},

note = {Accepted to Algorithmica},

url = {http://www.mrfellows.net/papers/J79-submitted.pdf}

}

@article{AlberFanFellowsFernauNiedermeierRosamondStege2005,

author = {Jochen Alber and Hongbing Fan and Michael R. Fellows and

Henning Fernau and Rolf Niedermeier and Fran Rosamond and Ulrike

Stege},

title = {A Refined Search Tree Technique for Dominating Set on Planar Graphs},

journal = {Journal of Computer and System Sciences},

volume = {71},

number = {4},

year = {2005},

pages = {385–405},

publisher = {Academic Press, Inc.},

url = {http://www.mrfellows.net/papers/AFFFNRS05_PlanarDS.pdf}

}

@inproceedings{DehneFellowsLangstonRosamondStevens2005,

title = {An {O}(2$^{O(k)}$n$^{3}$) {FPT} Algorithm for the

Undirected Feedback Vertex Set Problem},

author = {Frank K. H. A. Dehne and Michael R. Fellows and Michael A.

Langston and Frances A. Rosamond and Kim Stevens},

booktitle = {Proceedings of Computing and Combinatorics, 11th Annual International

Conference, {COCOON}’05},

publisher = {Springer-Verlag},

year = {2005},

volume = {3595},

editor = {Lusheng Wang},

pages = {859–869},

series = {Lecture Notes in Computer Science},

url = {http://www.mrfellows.net/papers/C64.pdf}

}

@inproceedings{Estivill-CastroFellowsLangstonRosamond2005,

title = {Fixed-Parameter Tractability is Polynomial-Time Extremal

Structure Theory {I}: The Case of Max Leaf},

author = {Vladimir Estivill-Castro and Michael R. Fellows and

Michael A. Langston and Frances A. Rosamond},

booktitle = {Proceedings of Algorithms and Complexity in Durham, {AC}i{D} 2005},

publisher = {King’s College, London},

year = {2005},

volume = {4},

editor = {Hajo Broersma and Matthew Johnson 0002 and Stefan Szeider},

pages = {1–41},

series = {Texts in Algorithmics},

url = {http://www.mrfellows.net/papers/C65-maxleaf.pdf}

}

@article{AlberFellowsNiedermeier2004,

author = {J. Alber and M. R. Fellows and R. Niedermeier},

title = {Polynomial-Time Data Reduction for Dominating Set},

abstract = {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 easy-to-implement 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.},

journal = {Journal of the ACM},

volume = {51},

number = {3},

year = {2004},

pages = {363–384},

url = {http://www.mrfellows.net/papers/J58-AlFeNi02.pdf}

}

@article{EllisFanFellows2004,

author = {J. Ellis and H. Fan and M. Fellows},

title = {The Dominating Set Problem is Fixed Parameter Tractable for

Graphs of Bounded Genus},

journal = {Journal of Algorithms},

pages = {152–168},

year = {2004},

number = {2},

volume = {52},

abstract = {We describe an algorithm for the dominating set problem

with time complexity $O((4g+40)^k n^2)$ for graphs of bounded genus $g

\ge 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.},

editor = {Zvi Galil and David S. Johnson and Donald E. Knuth},

publisher = {Elsevier B.V.}

}

@inproceedings{Abu-KhzamCollinsFellowsLangstonSutersSymons2004,

author = {Faisal N. Abu-Khzam and Rebecca L. Collins and Michael R.

Fellows and Michael A. Langston and W. Henry Suters and Christopher T.

Symons},

title = {Kernelization Algorithms for the {V}ertex {C}over Problem:

Theory and Experiments},

pages = {62–69},

editor = {Lars Arge and Guiseppe F. Italiano and Robert Sedgewick},

booktitle = {Proceedings of the Sixth Workshop on Algorithm

Engineering and Experiments and the first Workshop on Analytic

Algorithmics and Combinatorics {ALENEX}’04},

series = {Siam Proceedings Series},

publisher = {Society of Industrial and Applied Mathematics},

year = {2004}

}

@inproceedings{FelllowsKnauerNishimuraRagdeRosamondStegeThilikosWhitesides2004,

author = {M. R. Fellows and C. Knauer and N. Nishimura and P. Ragde

and F. A. Rosamond and U. Stege and D. M. Thilikos and S.

Whitesides},

title = {Faster Fixed-Parameter Tractable Algorithms for Matching

and Packing Problems},

pages = {311–322},

editor = {S. Albers and T. Radzik},

booktitle = {Proceedings of 12th Annual European Symposium on Algorithms {ESA}’04},

publisher = {Springer-Verlag},

series = {Lecture Notes in Computer Science},

volume = {3221},

year = {2004},

url = {http://www.mrfellows.net/papers/C61.pdf}

}

@inproceedings{FellowsHeggernesRosamondSloperTelle2004,

title = {Finding $k$ Disjoint Triangles in an Arbitrary Graph},

author = {Mike Fellows and Pinar Heggernes and Frances A. Rosamond

and Christian Sloper and Jan Arne Telle},

booktitle = {Proceedings of Graph-Theoretic Concepts in Computer Science, 30th

International Workshop,{WG}’04},

publisher = {Springer-Verlag},

year = {2004},

volume = {3353},

editor = {Juraj Hromkovic and Manfred Nagl and Bernhard Westfechtel},

pages = {235–244},

series = {Lecture Notes in Computer Science},

url = {http://www.mrfellows.net/papers/C62-wg2004.pdf}

}

@inproceedings{ChorFellowsJuedes2004,

title = {Linear Kernels in Linear Time, or How to Save $k$ Colors in

{O}(n$^2$) Steps},

author = {Benny Chor and Mike Fellows and David W. Juedes},

booktitle = {Proceedings of Graph-Theoretic Concepts in Computer Science, 30th

International Workshop,{WG}’04},

publisher = {Springer-Verlag},

year = {2004},

volume = {3353},

editor = {Juraj Hromkovic and Manfred Nagl and Bernhard Westfechtel},

pages = {257–269},

series = {Lecture Notes in Computer Science},

url = {http://www.mrfellows.net/papers/CFJ04_LinearKernels.pdf}

}

@article{FellowsHallettStege2003a,

author = {M. R. Fellows and M. Hallett and U. Stege},

title = {Analogs and Duals of the {MAST} Problem for Sequences \& Trees},

journal = {Journal of Algorithms},

volume = {49},

year = {2003},

pages = {192 — 216},

url = {http://www.mrfellows.net/papers/J54-MAST.pdf}

}

@article{DowneyEstivill-CastroFellowsPrietoRosamond2003b,

title = {Cutting Up is Hard to Do: the Parameterized Complexity of

{k}-Cut and Related Problems},

author = {Rodney G. Downey and Vladimir Estivill-Castro and Michael

R. Fellows and Elena Prieto and Frances A. Rosamond},

journal = {Electronic Notes in Theoretical Computer Science},

year = {2003},

volume = {78},

pages = {205–218},

url = {http://www.mrfellows.net/papers/DEPR03_kcut.pdf}

}

@inproceedings{Fellows2003a,

author = {Michael R. Fellows},

title = {Blow-ups, win/win’s, and crown rules: Some new directions in {FPT}},

booktitle = {Proceedings of the 29th International Workshop on

Graph-Theoretic Concepts in Computer Science, WG’03},

pages = {1–12},

year = {2003},

volume = {2880},

series = {LNCS},

abstract = {This survey reviews the basic notions of parameterized

complexity, and describes some new approaches to designing FPT

algorithms and problem reductions for graph problems.},

editor = {Hans L. Bodlaender},

publisher = {Springer-Verlag},

url = {http://www.mrfellows.net/papers/C52-WG03.pdf}

}

@inproceedings{DehneFellowsRosamond2003,

author = {Frank Dehne and Michael R. Fellows and Frances A. Rosamond},

title = {An {FPT} algorithm for set splitting},

booktitle = {Proceedings of the 29th International Workshop on

Graph-Theoretic Concepts in Computer Science, WG’03},

pages = {180–191},

year = {2003},

volume = {2880},

series = {Lecture Notes in Computer Science},

abstract = {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

$n$-variable 3SAT instances can be decided in time $2^{o(n)}$.},

editor = {Hans L. Bodlaender},

publisher = {Springer-Verlag},

url = {http://www.mrfellows.net/papers/C53-WG-2003.pdf}

}

@inproceedings{BodlaenderFellowsThilikos2003,

author = {H. L. Bodlaender and M. R. Fellows and D. M. Thilikos},

title = {Starting with Nondeterminism: The Systematic Derivation of

Linear-Time Graph Layout Algorithms},

booktitle = {Proceedings of Mathematical Foundations of Computer Science MFCS’03},

year = {2003},

pages = {239–248},

editor = {B. Rovan and P. Vojt{\’a}s},

publisher = {Springer},

series = {Lecture Notes in Computer Science},

volume = {2747},

url = {http://www.mrfellows.net/papers/C55-nondeterminism-MFCS03.pdf}

}

@inproceedings{AlberFellowsNiedermeier2002,

title = {Efficient Data Reduction for {DOMINATING} {SET}: {A} Linear

Problem Kernel for the Planar Case},

author = {Jochen Alber and Michael R. Fellows and Rolf Niedermeier},

booktitle = {Proceedings of 8th Scandinavian Workshop on Algorithm Theory {SWAT}’02},

publisher = {Springer},

year = {2002},

volume = {2368},

editor = {Martti Penttonen and Erik Meineche Schmidt},

pages = {150–159},

series = {Lecture Notes in Computer Science},

url = {http://www.mrfellows.net/papers/C50-swat2002.pdf}

}

@inproceedings{EllisFanFellows2002,

author = {J. Ellis and H. Fan and M.~R. Fellows},

title = {The Dominating Set Problem is Fixed Parameter Tractable for

Graphs of Bounded Genus},

booktitle = {Proceedings of SWAT 2002: Scandinavian Workshop on

Algorithm Theory},

year = {2002},

volume = {2368},

editor = {M. Penttonen and E. Meineche Schmidt},

series = {LNCS},

pages = {180–189},

publisher = {Springer},

url = {http://www.mrfellows.net/papers/C51.pdf}

}

@inproceedings{AlberFanFellowsFernauNiedermeierRosamondStege2001,

title = {A Refined Search Tree Technique for {DOMINATING} {SET} on

Planar Graphs},

author = {Jochen Alber and Hongbing Fan and Michael R. Fellows and

Henning Fernau and Rolf Niedermeier and Frances A. Rosamond and Ulrike

Stege},

abstract = {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.},

booktitle = {Proceedings of 26th

International Symposium Mathematical Foundations of Computer Science, MFCS’01},

publisher = {Springer-Verlag},

year = {2001},

volume = {2136},

editor = {Jiri Sgall and Ales Pultr and Petr Kolman},

pages = {111–122},

series = {Lecture Notes in Computer Science},

url = {http://www.mrfellows.net/papers/AFFFNRS01_PlanarDomSet.ps}

}

@article{DowneyFellowsRaman2000,

author = {Rodney G. Downey and Michael R. Fellows and Venkatesh Raman},

title = {The Complexity of Irredundant Sets Parameterized by Size},

journal = {Discrete Applied Mathematics},

volume = {100},

number = {3},

year = {2000},

pages = {155-167},

url = {http://www.mrfellows.net/papers/DFR00_IrredundanceSets.pdf}

}

@article{BodlaenderFellowsHallettWarehamWarnow2000a,

author = {Hans L. Bodlaender and Michael R. Fellows and Michael T.

Hallett and H. Todd Wareham and Tandy J. Warnow},

title = {The Hardness of Perfect Phylogeny, Feasible Register

Assignment and other problems on Thin Colored Graphs},

journal = {Theoretical Computer Science A},

abstract = {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 NP-Complete.},

volume = {244},

number = {1–2},

pages = {167–188},

year = {2000},

url = {http://www.mrfellows.net/papers/BFHWW00_PhylogenyThinColoredGraphs.pdf}

}

@inproceedings{FellowsMcCartinRosamondStege2000a,

title = {Coordinatized Kernels and Catalytic Reductions: An Improved

{FPT} Algorithm for Max Leaf Spanning Tree and Other Problems},

author = {Michael R. Fellows and Catherine McCartin and Frances A.

Rosamond and Ulrike Stege},

booktitle = {Proceedings of Foundations of Software Technology and Theoretical

Computer Science, 20th Conference, {FST} {TCS} ’00},

publisher = {Springer-Verlag},

year = {2000},

volume = {1974},

editor = {Sanjiv Kapoor and Sanjiva Prasad},

pages = {240–251},

series = {Lecture Notes in Computer Science},

url = {http://www.mrfellows.net/papers/C40-KernelsCatalytic-2000.pdf}

}

@inproceedings{FellowsHallettKorostenskyStege1998a,

author = {M. Fellows and M. T. Hallett and C. Korostensky and U. Stege},

title = {Analogs and Duals of the {MAST} Problem for Sequences and Trees},

abstract = {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 leaf-labels and a

subobject is defined by label-respecting hereditary topological

containment, both of these problems are NP-complete, as are the

analogous problems for sequences (the well-known Longest Common

Subsequence and Shortest Common Supersequence problems). However, when

the trees are restricted by allowing each symbol to occur as a

leaf-label at most once (which we call a phylogenetic tree or p-tree),

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.},

booktitle = {Proceedings of the 6th Annual European Symposium on Algorithms},

editor = {G. Bilardi and G. F. Italiano and A. Pietracaprina and G. Pu cci},

series = {Lecture Notes in Computer Science},

number = {1461},

publisher = {Springer-Verlag, Berlin},

year = {1998},

pages = {103–114},

url = {http://www.mrfellows.net/papers/J54-MAST-early.pdf}

}

@article{BalasubramanianFellowsRaman1998,

author = {Balasubramanian and Fellows and Raman},

title = {An Improved Fixed-Parameter Algorithm for Vertex Cover},

journal = {IPL: Information Processing Letters},

volume = {65},

number = {3},

year = {1998},

pages = {163–168},

url = {http://www.mrfellows.net/papers/BFR98_VC.pdf}

}

@article{DowneyFellows1998a,

author = {Rodney G. Downey and Michael R. Fellows},

title = {Threshold Dominating Sets and an Improved Characterization

of ${W}[2]$},

journal = {Theoretical Computer Science},

pages = {123–140},

year = {1998},

number = {1-2},

volume = {209},

publisher = {Elsevier Science Publishers B.V. (North Holland)},

url = {http://www.mrfellows.net/papers/J46-wstar2.pdf}

}

@article{AlonFellowsHare1996,

author = {Noga Alon and Michael R. Fellows and Donovan R. Hare},

title = {Vertex Transversals that Dominate},

journal = {Journal of Graph Theory},

pages = {21–32},

year = {1996},

number = {1},

volume = {21},

publisher = {John Wiley \& Sons},

url = {http://www.mrfellows.net/papers/J36-JGT96.pdf}

}

@article{CattellDinneenFellows1996c,

author = {Kevin Cattell and Michael J. Dinneen and Michael R. Fellows},

title = {A Simple Linear-Time Algorithm for finding

Path-Decompositions of Small Width},

journal = {Information Processing Letters},

pages = {197–203},

year = {1996},

number = {4},

volume = {57},

publisher = {North-Holland Publishing Company},

abstract = {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

path-decomposition 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.},

url = {http://www.mrfellows.net/papers/CDF96_PathDecompOfSmallWidth.pdf}

}

@inproceedings{DowneyFellowsTaylor1996b,

author = {Rod G. Downey and Michael R. Fellows and Udayan Taylor},

title = {The Parameterized Complexity of Relational Database

Queries and an Improved Characterization of {W[1]}},

booktitle = {Proceedings of Combinatorics, Complexity, and Logic, DMTCS’96},

year = {1996},

pages = {194–213},

publisher = {Springer-Verlag},

editor = {D. Bridges and C. Calude and J. Gibbons and S. Reeves

and I. Witten},

url = {http://www.mrfellows.net/papers/C33-relationaldatabase.ps}

}

@article{FellowsFrickeHedetniemiJacobs1994,

author = {Michael Fellows and Gerd Fricke and Stephen Hedetniemi and

David Jacobs},

title = {The Private Neighbor Cube},

journal = {SIAM Journal on Discrete Mathematics},

volume = {7},

number = {1},

pages = {41–47},

year = {1994}

}

@inproceedings{BodlaenderFellowsHallett1994a,

author = {Hans L. Bodlaender and Michael R. Fellows and Michael T. Hallett},

title = {Beyond ${NP}$-completeness for problems of bounded width:

Hardness for the ${W}$ hierarchy},

booktitle = {Proceedings of the 26th Annual ACM Symposium on Theory

of Computing, STOC’94},

pages = {449–458},

year = {1994},

publisher = {ACM Press},

address = {New York},

url = {http://www.mrfellows.net/papers/BFH94_BoundedWidth..pdf}

}

@article{FellowsLangston1992b,

author = {Michael R. Fellows and Michael A. Langston},

title = {On Well-Partial-Order Theory and Its Application to

Combinatorial Problems of {VLSI} Design},

journal = {SIAM Journal on Discrete Mathematics},

volume = {5},

number = {1},

pages = {117–126},

year = {1992}

}

@article{AbelloFellowsStillwell1991,

author = {Abello and Fellows and Stillwell},

title = {On the Complexity and Combinatorics of Covering Finite Complexes},

journal = {AJC: Australasian Journal of Combinatorics},

volume = {4},

year = {1991},

pages = {103–112}

}

@article{FellowsKaschube1991,

author = {Michael R. Fellows and P. A. Kaschube},

title = {Searching for $K_{3,3}$ in Linear Time},

journal = {Linear and Multilinear Algebra},

volume = {29},

number = {3},

pages = {279–290},

year = {1991}

}

@article{FellowsHoover1991,

author = {M. R. Fellows and M. Hoover},

title = {Perfect Domination},

journal = {AJC: Australasian Journal of Combinatorics},

volume = {3},

year = {1991},

pages = {141–150}

}

@article{BarefootClarkDouthettEntringerFellows1991a,

author = {C. A. Barefoot and L. H. Clark and J. Douthett and R. C.

Entringer and M. R. Fellows},

title = {Cycles of Length 0 Modulo 3 in Graphs},

journal = {Annals of Discrete Mathematics},

note = {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},

year = {1991},

pages = {87–101}

}

@article{FellowsWojciechowski1989,

author = {M. R. Fellows and J. M. Wojciechowski},

title = {Counting Spanning Trees in Directed Regular Multigraphs},

journal = {Journal of the Franklin Institute},

volume = {326},

year = {1989},

pages = {889–896}

}

@article{BrownFellowsLangston1989a,

author = {D. J. Brown and M. R. Fellows and M. A. Langston},

title = {Polynomial-Time Self-Reducibility: Theoretical Motivations

and Practical Results},

journal = {International Journal of Computer Mathematics},

volume = {31},

year = {1989},

pages = {1–9}

}

@article{FellowsStueckle1989a,

author = {M. R. Fellows and S. Stueckle},

title = {The Immersion Order, Forbidden Subgraphs and the Complexity

of Network Integrity},

journal = {Journal of Combinatorial Mathematics and Combinatorial Computing},

volume = {6},

year = {1989},

pages = {23–32}

}

@article{FellowsFriesenLangston1988,

author = {Michael R. Fellows and Donald K. Friesen and Michael A. Langston},

title = {On Finding Optimal and Near-Optimal Lineal Spanning Trees},

journal = {Algorithmica},

volume = {3},

number = {4},

pages = {549–560},

year = {1988}

}

@article{FellowsHooverHarary1988,

title = {On the Galactic Number of a Hypercube},

journal = {Mathematical and Computer Modelling},

volume = {11},

pages = {212 – 215},

year = {1988},

author = {Michael Fellows and Mark Hoover and Frank Harary},

abstract = {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 NP-complete.}

}

@inproceedings{BryantFellowsKinnersleyLangston1987a,

author = {R. L. Bryant and Michael R. Fellows and N. G. Kinnersley and

Michael A. Langston},

title = {On Finding Obstruction Sets and Polynomial-Time Algorithms

for Gate Matrix Layout},

booktitle = {Proceedings of the 25th Allerton Conference on

Communication, Control and Computing},

pages = {397–398},

year = {1987}

}

@article{FellowsHicklingSyslo1987,

title = {A Topological Parameterization and Hard Graph Problems},

journal = {Congressus Numerantium},

volume = {59},

pages = {69–78},

year = {1987},

author = {M. Fellows and F. Hickling and M. Syslo}

}

@article{ClarkEntringerFellows1987,

title = {Computational Complexity of Integrity},

journal = {Journal of Combinatorial Mathematics and Combinatorial Computing},

volume = {2},

pages = {179–191},

year = {1987},

author = {L. H. Clark and R. C. Entringer and M. Fellows}

}

@article{BodlaenderDowneyFellowsHermelin2010,

title = {On Problems without Polynomial Kernels},

author = {Hans L. Bodlaender and Rodney G. Downey and Michael R. Fellows and Danny Hermelin},

journal = {Journal of Computer and System Sciences},

note = {To Appear},

year = {2010}

}

@inproceedings{FellowsHromkovicRosamondSteinova2009b,

title = {Fixed-Parameter Tractability, Relative Kernelization and the Effectivization of Structural Connections},

author = {M. Fellows and J. Hromkovic and F. Rosamond and M. Steinova},

booktitle = {Proceedings of CiE’09},

publisher = {Springer-Verlag},

year = {2009},

note = {To Appear},

series = {Lecture Notes in Computer Science},

url = {http://www.mrfellows.net/papers/C102-Cie09abstract.pdf}

}

@inproceedings{Fellows2009b,

title = {The Complexity Ecology of Parameters: Some New Developments and Research Directions},

author = {Michael R. Fellows},

booktitle = {Proceedings of IWOCA’09},

publisher = {Springer-Verlag},

year = {2009},

note = {To Appear},

series = {Lecture Notes in Computer Science},

url = {http://www.mrfellows.net/papers/C101-IWOCA-09.pdf}

}

@article{FellowsLokshtanovMisraMnichRosamondSaurabhb2009,

author = {M.R. Fellows and D. Lokshtanov and N. Misra and M. Mnich and F. Rosamond and S. Saurabh},

title = {The Complexity Ecology of Parameters: An Illustration

Using Bounded Max Leaf Number},

pages = {822-848},

journal = {Theory of Computing Systems},

volume = {45},

year = {2009},

url = {http://www.mrfellows.net/papers/J76-TOCS-09.pdf}

}

@article{BodlaenderFellowsLangstonRaganRosamondWeyer2009,

author = {H. Bodlaender and M.R. Fellows and M. Langston and M. Ragan and F. Rosamond and M. Weyer},

title = {Quadratic Kernelization for Convex Recoloring of Trees},

journal = {Algorithmica},

note = {Accepted to Algorithmica},

year = {2009},

url = {http://www.mrfellows.net/papers/J79-submitted.pdf}

}

@inproceedings{BodlaenderDowneyFellowsHermelin2008b,

title = {On Problems without Polynomial Kernels},

author = {Hans L. Bodlaender and Rodney G. Downey and Michael R.

Fellows and Danny Hermelin},

booktitle = {Automata, Languages and Programming, 35th International

Colloquium, ICALP’08,

Part I: Track A: Algorithms, Automata, Complexity, and

Games},

publisher = {Springer-Verlag},

year = {2008},

volume = {5125},

editor = {Luca Aceto and Ivan Damg{\aa}rd and Leslie Ann Goldberg

and Magn{\’u}s M. Halld{\’o}rsson and Anna Ing{\’o}lfsd{\’o}ttir and

Igor Walukiewicz},

pages = {563–574},

series = {Lecture Notes in Computer Science},

url = {http://www.mrfellows.net/papers/C85-ICALP-08.pdf}

}

@article{Abu-KhzamFellowsLangstonSuters2007b,

title = {Crown Structures for Vertex Cover Kernelization},

author = {Faisal N. Abu-Khzam and Michael R. Fellows and Michael A.

Langston and W. Henry Suters},

publisher = {Springer-Verlag},

year = {2007},

abstract = {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

crown-free subgraph, and the problem of finding a crown of maximum

size in an arbitrary graph, are solvable in polynomial time.},

journal = {Theory of Computing Systems},

number = {3},

volume = {41},

pages = {411–431},

url = {http://www.mrfellows.net/papers/J66-TOCS-crowns.pdf}

}

@inproceedings{FellowsLangstonRosamondShaw2007b,

title = {Efficient Parameterized Preprocessing for Cluster Editing},

author = {Michael R. Fellows and Michael A.. Langston and Frances A.

Rosamond and Peter Shaw},

booktitle = {Proceedings of Fundamentals of Computation Theory, 16th International

Symposium, {FCT}’07},

publisher = {Springer-Verlag},

year = {2007},

volume = {4639},

editor = {Erzs{\’e}bet Csuhaj-Varj{\’u} and Zolt{\’a}n {\’E}sik},

pages = {312–321},

series = {Lecture Notes in Computer Science},

url = {http://www.mrfellows.net/papers/C78-FCT07.pdf}

}

@inproceedings{BodlaenderFellowsLangstonRaganRosamondWeyer2007b,

title = {Quadratic Kernelization for Convex Recoloring of Trees},

author = {Hans L. Bodlaender and Michael R. Fellows and Michael A.

Langston and Mark A. Ragan and Frances A. Rosamond and Mark Weyer},

booktitle = {Proceedings of Computing and Combinatorics, 13th Annual International

Conference, {COCOON}’07},

publisher = {Springer-Verlag},

year = {2007},

volume = {4598},

editor = {Guohui Lin},

pages = {86–96},

series = {Lecture Notes in Computer Science},

url = {http://www.mrfellows.net/papers/C75-COCOON-07.pdf}

}

@inproceedings{BurrageEstivill-CastroFellowsLangstonMacRosamond2006b,

title = {The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel},

author = {Kevin Burrage and Vladimir Estivill-Castro and Michael R.

Fellows and Michael A. Langston and Shev Mac and Frances A. Rosamond},

booktitle = {Proceedings of Parameterized and Exact Computation, Second

International Workshop, IWPEC’06},

publisher = {Springer-Verlag},

year = {2006},

volume = {4169},

editor = {Hans L. Bodlaender and Michael A. Langston},

pages = {192–202},

series = {Lecture Notes in Computer Science},

url = {http://www.mrfellows.net/papers/C68-IWPEC-06.pdf}

}

@inproceedings{Fellows2006b,

author = {M. Fellows},

title = {The Lost Continent of Polynomial Time},

booktitle = {Proceedings of Parameterized and Exact Computation, Second

International Workshop, IWPEC’06},

publisher = {Springer-Verlag},

series = {Lecture Notes in Computer Science},

volume = {4169},

pages = {276 – 277},

year = {2006},

url = {http://www.mrfellows.net/papers/C70-LostContinent.pdf}

}

@inproceedings{Estivill-CastroFellowsLangstonRosamond2005b,

title = {Fixed-Parameter Tractability is Polynomial-Time Extremal

Structure Theory {I}: The Case of Max Leaf},

author = {Vladimir Estivill-Castro and Michael R. Fellows and

Michael A. Langston and Frances A. Rosamond},

booktitle = {Algorithms and Complexity in Durham 2005 – Proceedings

of the First {AC}i{D}},

publisher = {King’s College, London},

year = {2005},

volume = {4},

editor = {Hajo Broersma and Matthew Johnson 0002 and Stefan Szeider},

pages = {1–41},

series = {Texts in Algorithmics},

url = {http://www.mrfellows.net/papers/C65-maxleaf.pdf}

}

@article{AlberFellowsNiedermeier2004b,

author = {J. Alber and M. R. Fellows and R. Niedermeier},

title = {Polynomial-Time Data Reduction for Dominating Set},

abstract = {We prove that Dominating Set restricted to planar graphs

has a kernel of linear size, achieved by two easy-to-implement 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.},

journal = {Journal of the ACM},

volume = {51},

number = {3},

year = {2004},

pages = {363–384},

url = {http://www.mrfellows.net/papers/J58-AlFeNi02.pdf}

}

@inproceedings{Abu-KhzamCollinsFellowsLangstonSutersSymons2004b,

author = {Faisal N. Abu-Khzam and Rebecca L. Collins and Michael R.

Fellows and Michael A. Langston and W. Henry Suters and Christopher T.

Symons},

title = {Kernelization Algorithms for the Vertex Cover Problem:

Theory and Experiments},

pages = {62–69},

editor = {Lars Arge and Guiseppe F. Italiano and Robert Sedgewick},

booktitle = {Proceedings of the sixth Workshop on Algorithm

Engineering and Experiments and the first Workshop on Analytic

Algorithmics and Combinatorics ALENEX’04},

series = {Siam Proceedings Series},

publisher = {Society of Industrial and Applied Mathematics},

year = {2004}

}

@inproceedings{ChorFellowsJuedes2004b,

title = {Linear Kernels in Linear Time, or How to Save $k$ Colors in

{O}(n$^2$) Steps},

author = {Benny Chor and Mike Fellows and David W. Juedes},

booktitle = {Graph-Theoretic Concepts in Computer Science, 30th

International Workshop WG’04},

publisher = {Springer-Verlag},

year = {2004},

volume = {3353},

editor = {Juraj Hromkovic and Manfred Nagl and Bernhard Westfechtel},

pages = {257–269},

series = {Lecture Notes in Computer Science},

url = {http://www.mrfellows.net/papers/CFJ04_LinearKernels.pdf}

}

@inproceedings{AlberFellowsNiedermeier2002b,

title = {Efficient Data Reduction for {DOMINATING} {SET}: {A} Linear

Problem Kernel for the Planar Case},

author = {Jochen Alber and Michael R. Fellows and Rolf Niedermeier},

booktitle = {Proceedings of the 8th Scandinavian

Workshop on Algorithm Theory SWAT’02},

publisher = {Springer-Verlag},

year = {2002},

volume = {2368},

editor = {Martti Penttonen and Erik Meineche Schmidt},

pages = {150–159},

series = {Lecture Notes in Computer Science},

url = {http://www.mrfellows.net/papers/C50-swat2002.pdf}

}

@inproceedings{FellowsMcCartinRosamondStege2000,

title = {Coordinatized Kernels and Catalytic Reductions: An Improved

{FPT} Algorithm for Max Leaf Spanning Tree and Other Problems},

author = {Michael R. Fellows and Catherine McCartin and Frances A.

Rosamond and Ulrike Stege},

booktitle = {Proceedings Foundations of Software Technology and Theoretical

Computer Science, 20th Conference, FST TCS’00},

publisher = {Springer-Verlag},

year = {2000},

volume = {1974},

editor = {Sanjiv Kapoor and Sanjiva Prasad},

pages = {240–251},

series = {Lecture Notes in Computer Science},

url = {http://www.mrfellows.net/papers/C40-KernelsCatalytic-2000.pdf}

}

@inproceedings{BodlaenderFellowsHallett1994b,

author = {Hans L. Bodlaender and Michael R. Fellows and Michael T. Hallett},

title = {Beyond ${NP}$-Completeness for problems of Bounded Width:

Hardness for the ${W}$ Hierarchy},

booktitle = {Proceedings of the 26th Annual ACM Symposium on Theory

of Computing, STOC’94},

pages = {449–458},

year = {1994},

publisher = {ACM Press},

url = {http://www.mrfellows.net/papers/BFH94_BoundedWidth.pdf}

}

@article{CaiFellowsJuedesRosamond2007b,

title = {On The Efficiency of Polynomial-Time Approximation},

author = {Liming Cai and Michael Fellows and David Juedes and

Frances Rosamond},

year = {2007},

journal = {Theory of Computing Systems},

volume = {41},

number = {3},

pages = {459–477},

publisher = {Springer-Verlag New York, Inc.},

address = {Secaucus, NJ, USA},

abstract = {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/{$\epsilon$}$, 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.},

url = {http://www.mrfellows.net/papers/J67-CFJR_jcss(old).pdf}

}

@inproceedings{DowneyFellowsMcCartin2006,

title = {Parameterized Approximation Problems},

author = {Rodney G. Downey and Michael R. Fellows and Catherine McCartin},

booktitle = {Proceedings of Parameterized and Exact Computation, Second

International Workshop, IWPEC’06},

publisher = {Springer},

year = {2006},

volume = {4169},

editor = {Hans L. Bodlaender and Michael A. Langston},

pages = {121–129},

series = {Lecture Notes in Computer Science}

}

@article{FellowsSzeiderWrightson2006,

author = {M. Fellows and S. Szeider and G. Wrightson},

title = {On Finding Short Resolution Refutations and Small

Unsatisfiable Subsets},

pages = {351–359},

journal = {Theoretical Computer Science},

volume = {351},

year = {2006},

abstract = {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 3-SAT formulas and/or to various restricted versions of resolution including tree-like

resolution, input resolution, and read-once resolution.

Applying a metatheorem of Frick and Grohe, we show that restricted to classes of locally bounded treewidth the considered

problems are FPT. Hence, the problems are fixed-parameter tractable for planar CNF formulas and CNF formulas of bounded

genus, $k$-SAT formulas with bounded number of occurrences per variable, and CNF formulas of bounded treewidth. },

url = {http://www.mrfellows.net/papers/J62-ShortResolution-TCS06.pdf}

}

@inproceedings{FellowsSzeiderWrightson2004,

author = {M. Fellows and S. Szeider and G. Wrightson},

title = {On Finding Short Resolution Refutations and Small

Unsatisfiable Subsets},

booktitle = {Proceedings of the First International Workshop on

Parameterized and Exact Computation IWPEC’04},

series = {Lecture Notes in Computer Science },

publisher = {Springer-Verlag },

volume = {3162},

pages = {223–234},

year = {2004},

url = {http://www.mrfellows.net/papers/C60-szeider-wrightson.pdf}

}

@article{DowneyFellows2001b,

author = {R.. Downey and M. Fellows},

title = {Index Sets and Parametric Reductions},

pages = {329–348},

journal = {Archive for Mathematical Logic},

volume = {40},

year = {2001},

number = {5},

url = {http://www.mrfellows.net/papers/J51-IndexSets01.pdf}

}

@inproceedings{FellowsDowneyKapronHallettWareham1994,

author = {M. Fellows and R. Downey and B. Kapron and M. Hallett

and H. T. Wareham},

title = {The Parameterized Complexity of Some Problems in Logic

and Linguistics},

booktitle = {Proceedings of Symposium on Logical Foundations of

Computer Science (LFCS)},

publisher = { Springer-Verlag},

series = {Lecture Notes in Computer Science},

volume = {813},

year = {1994},

pages = {89 — 100 }

}

@article{FellowsMcCartin2003,

author = {M. Fellows and C. McCartin},

title = {On the Parameterized Complexity of Minimizing Tardy Tasks},

journal = {Theoretical Computer Science A},

volume = {298},

year = {2003},

pages = {317–324}

}

@article{BodlaenderFellows1995,

author = {H. Bodlaender and M. Fellows},

title = {On the Complexity of $k$-Processor Scheduling},

journal = {Operations Research Letters},

volume = {18},

pages = {93 – 98},

year = {1995},

url = {http://www.mrfellows.net/papers/BF95_ProcessorScheduling.pdf}

}

@article{FellowsLangston1988c,

author = {M. Fellows and M. A. Langston},

title = {Processor Utilization in a Linearly Connected Parallel

Processing System},

journal = {IEEE Transactions on Computers},

volume = {37},

year = {1988},

pages = {594 – 603}

}

@inproceedings{FellowsFlumHermelinMullerRosamond2007b,

author = {Michael Fellows and J{\”o}rg Flum and Danny Hermelin and

Moritz M{\”u}ller and Frances Rosamond},

title = {Parameterized Complexity via Combinatorial Circuits},

booktitle = {Algorithms and Complexity in Durham 2007, Proceedings of

the third ACiD Workshop},

pages = {55–67},

year = {2007},

editor = {Hajo Broersma and Stefan Dantchev and Matthew Johnson

and Stefan Szeider},

volume = {9},

series = {Texts in Algorithmics},

publisher = {College Publications London},

url = {http://www.mrfellows.net/papers/C80-ACiD07-Circuits.pdf}

}

@article{FellowsHellSeyffarth1998,

author = {M. Fellows and P. Hell and K. Seyffarth},

title = {Constructions of Dense Planar Networks},

journal = {Networks},

volume = {32},

year = {1998},

pages = {275-281}

}

@article{AlonFellowsHare1996a,

author = {N. Alon and M. Fellows and D. O. Hare},

title = {Vertex Transversals That Dominate},

journal = {Journal of Graph Theory},

volume = {21},

year = {1996},

pages = {21–32},

url = {http://www.mrfellows.net/papers/J36-JGT96.pdf}

}

@article{FellowsHellSeyffarth1995,

author = {M. Fellows and P. Hell and K. Seyffarth},

title = {Large Planar Graphs with Given Diameter and Maximum Degree},

journal = {Discrete Applied Math},

volume = {61},

year = {1995},

pages = {133–153}

}

@article{CampbellCarlssonDinneenFaberFellowsLangstonMooreMullhauptSexton1992,

author = {L. Campbell and G. E. Carlsson and M. J. Dinneen and V.

Faber and M. Fellows and M. A. Langston and J. W. Moore and A. P.

Mullhaupt and H. B. Sexton},

title = {Small Diameter Symmetric Networks From Linear Groups},

journal = {IEEE Transactions on Computers},

volume = {40},

year = {1992},

pages = {218-220}

}

@article{BarefootClarkDouthettEntringerFellows1991b,

author = {C. A. Barefoot and L. H. Clark and J. Douthett and R.. C.

Entringer and M. R. Fellows},

title = {Cycles of Length 0 Modulo 3 in Graphs},

journal = {Annals of Discrete Mathematics},

note = {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},

year = {1991},

pages = {87–101}

}

@inproceedings{DinneenFaberFellows1991,

author = {M. Dinneen and V. Faber and M. Fellows},

title = {Algebraic Constructions of Efficient Broadcast Networks},

editor = {H. F. Mattson and T. Mora and T.R.N. Rao},

booktitle = {Proceedings of the Ninth International Symposium on

Applied Algebra, Algebraic Algorithms and Error-Correcting Codes

(AAECC’91)},

series = {Lecture Notes in Computer Science},

publisher = {Springer-Verlag},

volume = {539},

year = {1991},

pages = {152–158}

}

@article{FellowsKleitman1990,

author = {M. Fellows and D. J. Kleitman},

title = {Transversals of Vertex Partitions in Graphs},

journal = { SIAM Journal of Discrete Mathematics},

volume = {3},

year = {1990},

pages = {206-215}

}

@article{FellowsKleitman1989,

author = {M. Fellows and D. J. Kleitman},

title = {Radius and Diameter in Manhattan Lattices},

journal = { Discrete Mathematics},

volume = {73},

year = {1989},

pages = {119–125}

}

@inproceedings{BodlaenderEvansFellows1996,

title = {Finite-State Computability of Annotations of Strings and Trees},

author = {Hans L. Bodlaender and Patricia A. Evans and Michael R. Fellows},

booktitle = {Proceedings of the 7th Annual Symposium on

Combinatorial Pattern Matching: CPM 2006},

editor = {Daniel S. Hirschberg and Eugene W. Myers},

publisher = {Springer},

series = {Lecture Notes in Computer Science},

volume = {1075},

year = {1996},

pages = {384-391}

}

@inproceedings{AbrahamsonFellows1993b,

title = {Finite Automata, Bounded Treewidth and Well-Quasiordering},

author = {Karl R. Abrahamson and Michael R. Fellows},

publisher = {American Mathematical Society },

editor = {N. Robertson and P. Seymour },

booktitle = {Proceedings of the Joint Summer Research Conference on

Graph Minors: Graph Structure Theory, Seattle, June, 1991},

series = {Contemporary Mathematics},

volume = {147},

year = {1993},

pages = {539–564}

}

@inproceedings{FellowsLangston1989c,

author = {M. Fellows and M. Langston},

title = {An analogue of the {M}yhill-{N}erode theorem and its use in

computing finite-basis characterizations},

booktitle = {Proceedings of the 30th Annual IEEE Symposium on

Foundations of Computer Science, FOCS’89 (Research Triangle Park, NC)},

pages = {520–525},

year = {1989},

publisher = {IEEE Computer Society Press}

}

@article{BodlaenderFellowsThilikos2009,

author = {H. Bodlaender and M. Fellows and D. Thilikos},

title = {Derivation of Algorithms for Cutwidth and Related Graph Layout Parameters},

journal = {Journal of Computer and System Sciences},

volume = {75},

page = {231–244},

year = {2009},

abstract = {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 non-deterministic algorithm. The methodology is applied to rederive known results for the

cutwidth and the pathwidth problem, and obtain new results for variants.}

}

@article{FellowsRosamondRoticsSzeider2009,

author = {M. Fellows and F. Rosamond and U. Rotics and S. Szeider},

title = {Cliquewidth is {NP}-{C}omplete},

journal = {SIAM Journal on Discrete Mathematics (SIDMA) },

volume = {23},

number = {2},

page = {909–939},

year = {2009},

abstract = {Clique-width is a graph parameter that measures in a certain sense the complexity of a graph. Hard graph problems (e.g.., problems

expressible in Monadic Second Order Logic with second-order quantification on vertex sets, that includes NP-hard problems) can be

solved efficiently for graphs of certified small clique-width. We show that the clique-width of a given graph cannot be absolutely

approximated in polynomial time unless P=NP. We also show that, given a graph G and an integer k, deciding whether the

clique-width of G is at most k is NP-complete. This solves a problem that has been open since the introduction of clique-width in the

early 1990s},

note = {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 NP-Hardness for Clique-Width I: Non-approximability of Sequential Clique-width, and, Proving NP-Hardness for

Clique-Width II: Non-approximability of Clique-width; Electronic Colloquium on Computational Complexity (ECCC)},

url = {http://www.mrfellows.net/papers/C73-CliquewidthRevision1Aug05.pdf},

url = {http://www.mrfellows.net/papers/C73-CliquewidthIIRevisionAug05.pdf}

}

@inproceedings{AbrahamsonFellowsWilson1992,

title = {Parallel Self-Reducibility},

author = {Karl R. Abrahamson and Michael R. Fellows and Christopher

B. Wilson},

booktitle = {Proceedings of Computing and Information ICCI’92, Fourth

International Conference on Computing and Information},

publisher = {IEEE Computer Society},

year = {1992},

editor = {Waldemar W. Koczkodaj and Peter E. Lauer and Anestis A. Toptsis},

pages = {67–70}

}

@inproceedings{FellowsKoblitz1992b,

author = {Michael R. Fellows and Neal Koblitz},

title = {Self-Witnessing Polynomial-time Complexity and Certificates for Primality},

booktitle = {Proceedings of the 7th Annual Conference on Structure

in Complexity Theory, CSCT’92},

pages = {107–110},

year = {1992},

publisher = {IEEE Computer Society Press},

url = {http://www.mrfellows.net/papers/C13-ccc92-primality.pdf}

}

@article{AbrahamsonFellowsLangstonMoret1991,

author = {Karl Abrahamson and Michael R. Fellows and Michael A.

Langston and Bernard M. E. Moret},

title = {Constructive Complexity},

abstract = {Robinson and Seymour have provided tools for classifying decision problems as solvable in polynomial time that are

powerful and widely applicable, yet inherently non-constructive.

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 self-reducibility and oracle machines, both

conventional and {“}blind,{“}. },

journal = {Discrete Applied Mathematics and Combinatorial

Operations Research and Computer Science},

pages = {3–16},

year = {1991},

volume = {34},

publisher = {North-Holland Publishing Company}

}

@article{FellowsLangston1991,

title = {Fast Search Algorithms for Layout Permutation Problems},

journal = {Integration, the VLSI Journal},

volume = {12},

number = {3},

pages = {321 – 337},

year = {1991},

author = {Michael R. Fellows and Michael A. Langston}

}

@inproceedings{FellowsLangston1989d,

author = {Michael R. Fellows and Michael A. Langston},

title = {On Search, Decision and the Efficiency of Polynomial-time

Algorithms},

booktitle = {Proceedings of the 21st Annual ACM Symposium on Theory

of Computing, STOC’89},

pages = {501–512},

year = {1989},

publisher = {ACM Press},

organization = {ACM SIGACT},

url = {http://www.mrfellows.net/papers/FL89_Search,Decision,Efficiency.pdf}

}

@article{FellowsLangston1987a,

author = {Michael R. Fellows and Michael A. Langston},

title = {Nonconstructive advances in polynomial-time complexity},

journal = {Information Processing Letters},

pages = {157–162},

year = {1987},

number = {3},

volume = {26},

publisher = {North-Holland Publishing Company}

}

@inproceedings{FellowsLangston1988d,

author = {Michael R. Fellows and Michael A. Langston},

title = {Fast self-reduction algorithms for combinatorial problems

of {VLSI} design},

booktitle = {Proceedings of the 3rd Aegean Workshop on Computing:

VLSI Algorithms and Architectures, AWOC’88. Corfu, Greece},

pages = {278–287},

year = {1988},

volume = {319},

series = {LNCS},

editor = {J. H. Reif},

publisher = {Springer-Verlag}

}

@inproceedings{FellowsFominLokshtanovLosievskajaRosamondSaurabh2009c,

author = {Michael R. Fellows and

Fedor V. Fomin and

Daniel Lokshtanov and

Elena Losievskaja and

Frances A. Rosamond and

Saket Saurabh},

title = {Distortion Is Fixed Parameter Tractable},

booktitle = {Proceedings of ICALP 2009 (Track A)},

year = {2009},

pages = {463-474},

url = {http://www.mrfellows.net/papers/C96.pdf}

}

@techreport{FellowsFominLokshtanovLosievskajaRosamondSaurabh2009d,

title = {Parameterized Low-distortion Embeddings – Graph Metrics

into Lines and Trees},

author = {Michael Fellows and Fedor Fomin and Daniel Lokshtanov and

Elena Losievskaja and Frances A. Rosamond and Saket Saurabh},

note = {Manuscript},

year = {2009},

abstract = {We describe algorithms for

finding a low distortion non-contracting 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 NP-Complete for every fixed

rational $d \geq 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 $\Delta$, embedding of $M$

into a shortest path metric of $T$ is FPT, parameterized by

$(\Delta,d)$.}

}

@inproceedings{FellowsGrammNiedermeier2002a,

author = {Michael R. Fellows and Jens Gramm and Rolf Niedermeier},

title = {On the parameterized intractability of Closest Substring

and related problems},

abstract = {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 NP-complete and both

possess polynomial time approximation schemes. We also prove

W[1]-hardness for other parameterizations in the case of unbounded

alphabet size. Our main W[1]-hardness result generalizes to Consensus

Patterns, a problem of significance in computational

biology.},

booktitle = {Proceedings of the 19th Annual Symposium on Theoretical

Aspects of Computer Science, STACS’02},

pages = {262–273},

year = {2002},

volume = {2285},

series = {LNCS},

editor = {Helmut Alt and Afonso Ferreira},

publisher = {Springer-Verlag},

url = {http://www.mrfellows.net/papers/C48-stacs02-substrings.pdf}

}

@inproceedings{BodlaenderEvansFellows1996a,

title = {Finite-State Computability of Annotations of Strings and Trees},

author = {Hans L. Bodlaender and Patricia A. Evans and Michael R. Fellows},

booktitle = {Proceedings of the 7th Annual Symposium on

Combinatorial Pattern Matching: CPM’96},

editor = {Daniel S. Hirschberg and Eugene W. Myers},

publisher = {Springer},

series = {Lecture Notes in Computer Science},

volume = {1075},

year = {1996},

pages = {384-391}

}

@article{BodlaenderDowneyFellowsWareham1995a,

author = {Hans L. Bodlaender and Rodney G. Downey and Michael R.

Fellows and Harold T. Wareham},

title = {The Parameterized Complexity of Sequence Alignment and

Consensus},

journal = {Theoretical Computer Science},

volume = {147},

number = {1{\&}2},

year = {1995},

pages = {31-54},

url = {http://www.mrfellows.net/papers/BDFW95_SeqAlignment.pdf}

}

@article{BodlaenderDowneyFellowsHallettWareham1995c,

author = {Hans L. Bodlaender and Rodney G. Downey and Michael R.

Fellows and Michael T. Hallett and Harold T. Wareham},

title = {Parameterized complexity analysis in computational biology},

journal = {Computer Applications in the Biosciences},

volume = {11},

number = {1},

year = {1995},

pages = {49-57},

url = {http://www.mrfellows.net/papers/BDFHW95CompBio.pdf}

}

@inproceedings{BodlaenderDowneyFellowsWareham1994a,

title = {The Parameterized Complexity of Sequence Alignment and Consensus},

author = {Hans L. Bodlaender and Rodney G. Downey and Michael R.

Fellows and Harold T. Wareham},

booktitle = {Combinatorial Pattern Matching, 5th Annual Symposium,

CPM’94},

publisher = {Springer},

year = {1994},

volume = {807},

editor = {Maxime Crochemore and Dan Gusfield},

pages = {15–30},

series = {Lecture Notes in Computer Science}

}