My publications, sorted by year



2010

[1] Fellows, M. R., Fomin, F. V., and Gutin, G. Special Issue on Parameterized Complexity. Discrete Optimization (2010). To Appear. [ bib ]
[2] Fellows, M. R., Fertin, G., Hermelin, D., and Vialette, S. Sharp tractability borderlines for finding connected motifs in vertex-colored graphs. Computer and System Sciences (2010). To Appear. [ bib ]
[3] Bodlaender, H. L., Downey, R. G., Fellows, M. R., and Hermelin, D. On problems without polynomial kernels. Journal of Computer and System Sciences (2010). To Appear. [ bib ]

2009

[4] Fellows, M. R., Hermelin, D., and Rosamond, F. A. Well-quasi-ordering bounded treewidth graphs. In Proceedings of International Workshop on Parameterized and Exact Computation, IWPEC'09 (2009), Lecture Notes in Computer Science, Springer-Verlag. To Appear. [ bib | link ]
[5] Fellows, M. R. The complexity ecology of parameters: Some new developments and research directions. In Proceedings of IWOCA (2009), Lecture Notes in Computer Science, Springer-Verlag. To Appear. [ bib | link ]
[6] Fellows, M. R., Hermelin, D., Rosamond, F. A., and Vialette, S. On the parameterized complexity of multiple-interval graph problems. Journal of Theoretical Computer Science 410, 1 (2009), 53-61. [ bib | link ]
[7] Fellows, M. R., Guo, J., Komusiewicz, C., Niedermeier, R., and Uhlmann, J. Graph-based data clustering with overlaps. In Proceedings of COCOON (2009), vol. 5609 of Lecture Notes in Computer Science, Springer, pp. 516-526. [ bib | link ]
[8] Fellows, M. R., Guo, J., and Kanj, I. The parameterized complexity of some minimum label problems. In Proceedings of WG (2009), Lecture Notes in Computer Science, Springer-Verlag. To Appear. [ bib | link ]
[9] Fellows, M. R., Hartman, T., Hermelin, D., Landau, G. M., Rosamond, F. A., and Rozenberg, L. Haplotype inference constrained by plausible haplotype data. In Proceedings of the of the 20th Combinatorial Pattern Matching conference, CPM (2009), pp. 339-352. [ bib | link ]
[10] Betzler, N., Fellows, M. R., Guo, J., Niedermeier, R., and Rosamond, F. Fixed-parameter algorithms for Kemeny Rankings. Theoretical Computer Science (2009). Accepted for publication, August 2009, 30 pages. [ bib | link ]
[11] Betzler, N., Fellows, M. R., Guo, J., Niedermeier, R., and Rosamond, F. A. How similarity helps to efficiently compute Kemeny Rankings. In Proceedings of the 8th International Conference on Autonomous Agents and Multiagent Systems AAMAS (2009), pp. 657-664. [ bib | link ]
[12] Fellows, M., Hromkovic, J., Rosamond, F., and Steinova, M. Fixed-parameter tractability, relative kernelization and the effectivization of structural connections. In Proceedings of CiE'09 (2009), Lecture Notes in Computer Science, Springer-Verlag. To Appear. [ bib | link ]
[13] Fellows, M. R., Guo, J., Moser, H., and Niedermeier, R. A complexity dichotomy for finding disjoint solutions of vertex deletion problems. In Proceedings of MFCS'09 (2009), vol. 5734 of Lecture Notes in Computer Science, Springer-Verlag, pp. 319-330. [ bib | link ]
[14] Enciso, R., Fellows, M. R., Guo, J., Kanj, I., Rosamond, F., and Suchy, A. What makes equitable connected partition easy? In Proceedings of International Workshop of Parameterized and Exact Computation, IWPEC'09 (2009), Lecture Notes in Computer Science, Springer-Verlag. To Appear. [ bib ]
[15] Fellows, M., Fomin, F. V., Lokshtanov, D., Rosamond, F., Saurabh, S., and Villanger, Y. Local search: Is brute force avoidable? In Proceedings International Joint Conference on Artificial Intelligence, IJCAI'09 (2009). To Appear. [ bib | link ]
[16] Fellows, M. R., Fomin, F. V., Lokshtanov, D., Losievskaja, E., Rosamond, F. A., and Saurabh, S. Distortion is fixed parameter tractable. In Proceedings of ICALP'09 (Track A) (2009), pp. 463-474. [ bib | link ]
[17] Fellows, M., Fomin, F., Lokshtanov, D., Losievskaja, E., Rosamond, F. A., and Saurabh, S. Parameterized low-distortion embeddings - graph metrics into lines and trees. Tech. rep., 2009. Manuscript. [ bib ]
We describe algorithms for finding a low distortion non-contracting embedding of M into line and tree metrics. We give an O(nd4(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 >=2. This rules out any possibility of an algorithm with running time O((nW)h(d)) where h is a function of d alone. We generalize the result on embedding into the line by proving that for any tree T with maximum degree Δ, embedding of M into a shortest path metric of T is FPT, parameterized by (Δ,d).

[18] Fellows, M., Giannopoulos, P., Knauer, C., Paul, C., Rosamond, F., Whitesides, S., and Yu, N. On the parameterized complexity of the discrete milling problem with turn costs. In Proceedings of FST TCS'09 (2009), Springer-Verlag. To Appear. [ bib ]
[19] M. Dom, M. F., and Rosamond, F. Parameterized complexity of stabbing rectangles and squares in the plane. In Proceedings of the 3rd Workshop on Algorithms and Computation, WALCOM'09 (2009), vol. 5431 of Lecture Notes in Computer Science, Springer-Verlag, pp. 298-309. [ bib | link ]
[20] Fellows, M., Lokshtanov, D., Misra, N., Mnich, M., Rosamond, F., and Saurabh, S. The complexity ecology of parameters: An illustration using bounded max leaf number. Theory of Computing Systems 45 (2009), 822-848. [ bib | link ]
[21] Fellows, M., Guo, J., Moser, H., and Niedermeier, R. A generalization of Nemhauser and Trotter's local optimization algorithm. In Proceedings of STACS'09 (2009), pp. 409-420. [ bib | link ]
[22] Fellows, M., Hromkovic, J., Rosamond, F., and Steinova, M. Fixed-parameter tractability, relative kernelization and the effectivization of structural connections. In Proceedings of CiE'09 (2009), Lecture Notes in Computer Science, Springer-Verlag. To Appear. [ bib | link ]
[23] Fellows, M. R. The complexity ecology of parameters: Some new developments and research directions. In Proceedings of IWOCA'09 (2009), Lecture Notes in Computer Science, Springer-Verlag. To Appear. [ bib | link ]
[24] Fellows, M., Lokshtanov, D., Misra, N., Mnich, M., Rosamond, F., and Saurabh, S. The complexity ecology of parameters: An illustration using bounded max leaf number. Theory of Computing Systems 45 (2009), 822-848. [ bib | link ]
[25] Bodlaender, H., Fellows, M., Langston, M., Ragan, M., Rosamond, F., and Weyer, M. Quadratic kernelization for convex recoloring of trees. Algorithmica (2009). Accepted to Algorithmica. [ bib | link ]
[26] Bodlaender, H., Fellows, M., and Thilikos, D. Derivation of algorithms for cutwidth and related graph layout parameters. Journal of Computer and System Sciences 75 (2009). [ bib ]
This paper shows algorithms for graph parameters that ask for a linear ordering of the vertices of the graph. Constructive linear time algorithms for the fixed parameter versions of the problems have been published for cutwidth, pathwidth, and directed or weighted variants of these and other problems. However, the algorithms have complicated technical details. This paper attempts to present ideas in these algorithms in a more easily accessible manner, by showing that the algorithms can be obtained by a stepwise modification of a non-deterministic algorithm. The methodology is applied to rederive known results for the cutwidth and the pathwidth problem, and obtain new results for variants.

[27] Fellows, M., Rosamond, F., Rotics, U., and Szeider, S. Cliquewidth is NP-Complete. SIAM Journal on Discrete Mathematics (SIDMA) 23, 2 (2009). A preliminary and shortened version of this paper appeared in the proceedings of STOC 2006; 38th ACM Symposium on Theory of Computing, Seattle, Washington, USA, pp. 354—362, ACM Press, 2006. This paper combines the results of the technical reports: Proving 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). [ bib | link | link ]
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

[28] Fellows, M. R., Fomin, F. V., Lokshtanov, D., Losievskaja, E., Rosamond, F. A., and Saurabh, S. Distortion is fixed parameter tractable. In Proceedings of ICALP 2009 (Track A) (2009), pp. 463-474. [ bib | link ]
[29] Fellows, M., Fomin, F., Lokshtanov, D., Losievskaja, E., Rosamond, F. A., and Saurabh, S. Parameterized low-distortion embeddings - graph metrics into lines and trees. Tech. rep., 2009. Manuscript. [ bib ]
We describe algorithms for finding a low distortion non-contracting embedding of M into line and tree metrics. We give an O(nd4(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 >=2. This rules out any possibility of an algorithm with running time O((nW)h(d)) where h is a function of d alone. We generalize the result on embedding into the line by proving that for any tree T with maximum degree Δ, embedding of M into a shortest path metric of T is FPT, parameterized by (Δ,d).

2008

[30] Downey, R., Fellows, M., and Langston, M. The Computer Journal Special Issue on Parameterized Complexity: Foreword by the Guest Editors. The Computer Journal 51, 1 (2008), 1-6. 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. [ bib | link ]
[31] Bodlaender, H. L., Demaine, E. D., Fellows, M. R., Guo, J., Hermelin, D., Lokshtanov, D., Müller, M., Venkatesh Raman, J. v. R., and Rosamond, F. A. Open problems in parameterized and exact computation from iwpec 2008. Tech. Rep. UU-CS-2008-017, Department of Information and Computing Sciences, Utrecht University, 2008. [ bib | link ]
[32] Betzler, N., Fellows, M. R., Komusiewicz, C., and Niedermeier, R. Parameterized algorithms and hardness results for some graph motif problems. In Proceedings of Combinatorial Pattern Matching, 19th Annual Symposium, CPM, (2008), P. Ferragina and G. M. Landau, Eds., vol. 5029 of Lecture Notes in Computer Science, Springer, pp. 31-43. [ bib | link ]
[33] Betzler, N., Fellows, M. R., Guo, J., Niedermeier, R., and Rosamond, F. A. Fixed-parameter algorithms for Kemeny scores. In Proceedings of Algorithmic Aspects in Information and Management, 4th International Conference, AAIM (2008), R. Fleischer and J. Xu, Eds., vol. 5034 of Lecture Notes in Computer Science, Springer-Verlag, pp. 60-71. [ bib | link ]
[34] Betzler, N., Fellows, M. R., Guo, J., Niedermeier, R., and Rosamond, F. A. Computing Kemeny Rankings, parameterized by the average K-T distance. In Proceedings of the 2nd International Workshop on Computational Social Choice, COMSOC (2008). [ bib | link ]
[35] Fellows, M. R., Rosamond, F., and Slinko, A. Sensing God's Will is fixed parameter tractable. Tech. rep., University of Auckland, New Zealand, 2008. University of Auckland, NZ Mathematics Research Report, 9 pages. [ bib | link ]
[36] Fellows, M. R., Hermelin, D., Müller, M., and Rosamond, F. A. A purely democratic characterization of W[1]. In Proceedings of Parameterized and Exact Computation, Third International Workshop IWPEC'08 (2008), M. Grohe and R. Niedermeier, Eds., vol. 5018 of Lecture Notes in Computer Science, Springer-Verlag, pp. 103-114. [ bib | link ]
[37] Bodlaender, H. L., Downey, R. G., Fellows, M. R., and Hermelin, D. On problems without polynomial kernels. In Automata, Languages and Programming, 35th International Colloquium, ICALP'08, Part I: Track A: Algorithms, Automata, Complexity, and Games (2008), L. Aceto, I. Damgård, L. A. Goldberg, M. M. Halldórsson, A. Ingólfsdóttir, and I. Walukiewicz, Eds., vol. 5125 of Lecture Notes in Computer Science, Springer, pp. 563-574. [ bib | link ]
[38] Fellows, M., Flum, J., Hermelin, D., Muller, M., and Rosamond, F. W-hierarchies defined by symmetric gates. Theory of Computing Systems (2008). [ bib | link ]
Originally defined via the weighted satisfiability problem for Boolean circuits, the classes of the 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.

[39] Fellows, M., and Fernau, H. Facility location problems: A parameterized view. In Proceedings of AAIM'08 (2008), vol. 5034 of Lecture Notes in Computer Science, Springer, pp. 188-199. [ bib | link ]
[40] Fellows, M. R., Knauer, C., Nishimura, N., Ragde, P., Rosamond, F., Stege, U., Thilikos, D., and Whitesides, S. Faster fixed parameter tractable algorithms for matching and packing problems. Algorithmica 52, 2 (2008), 167-176. [ bib | link ]
[41] Dujmovic, V., Fellows, M. R., Kitching, M., Liotta, G., McCartin, C., Nishimura, N., Ragde, P., Rosamond, F., Whitesides, S., and Wood, D. R. On the parameterized complexity of layered graph drawing. Algorithmica 52, 2 (2008), 267-292. [ bib | link ]
[42] Fellows, M. R., Meister, D., Rosamond, F. A., Sritharan, R., and Telle, J. A. Leaf powers and their properties: Using the trees. In Proceedings of Algorithms and Computation, 19th International Symposium, ISAAC 2008, Gold Coast, Australia (2008), S.-H. Hong, H. Nagamochi, and T. Fukunaga, Eds., vol. 5369 of Lecture Notes in Computer Science, Springer-Verlag, pp. 402-413. [ bib | link ]
[43] Fellows, M. R., Lokshtanov, D., Misra, N., Rosamond, F. A., and Saurabh, S. Graph layout problems parameterized by vertex cover. In Proceedings of Algorithms and Computation, 19th International Symposium, ISAAC 2008, Gold Coast, Australia (2008), S.-H. Hong, H. Nagamochi, and T. Fukunaga, Eds., vol. 5369 of Lecture Notes in Computer Science, Springer-Verlag, pp. 294-305. [ bib | link ]
[44] Bodlaender, H. L., Fellows, M. R., Heggernes, P., Mancini, F., Papadopoulos, C., and Rosamond, F. A. Clustering with partial information. In Proceedings of Mathematical Foundations of Computer Science, 33rd International Symposium, MFCS 2008, Torun, Poland (2008), E. Ochmanski and J. Tyszkiewicz, Eds., vol. 5162 of Lecture Notes in Computer Science, Springer-Verlag, pp. 144-155. [ bib | link ]
[45] Fellows, M. R., and Fernau, H. Facility location problems: A parameterized view. In Proceedings of Algorithmic Aspects in Information and Management, 4th International Conference, AAIM'08 (2008), R. Fleischer and J. Xu, Eds., vol. 5034 of Lecture Notes in Computer Science, Springer-Verlag, pp. 188-199. [ bib | link ]
[46] Bodlaender, H. L., Downey, R. G., Fellows, M. R., and Hermelin, D. On problems without polynomial kernels. In Automata, Languages and Programming, 35th International Colloquium, ICALP'08, Part I: Track A: Algorithms, Automata, Complexity, and Games (2008), L. Aceto, I. Damgård, L. A. Goldberg, M. M. Halldórsson, A. Ingólfsdóttir, and I. Walukiewicz, Eds., vol. 5125 of Lecture Notes in Computer Science, Springer-Verlag, pp. 563-574. [ bib | link ]

2007

[47] Fellows, M. R., and Rosamond, F. A. The complexity ecology of parameters: An illustration using bounded max leaf number. In Proceedings of Computation and Logic in the Real World, Third Conference on Computability in Europe, CiE, Siena, Italy (2007), S. B. Cooper, B. Löwe, and A. Sorbi, Eds., vol. 4497 of Lecture Notes in Computer Science, Springer, pp. 268-277. [ bib | link ]
[48] Fellows, M., and Rosamond, F. Why is P Not Equal to NP? In Computation and Logic in the Real World: Third Conference on Computability in Europe, CiE 2007: Local Proceedings (2007). [ bib | link ]
[49] Fellows, M. R., Fertin, G., Hermelin, D., and Vialette, S. Sharp tractability borderlines for finding connected motifs in vertex-colored graphs. In Proceedings of Automata, Languages and Programming, 34th International Colloquium, ICALP (2007), L. Arge, C. Cachin, T. Jurdzinski, and A. Tarlecki, Eds., vol. 4596 of Lecture Notes in Computer Science, Springer, pp. 340-351. [ bib | link ]
[50] Fellows, M. R., Langston, M. A., Rosamond, F. A., and Shaw, P. Efficient parameterized preprocessing for cluster editing. In Fundamentals of Computation Theory, 16th International Symposium, FCT, Budapest, Hungary (2007), E. Csuhaj-Varjú and Z. Ésik, Eds., vol. 4639 of Lecture Notes in Computer Science, Springer, pp. 312-321. [ bib | link ]
[51] Christian, R., Fellows, M. R., Rosamond, F., and Slinko, A. On the complexity of lobbying in multiple referenda. Review of Economic Design 11 (2007), 217-224. [ bib | link ]
[52] Fellows, M., Fomin, F. V., Lokshtanov, D., Rosamond, F., Saurabh, S., Szeider, S., and Thomassen., C. On the complexity of some colorful problems parameterized by treewidth. (invited paper). In Proceedings of First International Conference on Combinatorial Optimization and Applications COCOA'07 (2007), vol. 4616 of Lecture Notes in Computer Science, Springer-Verlag, pp. 366-377. [ bib | link ]
We study the complexity of several coloring problems on graphs, parameterized by the treewidth of the graph: 1) The list chromatic number χl(G) of a graph G is defined to be the smallest positive integer r, such that for every assignment to the vertices v of G, of a list Lv of colors, where each list has length at least r, there is a choice of one color from each vertex list Lv yielding a proper coloring of G. We show that the problem of determining whether χl(G)<=r, the LIST CHROMATIC NUMBER problem, is solvable in linear time for every fixed treewidth bound t. The method by which this is shown is new and of general applicability. 2) The LIST COLORING problem takes as input a graph G, together with an assignment to each vertex v of a set of colors Cv. The problem is to determine whether it is possible to choose a color for vertex v from the set of permitted colors Cv , 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.

[53] Cai, L., Fellows, M., Juedes, D., and Rosamond, F. The complexity of polynomial-time approximation. Theory of Computing Systems 41, 3 (2007), 459-477. [ bib | link ]
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/ε. 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.

[54] Fellows, M., Flum, J., Hermelin, D., Müller, M., and Rosamond, F. Parameterized complexity via combinatorial circuits. In Algorithms and Complexity in Durham 2007, Proceedings of the third ACiD Workshop (2007), H. Broersma, S. Dantchev, M. Johnson, and S. Szeider, Eds., vol. 9 of Texts in Algorithmics, College Publications London, pp. 55-67. [ bib | link ]
[55] Bodlaender, H. L., Fellows, M. R., Langston, M. A., Ragan, M. A., Rosamond, F. A., and Weyer, M. Quadratic kernelization for convex recoloring of trees. In Proceedings of Computing and Combinatorics, 13th Annual International Conference, COCOON'07 (2007), G. Lin, Ed., vol. 4598 of Lecture Notes in Computer Science, Springer-Verlag, pp. 86-96. [ bib | link ]
[56] Fellows, M. R., Fomin, F. V., Lokshtanov, D., Rosamond, F. A., Saurabh, S., Szeider, S., and Thomassen, C. On the complexity of some colorful problems parameterized by treewidth. In Proceedings of Combinatorial Optimization and Applications, COCOA'07 (2007), A. W. M. Dress, Y. Xu, and B. Zhu, Eds., vol. 4616 of Lecture Notes in Computer Science, Springer-Verlag, pp. 366-377. [ bib | link ]
[57] Chor, B., Fellows, M. R., Ragan, M. A., Razgon, I., Rosamond, F. A., and Snir, S. Connected coloring completion for general graphs: Algorithms and complexity. In Proceedings of Computing and Combinatorics, 13th Annual International Conference, COCOON'07 (2007), G. Lin, Ed., vol. 4598 of Lecture Notes in Computer Science, Springer-Verlag, pp. 75-85. [ bib | link ]
[58] Fellows, M. R., Langston, M. A., Rosamond, F. A., and Shaw, P. Efficient parameterized preprocessing for cluster editing. In Proceedings of 16th International Symposium Fundamentals of Computation Theory FCT'07 (2007), E. Csuhaj-Varjú and Z. Ésik, Eds., vol. 4639 of Lecture Notes in Computer Science, Springer-Verlag, pp. 312-321. [ bib | link ]
[59] Cai, L., Fellows, M., Juedes, D., and Rosamond, F. The complexity of polynomial-time approximation. Theory of Computing Systems 41, 3 (2007), 459-477. [ bib | link ]
We show that Planar TMIN, Planar TMAX and Planar MPSAT, parameterized by k = 1/ε, are hard for W[1], and thus unlikely that they admit EPTASs. We show that there are EPTASs for some subproblems described by syntactic restrictions, and establish some limits on how far these positive results can be extended.

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

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

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

[63] Fellows, M. R., Langston, M. A., Rosamond, F. A., and Shaw, P. Efficient parameterized preprocessing for cluster editing. In Proceedings of Fundamentals of Computation Theory, 16th International Symposium, FCT'07 (2007), E. Csuhaj-Varjú and Z. Ésik, Eds., vol. 4639 of Lecture Notes in Computer Science, Springer-Verlag, pp. 312-321. [ bib | link ]
[64] Bodlaender, H. L., Fellows, M. R., Langston, M. A., Ragan, M. A., Rosamond, F. A., and Weyer, M. Quadratic kernelization for convex recoloring of trees. In Proceedings of Computing and Combinatorics, 13th Annual International Conference, COCOON'07 (2007), G. Lin, Ed., vol. 4598 of Lecture Notes in Computer Science, Springer-Verlag, pp. 86-96. [ bib | link ]
[65] Cai, L., Fellows, M., Juedes, D., and Rosamond, F. On the efficiency of polynomial-time approximation. Theory of Computing Systems 41, 3 (2007), 459-477. [ bib | link ]
We offer a number of results concerning the problems Planar TMIN, Planar TMAX and Planar MPSAT defined by Khanna and Motwani: (1) We show that each of these problems of approximation, naturally parameterized by k = 1/ε, is hard for W[1], and thus unlikely that they admit EPTASs. (2) We show that there are EPTASs for some subproblems described by syntactic restrictions, and establish some limits on how far these positive results can be extended.

[66] Fellows, M., Flum, J., Hermelin, D., Müller, M., and Rosamond, F. Parameterized complexity via combinatorial circuits. In Algorithms and Complexity in Durham 2007, Proceedings of the third ACiD Workshop (2007), H. Broersma, S. Dantchev, M. Johnson, and S. Szeider, Eds., vol. 9 of Texts in Algorithmics, College Publications London, pp. 55-67. [ bib | link ]

2006

[67] Fellows, M. The lost continent of polynomial time. In Proceedings of IWPEC'06 (2006), vol. 4169 of Lecture Notes in Computer Science, Springer-Verlag, p. 276 – 277. [ bib | link ]
[68] Fellows, M. R., Gramm, J., and Niedermeier, R. On the parameterized intractability of motif search problems. Combinatorica 26, 2 (2006), 141-167. [ bib | link ]
[69] Dujmovic, V., Fellows, M. R., Hallett, M. T., Kitching, M., Liotta, G., McCartin, C., Nishimura, N., Ragde, P., Rosamond, F. A., Suderman, M., Whitesides, S., and Wood, D. R. A fixed-parameter approach to 2-layer planarization. Algorithmica 45, 2 (2006), 159-182. [ bib | link ]
[70] Fellows, M. R., Gramm, J., and Niedermeier, R. On the parameterized intractability of motif search problems. Combinatorica 26, 2 (2006), 141-167. [ bib | link ]
[71] Dehne, F., Fellows, M. R., Fernau, H., Prieto, E., and Rosamond, F. A. NONBLOCKER: Parameterized algorithmics for minimum dominating set. In Proceedings of Theory and Practice of Computer Science, 32nd Conference on Current Trends in Theory and Practice of Computer Science SOFSEM'06 (2006), J. Wiedermann, G. Tel, J. Pokorný, M. Bieliková, and J. Stuller, Eds., vol. 3831 of Lecture Notes in Computer Science, Springer-Verlag, pp. 237-245. [ bib | link ]
[72] Fellows, M. R., Rosamond, F. A., Rotics, U., and Szeider, S. Clique-width minimization is NP-hard. In Proceedings of the 38th Annual Symposium on Theory of Computing, ACM'06 (2006), J. M. Kleinberg, Ed., ACM, pp. 354-362. [ bib | link ]
[73] Burrage, K., Estivill-Castro, V., Fellows, M. R., Langston, M. A., Mac, S., and Rosamond, F. A. The undirected feedback vertex set problem has a poly(k) kernel. In Proceedings of Parameterized and Exact Computation, Second International Workshop, IWPEC'06 (2006), H. L. Bodlaender and M. A. Langston, Eds., vol. 4169 of Lecture Notes in Computer Science, Springer-Verlag, pp. 192-202. [ bib | link ]
[74] Bodlaender, H. L., Fellows, M. R., Langston, M. A., Ragan, M. A., Rosamond, F. A., and Weyer, M. Kernelization for convex recoloring. In Proceedings of Algorithms and Complexity in Durham, ACiD'06 (2006), H. Broersma, S. S. Dantchev, M. J. 0002, and S. Szeider, Eds., vol. 7 of Texts in Algorithmics, King's College, London, pp. 23-36. Accepted to Algorithmica. [ bib | link ]
[75] Burrage, K., Estivill-Castro, V., Fellows, M. R., Langston, M. A., Mac, S., and Rosamond, F. A. The undirected feedback vertex set problem has a poly(k) kernel. In Proceedings of Parameterized and Exact Computation, Second International Workshop, IWPEC'06 (2006), H. L. Bodlaender and M. A. Langston, Eds., vol. 4169 of Lecture Notes in Computer Science, Springer-Verlag, pp. 192-202. [ bib | link ]
[76] Fellows, M. The lost continent of polynomial time. In Proceedings of Parameterized and Exact Computation, Second International Workshop, IWPEC'06 (2006), vol. 4169 of Lecture Notes in Computer Science, Springer-Verlag, p. 276 – 277. [ bib | link ]
[77] Downey, R. G., Fellows, M. R., and McCartin, C. Parameterized approximation problems. In Proceedings of Parameterized and Exact Computation, Second International Workshop, IWPEC'06 (2006), H. L. Bodlaender and M. A. Langston, Eds., vol. 4169 of Lecture Notes in Computer Science, Springer, pp. 121-129. [ bib ]
[78] Fellows, M., Szeider, S., and Wrightson, G. On finding short resolution refutations and small unsatisfiable subsets. Theoretical Computer Science 351 (2006), 351-359. [ bib | link ]
We consider the parameterized problems of whether a given set of clauses can be refuted within k resolution steps, and whether a given set of clauses contains an unsatisfiable subset of size at most k. We show that both problems are complete for W[1]. Our results remain true if restricted to 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.

2005

[79] Chen, J., Chor, B., Fellows, M., Huang, X., Juedes, D. W., Kanj, I. A., and Xia, G. Tight lower bounds for certain parameterized NP-hard problems. Information and Computation 201, 2 (2005), 216-231. [ bib | link ]
[80] Alber, J., Fan, H., Fellows, M. R., Fernau, H., Niedermeier, R., Rosamond, F., and Stege, U. A refined search tree technique for dominating set on planar graphs. Journal of Computer and System Sciences 71, 4 (2005), 385-405. [ bib | link ]
[81] Dehne, F. K. H. A., Fellows, M. R., Langston, M. A., Rosamond, F. A., and Stevens, K. An O(2O(k)n3) FPT algorithm for the undirected feedback vertex set problem. In Proceedings of Computing and Combinatorics, 11th Annual International Conference, COCOON'05 (2005), L. Wang, Ed., vol. 3595 of Lecture Notes in Computer Science, Springer-Verlag, pp. 859-869. [ bib | link ]
[82] Estivill-Castro, V., Fellows, M. R., Langston, M. A., and Rosamond, F. A. Fixed-parameter tractability is polynomial-time extremal structure theory I: The case of max leaf. In Proceedings of Algorithms and Complexity in Durham, ACiD 2005 (2005), H. Broersma, M. J. 0002, and S. Szeider, Eds., vol. 4 of Texts in Algorithmics, King's College, London, pp. 1-41. [ bib | link ]
[83] Estivill-Castro, V., Fellows, M. R., Langston, M. A., and Rosamond, F. A. Fixed-parameter tractability is polynomial-time extremal structure theory I: The case of max leaf. In Algorithms and Complexity in Durham 2005 - Proceedings of the First ACiD (2005), H. Broersma, M. J. 0002, and S. Szeider, Eds., vol. 4 of Texts in Algorithmics, King's College, London, pp. 1-41. [ bib | link ]

2004

[84] Dehne, F. K., Fellows, M. R., Rosamond, F. A., and Shaw, P. Greedy localization, iterative compression, modeled crown reductions: New FPT techniques, an improved algorithm for set splitting, and a novel 2k kernelization for vertex cover. In Proceedings of Parameterized and Exact Computation, First International Workshop, IWPEC 2004, Bergen, Norway (2004), R. G. Downey, M. R. Fellows, and F. K. Dehne, Eds., vol. 3162 of Lecture Notes in Computer Science, Springer, pp. 271-280. [ bib | link ]
[85] Fellows, M. R. A survey of FPT algorithm design techniques with an emphasis on recent advances and connections to practical computing. In Proceedings of 12th Annual European Symposium ESA, Bergen, Norway (2004), S. Albers and T. Radzik, Eds., vol. 3221 of Lecture Notes in Computer Science, Springer-Verlag, pp. 1-2. [ bib | link ]
[86] Alber, J., Fellows, M. R., and Niedermeier, R. Polynomial-time data reduction for dominating set. Journal of the ACM 51, 3 (2004), 363-384. [ bib | link ]
We demonstrate the power of data reduction by preprocessing from a theoretical as well as a practical side. In particular, we prove that Dominating Set restricted to planar graphs has a problem kernel of linear size, achieved by two 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.

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

[88] Abu-Khzam, F. N., Collins, R. L., Fellows, M. R., Langston, M. A., Suters, W. H., and Symons, C. T. Kernelization algorithms for the Vertex Cover problem: Theory and experiments. In Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the first Workshop on Analytic Algorithmics and Combinatorics ALENEX'04 (2004), L. Arge, G. F. Italiano, and R. Sedgewick, Eds., Siam Proceedings Series, Society of Industrial and Applied Mathematics, pp. 62-69. [ bib ]
[89] Fellows, M. R., Knauer, C., Nishimura, N., Ragde, P., Rosamond, F. A., Stege, U., Thilikos, D. M., and Whitesides, S. Faster fixed-parameter tractable algorithms for matching and packing problems. In Proceedings of 12th Annual European Symposium on Algorithms ESA'04 (2004), S. Albers and T. Radzik, Eds., vol. 3221 of Lecture Notes in Computer Science, Springer-Verlag, pp. 311-322. [ bib | link ]
[90] Fellows, M., Heggernes, P., Rosamond, F. A., Sloper, C., and Telle, J. A. Finding k disjoint triangles in an arbitrary graph. In Proceedings of Graph-Theoretic Concepts in Computer Science, 30th International Workshop,WG'04 (2004), J. Hromkovic, M. Nagl, and B. Westfechtel, Eds., vol. 3353 of Lecture Notes in Computer Science, Springer-Verlag, pp. 235-244. [ bib | link ]
[91] Chor, B., Fellows, M., and Juedes, D. W. Linear kernels in linear time, or how to save k colors in O(n2) steps. In Proceedings of Graph-Theoretic Concepts in Computer Science, 30th International Workshop,WG'04 (2004), J. Hromkovic, M. Nagl, and B. Westfechtel, Eds., vol. 3353 of Lecture Notes in Computer Science, Springer-Verlag, pp. 257-269. [ bib | link ]
[92] Alber, J., Fellows, M. R., and Niedermeier, R. Polynomial-time data reduction for dominating set. Journal of the ACM 51, 3 (2004), 363-384. [ bib | link ]
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.

[93] Abu-Khzam, F. N., Collins, R. L., Fellows, M. R., Langston, M. A., Suters, W. H., and Symons, C. T. Kernelization algorithms for the vertex cover problem: Theory and experiments. In Proceedings of the sixth Workshop on Algorithm Engineering and Experiments and the first Workshop on Analytic Algorithmics and Combinatorics ALENEX'04 (2004), L. Arge, G. F. Italiano, and R. Sedgewick, Eds., Siam Proceedings Series, Society of Industrial and Applied Mathematics, pp. 62-69. [ bib ]
[94] Chor, B., Fellows, M., and Juedes, D. W. Linear kernels in linear time, or how to save k colors in O(n2) steps. In Graph-Theoretic Concepts in Computer Science, 30th International Workshop WG'04 (2004), J. Hromkovic, M. Nagl, and B. Westfechtel, Eds., vol. 3353 of Lecture Notes in Computer Science, Springer-Verlag, pp. 257-269. [ bib | link ]
[95] Fellows, M., Szeider, S., and Wrightson, G. On finding short resolution refutations and small unsatisfiable subsets. In Proceedings of the First International Workshop on Parameterized and Exact Computation IWPEC'04 (2004), vol. 3162 of Lecture Notes in Computer Science, Springer-Verlag, pp. 223-234. [ bib | link ]

2003

[96] Chen, J., and Fellows, M. Foreword from the Guest Editors. Journal of Computer and System Sciences 67 (2003), 653-654. Special Issue on Parameterized Complexity,. [ bib ]
[97] Fellows, M. R. Blow-ups, win/win's, and crown rules: Some new directions in FPT. In Proceedings of the 29th International Workshop on Graph-Theoretic Concepts in Computer Science, WG'2003, Elspeet, The Netherlands (2003), H. L. Bodlaender, Ed., vol. 2880 of Lecture Notes in Computer Science, Springer-Verlag, pp. 1-12. [ bib | link ]
This survey reviews the basic notions of parameterized complexity, and describes some new approaches to designing FPT algorithms and problem reductions for graph problems.

[98] Fellows, M. R. New directions and new challenges in algorithm design and complexity, parameterized. In Proceedings of Algorithms and Data Structures, 8th International Workshop WADS (2003), F. K. H. A. Dehne, J.-R. Sack, and M. H. M. Smid, Eds., vol. 2748 of Lecture Notes in Computer Science, Springer-Verlag, pp. 505-520. [ bib | link ]
[99] Fellows, M. R., Hallett, M., and Stege, U. Analogs & duals of the MAST problem for sequences & trees. Journal of Algorithms 49 (2003), 192 - 216. [ bib | link ]
[100] Downey, R. G., Estivill-Castro, V., Fellows, M. R., Prieto, E., and Rosamond, F. A. Cutting up is hard to do: the parameterized complexity of k-cut and related problems. Electronic Notes in Theoretical Computer Science 78 (2003), 205-218. [ bib | link ]
[101] Bell, T., Fellows, M., Witten, I., and Koblitz, N. Explaining cryptographic systems to the general public. Computers and Education 40 (2003), 199-215. [ bib ]
[102] Bell, T., Fellows, M., Koblitz, N., and Witten, I. Explaining cryptographic ideas to the general public. Computers and Education 40 (2003), 199—215. [ bib | link ]
[103] Fellows, M. R., Hallett, M., and Stege, U. Analogs and duals of the MAST problem for sequences & trees. Journal of Algorithms 49 (2003), 192 - 216. [ bib | link ]
[104] Downey, R. G., Estivill-Castro, V., Fellows, M. R., Prieto, E., and Rosamond, F. A. Cutting up is hard to do: the parameterized complexity of k-cut and related problems. Electronic Notes in Theoretical Computer Science 78 (2003), 205-218. [ bib | link ]
[105] Fellows, M. R. Blow-ups, win/win's, and crown rules: Some new directions in FPT. In Proceedings of the 29th International Workshop on Graph-Theoretic Concepts in Computer Science, WG'03 (2003), H. L. Bodlaender, Ed., vol. 2880 of LNCS, Springer-Verlag, pp. 1-12. [ bib | link ]
This survey reviews the basic notions of parameterized complexity, and describes some new approaches to designing FPT algorithms and problem reductions for graph problems.

[106] Dehne, F., Fellows, M. R., and Rosamond, F. A. An FPT algorithm for set splitting. In Proceedings of the 29th International Workshop on Graph-Theoretic Concepts in Computer Science, WG'03 (2003), H. L. Bodlaender, Ed., vol. 2880 of Lecture Notes in Computer Science, Springer-Verlag, pp. 180-191. [ bib | link ]
An FPT algorithm with a running time of O(n 4 + 2O(k) n2.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 2o(k) nc unless the satisfiability of n-variable 3SAT instances can be decided in time 2o(n).

[107] Bodlaender, H. L., Fellows, M. R., and Thilikos, D. M. Starting with nondeterminism: The systematic derivation of linear-time graph layout algorithms. In Proceedings of Mathematical Foundations of Computer Science MFCS'03 (2003), B. Rovan and P. Vojtás, Eds., vol. 2747 of Lecture Notes in Computer Science, Springer, pp. 239-248. [ bib | link ]
[108] Fellows, M., and McCartin, C. On the parameterized complexity of minimizing tardy tasks. Theoretical Computer Science A 298 (2003), 317-324. [ bib ]

2002

[109] Fellows, M. R. Parameterized complexity: The main ideas and connections to practical computing. In Experimental Algorithmics (2002), R. Fleischer, B. M. E. Moret, and E. M. Schmidt, Eds., vol. 2547 of Lecture Notes in Computer Science, Springer-Verlag, pp. 51-77. [ bib | link ]
[110] Fellows, M. R., Gramm, J., and Niedermeier, R. On the parameterized intractability of closest substring and related problems. In Proceedings of the 19th Annual Symposium on Theoretical Aspects of Computer Science, STACS'02 (2002), H. Alt and A. Ferreira, Eds., vol. 2285 of Lecture Notes in Computer Science, Springer-Verlag, pp. 262-273. [ bib | link ]
We show that Closest Substring, one of the most important problems in the field of biological sequence analysis, is W[1]-hard with respect to the number k of input strings (even over a binary alphabet). This problem is therefore unlikely to be solvable in time O(f(k)n) for any function f and constant c independent of k. Effectively, the problem can be expected to be intractable, in any practical sense, for k 3. Our result supports the intuition that Closest Substring is computationally much harder than the special case of Closest String, although both problems are 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.

[111] Alber, J., Fellows, M. R., and Niedermeier, R. Efficient data reduction for DOMINATING SET: A linear problem kernel for the planar case. In Proceedings of 8th Scandinavian Workshop on Algorithm Theory SWAT'02 (2002), M. Penttonen and E. M. Schmidt, Eds., vol. 2368 of Lecture Notes in Computer Science, Springer, pp. 150-159. [ bib | link ]
[112] Ellis, J., Fan, H., and Fellows, M. R. The dominating set problem is fixed parameter tractable for graphs of bounded genus. In Proceedings of SWAT 2002: Scandinavian Workshop on Algorithm Theory (2002), M. Penttonen and E. M. Schmidt, Eds., vol. 2368 of LNCS, Springer, pp. 180-189. [ bib | link ]
[113] Alber, J., Fellows, M. R., and Niedermeier, R. Efficient data reduction for DOMINATING SET: A linear problem kernel for the planar case. In Proceedings of the 8th Scandinavian Workshop on Algorithm Theory SWAT'02 (2002), M. Penttonen and E. M. Schmidt, Eds., vol. 2368 of Lecture Notes in Computer Science, Springer-Verlag, pp. 150-159. [ bib | link ]
[114] Fellows, M. R., Gramm, J., and Niedermeier, R. On the parameterized intractability of closest substring and related problems. In Proceedings of the 19th Annual Symposium on Theoretical Aspects of Computer Science, STACS'02 (2002), H. Alt and A. Ferreira, Eds., vol. 2285 of LNCS, Springer-Verlag, pp. 262-273. [ bib | link ]
We show that Closest Substring, one of the most important problems in the field of biological sequence analysis, is W[1]-hard with respect to the number k of input strings (even over a binary alphabet). This problem is therefore unlikely to be solvable in time O(f(k)n) for any function f and constant c independent of k. Our result supports the intuition that Closest Substring is computationally much harder than the special case of Closest String, although both problems are 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.

2001

[115] Cattell, K., Dinneen, M. J., and Fellows, M. R. Forbidden minors to graphs with small feedback sets. Discrete Mathematics 230, 1-3 (2001), 215-252. [ bib | link ]
[116] Fellows, M. R. Parameterized complexity: New developments and research frontiers. In Aspects of Complexity (2001), De Gruyter, pp. 51-72. [ bib | link ]
[117] Fellows, M. R. Some new developments in parameterized complexity. In Proceedings of the 12th Australasian Workshop on Combinatorial Algorithms (2001), E. T. Baskoro, Ed., pp. 43-44. [ bib | link ]
[118] Fellows, M. R. Parameterized complexity: Main ideas, connections to heuristics and research frontiers. In Proceedings of ISAAC (2001), vol. 2223 of Lecture Notes in Computer Science, Springer-Verlag, pp. 291-307. [ bib | link ]
[119] Downey, R. G., and Fellows, M. R. Index sets and parametric reductions. Archive for Mathematical Logic 40, 5 (2001), 329-348. [ bib | link ]
[120] Dujmovic, V., Fellows, M. R., Hallett, M. T., Kitching, M., Liotta, G., McCartin, C., Nishimura, N., Ragde, P., Rosamond, F. A., Suderman, M., Whitesides, S., and Wood, D. R. A fixed-parameter approach to two-layer planarization. In Proceedings of the 9th International Symposium on Graph Drawing GD'01 (2001), vol. 2265 of Lecture Notes in Computer Science, Springer-Verlag, pp. 1-15. [ bib | link ]
[121] Dujmović, V., Fellows, M., Hallett, M., Kitching, M., Liotta, G., McCartin, C., Nishimura, N., Ragde, P., Rosamond, F., Suderman, M., Whitesides, S., and Wood, D. R. On the parameterized complexity of layered graph drawing. In Proceedings of the 9th Annual European Symposium on Algorithms, ESA '01 (2001), vol. 2161 of Lecture Notes in Computer Science, Springer-Verlag, pp. 488-499. [ bib ]
[122] Alber, J., Fan, H., Fellows, M. R., Fernau, H., Niedermeier, R., Rosamond, F. A., and Stege, U. A refined search tree technique for DOMINATING SET on planar graphs. In Proceedings of 26th International Symposium Mathematical Foundations of Computer Science, MFCS'01 (2001), J. Sgall, A. Pultr, and P. Kolman, Eds., vol. 2136 of Lecture Notes in Computer Science, Springer-Verlag, pp. 111-122. [ bib | link ]
We establish refined search tree techniques for the parameterized Dominating Set problem on planar graphs. We prove an intricate branching theorem based on the Euler formula. In addition, we give a family of example graphs showing that the bound of the branching theorem is optimal with respect to our reduction rules. Our final algorithm is easy to implement; its analysis, however, is involved.

[123] Downey, R., and Fellows, M. Index sets and parametric reductions. Archive for Mathematical Logic 40, 5 (2001), 329-348. [ bib | link ]

2000

[124] Cattell, K., Dinneen, M. J., Downey, R. G., and Fellows, M. R. On computing graph minor obstruction sets. Theoretical Computer Science 233, 1 (2000), 107-127. [ bib | link ]
[125] Bodlaender, H. L., Fellows, M. R., Hallett, M. T., Wareham, H. T., and Warnow, T. J. The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs. Theoretical Computer Science A 244, 1-2 (2000), 167-188. [ bib | link ]
In this paper, we consider the complexity of a number of combinatorial problems; namely, Intervalizing Colored Graphs (DNA physical mapping), Triangulating Colored Graphs (perfect phylogeny), (Directed) (Modified) Colored Cutwidth, Feasible Register Assignment and Module Allocation for graphs of bounded pathwidth. Each of these problems has as a characteristic a uniform upper bound on the tree or path width of the graphs in "yes"-instances. For all of these problems with the exceptions of Feasible Register Assignment and Module Allocation, a vertex or edge coloring is given as part of the input. Our main results are that the parameterized variant of each of the considered problems is hard for the complexity classes W [t] for all t 2 N. We also show that Intervalizing Colored Graphs, Triangulating Colored Graphs, and Colored Cutwidth are NP-Complete.

[126] Downey, R. G., Fellows, M. R., and Raman, V. The complexity of irredundant sets parameterized by size. Discrete Applied Mathematics 100, 3 (2000), 155-167. [ bib | link ]
[127] Bodlaender, H. L., Fellows, M. R., Hallett, M. T., Wareham, H. T., and Warnow, T. J. The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs. Theoretical Computer Science A 244, 1-2 (2000), 167-188. [ bib | link ]
We consider the complexity of Intervalizing Colored Graphs (DNA physical mapping), Triangulating Colored Graphs (perfect phylogeny), (Directed) (Modified) Colored Cutwidth, Feasible Register Assignment and Module Allocation for graphs of bounded pathwidth. Each of these problems has a uniform upper bound on the tree or pathwidth of the graphs in "yes"-instances. For all of these problems with the exceptions of Feasible Register Assignment and Module Allocation, a vertex or edge coloring is given as part of the input. Our main results are that the parameterized variant of each of the considered problems is hard for W [t] for all t 2 N. We also show that Intervalizing Colored Graphs, Triangulating Colored Graphs, and Colored Cutwidth are NP-Complete.

[128] Fellows, M. R., McCartin, C., Rosamond, F. A., and Stege, U. Coordinatized kernels and catalytic reductions: An improved FPT algorithm for max leaf spanning tree and other problems. In Proceedings of Foundations of Software Technology and Theoretical Computer Science, 20th Conference, FST TCS '00 (2000), S. Kapoor and S. Prasad, Eds., vol. 1974 of Lecture Notes in Computer Science, Springer-Verlag, pp. 240-251. [ bib | link ]
[129] Fellows, M. R., McCartin, C., Rosamond, F. A., and Stege, U. Coordinatized kernels and catalytic reductions: An improved FPT algorithm for max leaf spanning tree and other problems. In Proceedings Foundations of Software Technology and Theoretical Computer Science, 20th Conference, FST TCS'00 (2000), S. Kapoor and S. Prasad, Eds., vol. 1974 of Lecture Notes in Computer Science, Springer-Verlag, pp. 240-251. [ bib | link ]

1999

[130] Downey, R. G., and Fellows, M. R. Parameterized Complexity. Springer-Verlag, 1999. 530 pp. [ bib ]
[131] Downey, R. G., Fellows, M. R., and Stege, U. Parameterized complexity: A framework for systematically confronting computational intractability. In Contemporary Trends in Discrete Mathematics: From DIMACS and DIMATIA to the Future, vol. 49 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science. DIMACS, 1999, pp. 49-99. [ bib | link ]
In this paper we give a programmatic overview of parameterized computational complexity in the broad context of the problem of coping with computational intractability. We give some examples of how 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.

[132] Downey, R. G., Fellows, M. R., and Stege, U. Computational Tractability: A View from Mars. Tech. rep., 1999. [ bib | link ]
[133] Downey, R. G., and Fellows, M. R. Parameterized complexity after (almost) 10 years: Review and open questions. In Proceedings of Combinatorics, Computation and Logic, DMTCS'99 and CATS'99 (Singapore, 1999), vol. 21 of Australian Computer Science Communications, Springer-Verlag, pp. 1-33. [ bib | link ]
[134] Downey, R. G., Fellows, M. R., Vardy, A., and Whittle, G. The parametrized complexity of some fundamental problems in coding theory. SIAM Journal of Computing 29, 2 (1999), 545-570. [ bib | link ]
The parametrized complexity of a number of fundamental problems in the theory of linear codes and integer lattices is explored. Concerning codes, the main results are that 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.

[135] Bell, T., Fellows, M., Koblitz, N., and Witten, I. Explaining cryptographic systems to the general public. In Proceedings of the First IFIP World Conference on Information Security Education (WISE) (1999), L. Yngstgröm and S. Fischer-Hübner, Eds., vol. 99-008, Stockholm University Report Series, p. 221—233. [ bib ]

1998

[136] Fellows, M., Hallett, M. T., Korostensky, C., and Stege, U. Analogs and duals of the MAST problem for sequences and trees. In Proceedings of the 6th Annual European Symposium on Algorithms (1998), G. Bilardi, G. F. Italiano, A. Pietracaprina, and G. P. cci, Eds., no. 1461 in Lecture Notes in Computer Science, Springer-Verlag, Berlin, pp. 103-114. [ bib | link ]
Two natural kinds of problems about "structured collections of symbols" can be generally refered to as the Largest Common Subobject and the Smallest Common Superobject problems, which we consider here as the dual problems of interest. For the case of rooted binary trees where the symbols occur as 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.

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

[138] Downey, R. G., and Fellows, M. R. Threshold dominating sets and an improved characterization of W[2]. Theoretical Computer Science 209, 1-2 (1998), 123-140. [ bib | link ]
[139] Downey, R. G., Fellows, M. R., and Regan, K. W. Parameterized circuit complexity and the W hierarchy. Theoretical Computer Science A 191, 1-2 (1998), 97-115. [ bib | link ]
[140] Fellows, M., Hallett, M. T., Korostensky, C., and Stege, U. Analogs and duals of the MAST problem for sequences and trees. In Proceedings of the 6th Annual European Symposium on Algorithms (1998), G. Bilardi, G. F. Italiano, A. Pietracaprina, and G. P. cci, Eds., no. 1461 in Lecture Notes in Computer Science, Springer-Verlag, Berlin, pp. 103-114. [ bib | link ]
Two natural kinds of problems about "structured collections of symbols" can be generally refered to as the Largest Common Subobject and the Smallest Common Superobject problems, which we consider here as the dual problems of interest. For the case of rooted binary trees where the symbols occur as 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.

[141] Balasubramanian, Fellows, and Raman. An improved fixed-parameter algorithm for vertex cover. IPL: Information Processing Letters 65, 3 (1998), 163-168. [ bib | link ]
[142] Downey, R. G., and Fellows, M. R. Threshold dominating sets and an improved characterization of W[2]. Theoretical Computer Science 209, 1-2 (1998), 123-140. [ bib | link ]
[143] Fellows, M., Hell, P., and Seyffarth, K. Constructions of dense planar networks. Networks 32 (1998), 275-281. [ bib ]

1997

[144] Courcelle, B., Downey, R. G., and Fellows, M. R. A note on the computability of graph minor obstruction sets for monadic second order ideals. Journal of Universal Computer Science 3, 11 (1997), 1194-1198. [ bib | link ]
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.

[145] Cai, L., Chen, J., Downey, R. G., and Fellows, M. R. Advice classes of parameterized tractability. Annals of Pure and Applied Logic 84, 1 (1997), 119-138. [ bib | link ]
[146] Cai, L., Chen, J., Downey, R. G., and Fellows, M. R. The parameterized complexity of short computation and factorization. Archive for Mathematical Logic 36 (1997), 321-338. [ bib | link ]
We study the parameterized complexity of: (1) problems concerning parameterized computations of Turing machines, such as determining whether a nondeterministic machine can reach an accept state in steps (the Short TM Computation Problem), and (2) problems concerning derivations and factorizations, such as determining whether a word can be derived in a grammar in steps, or whether a permutation has a factorization of length over a given set of generators. We show hardness and completeness for these problems for various levels of the hierarchy.

[147] Downey, R., Fellows, M., and Regan, K. Descriptive complexity and the W hierarchy. In Proof Complexity and Feasible Arithmetics, P. Beame and S. Buss, Eds., AMS-DIMACS Series in Discrete Mathematics and Theoretical Computer Science. American Mathematical Society, 1997, pp. 119-134. [ bib | link ]
[148] Downey, R. G., Fellows, M. R., Vardy, A., and Whittle, G. The parametrized complexity of some fundamental problems of linear codes and integral lattices. Tech. rep., 1997. Manuscript. [ bib | link ]
[149] Casey, N., and Fellows, M. Implementing the standards: Let’s focus on the first four. DIMACS Series: Discrete Mathematics in the Schools. How Can We Have an Impact? (1997). [ bib | link ]

1996

[150] Bell, T., Fellows, M. R., and Witten, I. Computer Science Unplugged ... offline activities and games for all ages: Teacher Edition. Computer Science Unplugged, 1996. There are currently two versions of the book. The "Teachers' Edition" which is aimed at people with less of a technical background. It has 12 activities, and a lot more illustrations and handouts. Both books are available in Download from http://www.lulu.com. [ bib ]
Many important topics in computer science can be taught without using computers at all. This series of activities unplugs computer science by providing 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.

[151] Fellows, M. R., Bell, T., and Witten, I. Computer Science Unplugged ... offline activities and games for all ages: Original Activities Book. Computer Science Unplugged, 1996. [ bib ]
There are currently two versions of the book. This original edition is aimed for people with some technical interest. This 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.

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

[153] Cattell, K., Dinneen, M. J., and Fellows, M. R. Forbidden minors to graphs with small feedback sets. Tech. rep., 1996. Preprint. Journal publication is “Discrete Mathematics” (2000),. [ bib | link ]
[154] Bailey, I., Cattell, K., Fellows, M. R., Koop, B., Olafson, R., Olafson, R., and Upton, C. Approaches to detection of distantly related proteins by database searches. BioTechniques 21 (1996), 1118 - 1125. [ bib ]
[155] Downey, R. G., Fellows, M. R., and Taylor, U. The parameterized complexity of relational database queries and an improved characterization of W[1]. In Combinatorics, Complexity, and Logic – Proceedings of DMTCS ’96 (1996), D. Bridges, C. Calude, J. Gibbons, S. Reeves, and I. Witten, Eds., Springer-Verlag, pp. 194-213. [ bib | link ]
[156] Cesati, M., and Fellows, M. Sparse parameterized problems. Annals of Pure and Applied Logic 82 (1996), 1-15. [ bib | link ]
[157] Fellows, M. The heart of puzzling: Mathematics and computer games. In Proceedings of the 1996 Computer Games Developers Conference (1996), Miller Freeman, p. 109—120. [ bib | link ]
[158] Alon, N., Fellows, M. R., and Hare, D. R. Vertex transversals that dominate. Journal of Graph Theory 21, 1 (1996), 21-32. [ bib | link ]
[159] Cattell, K., Dinneen, M. J., and Fellows, M. R. A simple linear-time algorithm for finding path-decompositions of small width. Information Processing Letters 57, 4 (1996), 197-203. [ bib | link ]
We describe a simple algorithm running in linear time for each fixed constant k, that either establishes that the pathwidth of a graph G is greater than k, or finds a path-decomposition of G of width at most O(2k). This provides a simple proof of the result by Bodlaender that many families of graphs of bounded pathwidth can be recognized in linear time.

[160] Downey, R. G., Fellows, M. R., and Taylor, U. The parameterized complexity of relational database queries and an improved characterization of W[1]. In Proceedings of Combinatorics, Complexity, and Logic, DMTCS'96 (1996), D. Bridges, C. Calude, J. Gibbons, S. Reeves, and I. Witten, Eds., Springer-Verlag, pp. 194-213. [ bib | link ]
[161] Alon, N., Fellows, M., and Hare, D. O. Vertex transversals that dominate. Journal of Graph Theory 21 (1996), 21-32. [ bib | link ]
[162] Bodlaender, H. L., Evans, P. A., and Fellows, M. R. Finite-state computability of annotations of strings and trees. In Proceedings of the 7th Annual Symposium on Combinatorial Pattern Matching: CPM 2006 (1996), D. S. Hirschberg and E. W. Myers, Eds., vol. 1075 of Lecture Notes in Computer Science, Springer, pp. 384-391. [ bib ]
[163] Bodlaender, H. L., Evans, P. A., and Fellows, M. R. Finite-state computability of annotations of strings and trees. In Proceedings of the 7th Annual Symposium on Combinatorial Pattern Matching: CPM'96 (1996), D. S. Hirschberg and E. W. Myers, Eds., vol. 1075 of Lecture Notes in Computer Science, Springer, pp. 384-391. [ bib ]

1995

[164] Fellows, M., Kratochvil, J., Middendorf, M., and Pfeiffer, F. The complexity of induced minors and related problems. Algorithmica 13, 3 (1995), 266-282. [ bib | link ]
The computational complexity of a number of problems concerning induced structures in graphs is studied, and compared with the complexity of corresponding problems concerning 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.

[165] Cattell, K., Dinneen, M. J., and Fellows, M. R. Obstructions to within a few vertices or edges of acyclic. In Proceedings of the 4th International Workshop on Algorithms and Data Structures, WADS'95 (1995), S. G. Akl, F. Dehne, J.-R. Sack, and N. Santoro, Eds., vol. 955 of Lecture Notes in Computer Science, Springer-Verlag, pp. 415-427. [ bib | link ]
Finite obstruction sets for lower ideals in the minor order are guaranteed to exist by the Graph Minor Theorem. It has been known for several years that, in principle, obstruction sets can be mechanically computed for most natural lower ideals. In this paper, we describe a generalpurpose method for finding obstructions by using a bounded treewidth (or pathwidth) search. We illustrate this approach by characterizing certain families of 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.

[166] Abrahamson, K., Downey, R. G., and Fellows, M. R. Fixed-parameter tractability and completeness IV: On completeness for W[P] and PSPACE analogs. Annals of Pure and Applied Logic 73 (1995), 235-276. [ bib | link ]
[167] Cai, L., Chen, J., Downey, R., and Fellows, M. On the structure of parameterized problems in NP. Information and Computation 123, 1 (1995), 38-49. [ bib ]
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.

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

[169] Downey, R., and Fellows, M. R. Fixed-parameter tractability and completeness II: Completeness for W[1]. Theoretical Computer Science A 141 (1995), 109-131. Preliminary versions of some of the results of this paper were presented at the 21st Manitoba Conference on Numerical Mathematics and Computation, 1991. [ bib | link ]
[170] Downey, R., and Fellows, M. R. Fixed-parameter tractability and completeness I: Basic theory. Siam Journal of Computing 24 (1995), 873-921. Preliminary versions of some of the results of this paper were presented at the 21st Manitoba Conference on Numerical Mathematics and Computation, 1991. [ bib | link ]
[171] Bodlaender, H. L., Downey, R. G., Fellows, M. R., Hallett, M. T., and Wareham, H. T. Parameterized complexity analysis in computational biology. Computer Applications in the Biosciences 11, 1 (1995), 49-57. [ bib | link ]
[172] Bodlaender, H. L., Downey, R. G., Fellows, M. R., and Wareham, H. T. The parameterized complexity of sequence alignment and consensus. Theoretical Computer Science 147, 1&2 (1995), 31-54. [ bib | link ]
[173] Abrahamson, K., Downey, R. G., and Fellows, M. R. Fixed-parameter tractability and completeness IV: On completeness for W[P] and PSPACE analogs. Annals of Pure and Applied Logic 73 (1995), 235-276. [ bib | link ]
[174] Downey, R. G., and Fellows, M. R. Fixed-parameter tractability and completeness II: On completeness for W[1]. Theoretical Computer Science 141, 1&2 (1995), 109-131. [ bib | link ]
[175] Cai, L., Chen, J., Downey, R., and Fellows, M. On the structure of parameterized problems in NP. Information and Computation 123, 1 (1995), 38-49. [ bib ]
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.

[176] Downey, R. G., and Fellows, M. R. Fixed-parameter tractability and completeness I: Basic results. SIAM Journal of Computing 24, 4 (1995), 873-921. [ bib | link ]
[177] Bodlaender, H., and Fellows, M. On the complexity of k-processor scheduling. Operations Research Letters 18 (1995), 93 – 98. [ bib | link ]
[178] Fellows, M., Hell, P., and Seyffarth, K. Large planar graphs with given diameter and maximum degree. Discrete Applied Math 61 (1995), 133-153. [ bib ]
[179] Bodlaender, H. L., Downey, R. G., Fellows, M. R., and Wareham, H. T. The parameterized complexity of sequence alignment and consensus. Theoretical Computer Science 147, 1&2 (1995), 31-54. [ bib | link ]
[180] Bodlaender, H. L., Downey, R. G., Fellows, M. R., Hallett, M. T., and Wareham, H. T. Parameterized complexity analysis in computational biology. Computer Applications in the Biosciences 11, 1 (1995), 49-57. [ bib | link ]

1994

[181] Fellows, M. R., and Langston, M. A. On search, decision and the efficiency of polynomial-time algorithms. Journal of Computer and System Sciences (1994), 769-779. [ bib | link ]
[182] Bodlaender, H. L., Downey, R. G., Fellows, M. R., and Wareham, H. T. The parameterized complexity of sequence alignment and consensus. In Proceedings of Combinatorial Pattern Matching, 5th Annual Symposium, CPM (1994), M. Crochemore and D. Gusfield, Eds., vol. 807 of Lecture Notes in Computer Science, Springer, pp. 15-30. [ bib ]
[183] Bodlaender, H. L., Downey, R. G., Fellows, M. R., Hallett, M. T., and Wareham, H. T. Parameterized complexity analysis in computational biology. Proceedings of the IEEE Computer Society Workshop on Shape and Pattern Recognition in Computational Biology (1994), 99-116. IBM TJ Watson Research Center Publication. [ bib ]
[184] Cai, L., Chen, J., Downey, R. G., and Fellows, M. R. On the structure of parameterized problems in NP. In Proceedings of 11th Annual Symposium on Theoretical Aspects of Computer Science, STACS'94, Caen, France (1994), P. Enjalbert, E. W. Mayr, and K. W. Wagner, Eds., vol. 775 of Lecture Notes in Computer Science, Springer, pp. 509-520. [ bib ]
[185] Fellows, M., and Koblitz, N. Combinatorial cryptosystems galore! In Proceedings of the Second International Symposium on Finite Fields, Las Vegas, Nevada, August, 1993 (1994), vol. 168 of Contemporary Mathematics, American Mathematical Society, pp. 51-61. [ bib | link ]
[186] Fellows, M., Hibner, A., and Koblitz, N. Cultural aspects of mathematics education reform. Notices of the American Mathematics Society 41 (1994), 5—9. [ bib ]
[187] Fellows, M., Fricke, G., Hedetniemi, S., and Jacobs, D. The private neighbor cube. SIAM Journal on Discrete Mathematics 7, 1 (1994), 41-47. [ bib ]
[188] Bodlaender, H. L., Fellows, M. R., and Hallett, M. T. Beyond NP-completeness for problems of bounded width: Hardness for the W hierarchy. In Proceedings of the 26th Annual ACM Symposium on Theory of Computing, STOC'94 (New York, 1994), ACM Press, pp. 449-458. [ bib | link ]
[189] Bodlaender, H. L., Fellows, M. R., and Hallett, M. T. Beyond NP-completeness for problems of bounded width: Hardness for the W hierarchy. In Proceedings of the 26th Annual ACM Symposium on Theory of Computing, STOC'94 (1994), ACM Press, pp. 449-458. [ bib | link ]
[190] Fellows, M., Downey, R., Kapron, B., Hallett, M., and Wareham, H. T. The parameterized complexity of some problems in logic and linguistics. In Proceedings of Symposium on Logical Foundations of Computer Science (LFCS) (1994), vol. 813 of Lecture Notes in Computer Science, Springer-Verlag, pp. 89 - 100. [ bib ]
[191] Bodlaender, H. L., Downey, R. G., Fellows, M. R., and Wareham, H. T. The parameterized complexity of sequence alignment and consensus. In Combinatorial Pattern Matching, 5th Annual Symposium, CPM'94 (1994), M. Crochemore and D. Gusfield, Eds., vol. 807 of Lecture Notes in Computer Science, Springer, pp. 15-30. [ bib ]

1993

[192] Abrahamson, K. R., and Fellows, M. R. Finite automata, bounded treewidth and well-quasiordering. In Proceedings of the Joint Summer Research Conference on Graph Minors: Graph Structure Theory, Seattle, June, 1991 (1993), N. Robertson and P. Seymour, Eds., vol. 147 of Contemporary Mathematics, American Mathematical Society, pp. 539-564. [ bib ]
[193] Abrahamson, K., Downey, R., and Fellows, M. R. Fixed-parameter intractability II. In Proceedings of the 10th Symposium on Theoretical Aspects of Computer Sciences, STACS'93 (1993), vol. 665 of Lecture Notes in Computer Science, Springer-Verlag, pp. 374-385. [ bib ]
[194] Fellows, M. R., Hallett, M. T., and Wareham, H. T. DNA physical mapping: Three ways difficult. In Proceedings of the 1st Annual European Symposium on Algorithms, ESA '93, T. Lengauer, Ed., vol. 726 of Lecture Notes in Computer Science. Springer-Verlag, 1993, pp. 157-168. [ bib ]
[195] Downey, R., and Fellows, M. Fixed-parameter tractability and completeness III: Some structural aspects of the W hierarchy. In Complexity Theory: Current Research - Proceedings of the 1992 Dagstuhl Workshop on Structural Complexity (Cambridge, 1993), K. Ambos-Spies, S. Homer, and U. Schöning, Eds., Cambridge University Press, pp. 191-225. [ bib ]
[196] Abrahamson, K. A., Downey, R. G., and Fellows, M. R. Fixed-parameter intractability II. In Proceedings of the 10th Annual Symposium on Theoretical Aspects of Computer Science, STACS'93 (1993), P. Enjalbert, A. Finkel, and K. W. Wagner, Eds., vol. 665 of Lecture Notes in Computer Science, Springer-Verlag, pp. 374-385. [ bib ]
[197] Fellows, M. R., and Koblitz, N. Fixed-parameter complexity and cryptography. In Proceedings of 10th International Symposium Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC'93, San Juan de Puerto Rico, Puerto Rico (1993), G. D. Cohen, T. Mora, and O. Moreno, Eds., vol. 673 of Lecture Notes in Computer Science, Springer, pp. 121-131. [ bib ]
[198] Downey, R. G., Evans, P. A., and Fellows, M. R. Parameterized learning complexity. In Proceedings of the Sixth Annual ACM Conference on Computational Learning Theory (1993), ACM Press, pp. 51-57. [ bib | link ]
[199] Fellows, M., and Koblitz, N. Kid krypto. In Proceedings of Crypto 1992 (1993), vol. 740 of Lecture Notes in Computer Science, Springer-Verlag, New York, Inc., p. 371—389. [ bib | link ]
[200] Fellows, M. Computer science in the elementary schools. In Proceedings of the Mathematicians and Education Reform Workshop, Seattle, 1991 (1993), N. Fisher, H. Keynes, and P. Wagreich, Eds., vol. 3 of Issues in Mathematics Education, Conference Board of the Mathematical Sciences, p. 143 –163. [ bib | link ]
[201] Abrahamson, K. R., and Fellows, M. R. Finite automata, bounded treewidth and well-quasiordering. In Proceedings of the Joint Summer Research Conference on Graph Minors: Graph Structure Theory, Seattle, June, 1991 (1993), N. Robertson and P. Seymour, Eds., vol. 147 of Contemporary Mathematics, American Mathematical Society, pp. 539-564. [ bib ]

1992

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

[203] Fellows, M. R., and Langston, M. A. On well-partial-order theory and its application to combinatorial problems of VLSI design. SIAM Journal on Discrete Mathematics 5, 1 (1992), 117-126. [ bib ]
[204] Bodlaender, H. L., Fellows, M. R., and Warnow, T. J. Two strikes against perfect phylogeny. In Proceedings of the 19th International Colloquium on Automata, Languages and Programming, ICALP'92 (1992), W. Kuich, Ed., vol. 623 of Lecture Notes in Computer Science, Springer-Verlag, pp. 273-283. [ bib | link ]
[205] Downey, R., and Fellows, M. Fixed-parameter intractability. In Proceedings of the Seventh Annual IEEE Conference on Structure in Complexity Theory (1992), pp. 36-49. [ bib ]
[206] Downey, R., and Fellows, M. Fixed-parameter tractability and completeness. Congressus Numerantium 87 (1992), 161-178. [ bib ]
[207] Fellows, M. R., and Koblitz, N. Self-witnessing polynomial-time complexity and prime factorization. In Proceedings of the 7th Annual Conference on Structure in Complexity Theory, CSCT'92 (1992), IEEE Computer Society Press, pp. 107-110. [ bib | link ]
[208] Fellows, M. R., and Koblitz, N. Self-witnessing polynomial-time complexity and prime factorization. Designs, Codes and Cryptography 2, 3 (1992), 231-235. [ bib ]
[209] Casey, N., and Fellows, M. R. This is Mega-Mathematics! Los Alamos National Labs, 1992. Available at http://www.c3.lanl.gov/ captors/mega-math. See also www.ccs3.lanl.gov/mega-math/write.html. [ bib | link ]
A collection of classroom lessons in mathematics and computer science. Each lesson contains extensive background material that assumes that the topic of the lesson is new to the teacher. Topics include map coloring, graph theory, knot theory, finite state machines, algorithms, logic and infinity.

[210] Fellows, M. R., and Langston, M. A. On well-partial-order theory and its application to combinatorial problems of VLSI design. SIAM Journal on Discrete Mathematics 5, 1 (1992), 117-126. [ bib ]
[211] Campbell, L., Carlsson, G. E., Dinneen, M. J., Faber, V., Fellows, M., Langston, M. A., Moore, J. W., Mullhaupt, A. P., and Sexton, H. B. Small diameter symmetric networks from linear groups. IEEE Transactions on Computers 40 (1992), 218-220. [ bib ]
[212] Abrahamson, K. R., Fellows, M. R., and Wilson, C. B. Parallel self-reducibility. In Proceedings of Computing and Information ICCI'92, Fourth International Conference on Computing and Information (1992), W. W. Koczkodaj, P. E. Lauer, and A. A. Toptsis, Eds., IEEE Computer Society, pp. 67-70. [ bib ]
[213] Fellows, M. R., and Koblitz, N. Self-witnessing polynomial-time complexity and certificates for primality. In Proceedings of the 7th Annual Conference on Structure in Complexity Theory, CSCT'92 (1992), IEEE Computer Society Press, pp. 107-110. [ bib | link ]

1991

[214] Dinneen, M. J., Fellows, M. R., and Faber, V. Algebraic constructions of efficient broadcast networks. In Proceedings of Applied Algebra, Algebraic Algorithms and Error-Correcting Codes AAECC'91 (Berlin, Germany, 1991), H. F. Mattson, T. Mora, and T. R. N. Rao, Eds., vol. 539 of LNCS, Springer-Verlag, pp. 152-158. [ bib ]
[215] Abello, Fellows, and Stillwell. On the complexity and combinatorics of covering finite complexes. AJC: Australasian Journal of Combinatorics 4 (1991), 103-112. [ bib ]
[216] Fellows, M. R., and Kaschube, P. A. Searching for k3,3 in linear time. Linear and Multilinear Algebra 29, 3 (1991), 279-290. [ bib ]
[217] Fellows, M. R., and Hoover, M. Perfect domination. AJC: Australasian Journal of Combinatorics 3 (1991), 141-150. [ bib ]
[218] Barefoot, C. A., Clark, L. H., Douthett, J., Entringer, R. C., and Fellows, M. R. Cycles of length 0 modulo 3 in graphs. Annals of Discrete Mathematics (1991), 87-101. An earlier paper was presented at Graph theory, Combinatorics, and Applications, Volume 1. Proceedings of the Sixth Quadrennial International Conference on the Theory and Applications of Graphs. [ bib ]
[219] Barefoot, C. A., Clark, L. H., Douthett, J., Entringer, R. C., and Fellows, M. R. Cycles of length 0 modulo 3 in graphs. Annals of Discrete Mathematics (1991), 87-101. An earlier paper was presented at Graph theory, Combinatorics, and Applications, Volume 1. Proceedings of the Sixth Quadrennial International Conference on the Theory and Applications of Graphs. [ bib ]
[220] Dinneen, M., Faber, V., and Fellows, M. Algebraic constructions of efficient broadcast networks. In Proceedings of the Ninth International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes (AAECC'91) (1991), H. F. Mattson, T. Mora, and T. Rao, Eds., vol. 539 of Lecture Notes in Computer Science, Springer-Verlag, pp. 152-158. [ bib ]
[221] Abrahamson, K., Fellows, M. R., Langston, M. A., and Moret, B. M. E. Constructive complexity. Discrete Applied Mathematics and Combinatorial Operations Research and Computer Science 34 (1991), 3-16. [ bib ]
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,".

[222] Fellows, M. R., and Langston, M. A. Fast search algorithms for layout permutation problems. Integration, the VLSI Journal 12, 3 (1991), 321 - 337. [ bib ]

1990

[223] Fellows, M., and Kleitman, D. J. Transversals of vertex partitions in graphs. SIAM Journal of Discrete Mathematics 3 (1990), 206-215. [ bib ]

1989

[224] Fellows, M. R. The Robertson-Seymour theorems: A survey of applications. In CMGA: Graphs and Algorithms: Contemporary Mathematics (1989), vol. 89, AMS, pp. 1-18. [ bib ]
[225] Brown, D. J., Fellows, M. R., and Langston, M. A. Polynomial-time self-reducibility: Theoretical motivations and practical results. International Journal of Computer Mathematics 31 (1989), 1-9. [ bib ]
[226] Fellows, M. R., and Stueckle, S. The immersion order, forbidden subgraphs and the complexity of network integrity. Journal of Combinatorial Mathematics and Combinatorial Computing 6 (1989), 23-32. [ bib ]
[227] Fellows, M., and Langston, M. An analogue of the Myhill-Nerode theorem and its use in computing finite-basis characterizations. In Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, FOCS'89 (1989), IEEE Computer Society Press, pp. 520-525. [ bib ]
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.

[228] Fellows, M., Kinnersley, N., and Langston, M. Finite-basis theorems and a computation-integrated approach to obstruction set isolation. In Proceedings of the Third Conference on Computers and Mathematics (1989), E. Kaltofen and S. M. Watt, Eds., Springer-Verlag, pp. 37-45. [ bib ]
[229] Fellows, M. R., and Langston, M. An analogue of the Myhill-Nerode theorem and its use in computing finite-basis characterizations. In Proceedings of 30th annual Symposium on Foundations of Computer Science FOCS'89 (1989), IEEE Computer Society Press, pp. 520-525. [ bib | link ]
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.

[230] Abrahamson, K. R., Fellows, M. R., Ellis, J. A., and Mata, M. E. On the complexity of fixed parameter problems. In Proceedings of 30th annual Symposium on Foundations of Computer Science FOCS'89 (1989), IEEE Computer Society Press, pp. 210-215. [ bib | link ]
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.

[231] Fellows, M. R., and Wojciechowski, J. M. Counting spanning trees in directed regular multigraphs. Journal of the Franklin Institute 326 (1989), 889-896. [ bib ]
[232] Brown, D. J., Fellows, M. R., and Langston, M. A. Polynomial-time self-reducibility: Theoretical motivations and practical results. International Journal of Computer Mathematics 31 (1989), 1-9. [ bib ]
[233] Fellows, M. R., and Stueckle, S. The immersion order, forbidden subgraphs and the complexity of network integrity. Journal of Combinatorial Mathematics and Combinatorial Computing 6 (1989), 23-32. [ bib ]
[234] Fellows, M., and Kleitman, D. J. Radius and diameter in manhattan lattices. Discrete Mathematics 73 (1989), 119-125. [ bib ]
[235] Fellows, M., and Langston, M. An analogue of the Myhill-Nerode theorem and its use in computing finite-basis characterizations. In Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, FOCS'89 (Research Triangle Park, NC) (1989), IEEE Computer Society Press, pp. 520-525. [ bib ]
[236] Fellows, M. R., and Langston, M. A. On search, decision and the efficiency of polynomial-time algorithms. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing, STOC'89 (1989), ACM SIGACT, ACM Press, pp. 501-512. [ bib | link ]

1988

[237] Fellows, M. R., and Langston, M. A. Nonconstructive tools for proving polynomial-time decidability. Journal of the ACM 35, 3 (1988), 727-739. [ bib | link ]
[238] Fellows, M. R., and Langston, M. A. Layout permutation problems and well-partially-ordered sets. In Proceedings of the fifth MIT conference on Advanced research in VLSI (Cambridge, MA, USA, 1988), MIT Press, pp. 315-327. [ bib ]
[239] Fellows, M. R., and Langston, M. A. Fast self-reduction algorithms for combinatorial problems of VLSI design. In Proceedings of the 3rd Aegean Workshop on Computing: VLSI Algorithms and Architectures, AWOC'88. Corfu, Greece (1988), J. H. Reif, Ed., vol. 319 of Lecture Notes in Computer Science, Springer-Verlag, pp. 278-287. [ bib ]
[240] Fellows, M. R., Friesen, D. K., and Langston, M. A. On finding optimal and near-optimal lineal spanning trees. Algorithmica 3, 4 (1988), 549-560. [ bib ]
[241] Fellows, M., Hoover, M., and Harary, F. On the galactic number of a hypercube. Mathematical and Computer Modelling 11 (1988), 212 - 215. [ bib ]
A galaxy is a union of vertex disjoint stars. The galactic number of a graph is the minimum number of galaxies which partition the edge set. The galactic number of complete graphs is determined. This result is used to give bounds on the galactic number of binary cube graphs. The problem of determining the galactic number of a graph is shown to be NP-complete.

[242] Fellows, M., and Langston, M. A. Processor utilization in a linearly connected parallel processing system. IEEE Transactions on Computers 37 (1988), 594 – 603. [ bib ]
[243] Fellows, M. R., and Langston, M. A. Fast self-reduction algorithms for combinatorial problems of VLSI design. In Proceedings of the 3rd Aegean Workshop on Computing: VLSI Algorithms and Architectures, AWOC'88. Corfu, Greece (1988), J. H. Reif, Ed., vol. 319 of LNCS, Springer-Verlag, pp. 278-287. [ bib ]

1987

[244] Fellows, M. R., and Langston, M. A. Nonconstructive advances in polynomial-time complexity. Information Processing Letters 26, 3 (1987), 157-162. [ bib ]
[245] R. L. Bryant, N. G. Kinnersley, M. R. F., and Langston, M. A. On finding obstruction sets and polynomial-time algorithms for gate matrix layout. In Proceedings of the 25th Allerton Conference on Communication, Control and Computing (1987), pp. 397-398. [ bib ]
[246] Bryant, R. L., Fellows, M. R., Kinnersley, N. G., and Langston, M. A. On finding obstruction sets and polynomial-time algorithms for gate matrix layout. In Proceedings of the 25th Allerton Conference on Communication, Control and Computing (1987), pp. 397-398. [ bib ]
[247] Fellows, M., Hickling, F., and Syslo, M. A topological parameterization and hard graph problems. Congressus Numerantium 59 (1987), 69-78. [ bib ]
[248] Clark, L. H., Entringer, R. C., and Fellows, M. Computational complexity of integrity. Journal of Combinatorial Mathematics and Combinatorial Computing 2 (1987), 179-191. [ bib ]
[249] Fellows, M. R., and Langston, M. A. Nonconstructive advances in polynomial-time complexity. Information Processing Letters 26, 3 (1987), 157-162. [ bib ]

Unpublished

[250] Downey, R., Fellows, M., and Mccartin, C. Parameterized approximation problems. Tech. rep. [ bib ]