Parameterized Computational Feasibility
The DOI matches its Crossref record; 23 of the 23 references it cites were found in a registry or an index.
Abstract
Many natural computational problems have input consisting of two or more parts. For example, the input might consist of a graph and a positive integer. For many natural problems we may view one of the inputs as a parameter and study how the complexity of the problem varies if the parameter is held fixed. For many applications of computational problems involving such a parameter, only a small range of parameter values is of practical significance, so that fixed- parameter complexity is a natural concern. In studying the complexity of such problems, it is therefore important to have a framework in which we can make qualitative distinctions about the contribution of the parameter to the complexity of the problem. In this paper we survey one such framework for investigating parameterized computational complexity and present a number of new results for this theory. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
(1979) · Cited by 43,841
Valiant, L. G. (1984) · Communications of the ACM · doi:10.1145/1968.1972 · Cited by 3,279
Learning regular sets from queries and counterexamples
Angluin, D. (1987) · Information and Computation · doi:10.1016/0890-5401(87)90052-6 · Cited by 2,114
Learnability and the Vapnik-Chervonenkis dimension
Blumer, A., Ehrenfeucht, A., Haussler, D., & Warmuth, M. K. (1989) · Journal of the ACM · doi:10.1145/76359.76371 · Cited by 1,839
Combinatorial Problems and Exercises
(1993) · Elsevier eBooks · doi:10.1016/c2009-0-09109-0 · Cited by 1,312
Graph Minors .XIII. The Disjoint Paths Problem
Robertson, N., & Seymour, P. D. (1995) · Journal of Combinatorial Theory, Series B · doi:10.1006/jctb.1995.1006 · Cited by 1,262
On the Structure of Polynomial Time Reducibility
Ladner, R. E. (1975) · Journal of the ACM · doi:10.1145/321864.321877 · Cited by 781
Fixed-Parameter Tractability and Completeness I: Basic Results
Downey, R. G., & Fellows, M. R. (1995) · SIAM Journal on Computing · doi:10.1137/s0097539792228228 · Cited by 468
Self-citationEfficient algorithms for inferring evolutionary trees
Gusfield, D. (1991) · Networks · doi:10.1002/net.3230210104 · Cited by 399
Finding a Minimum Circuit in a Graph
Itai, A., & Rodeh, M. (1978) · SIAM Journal on Computing · doi:10.1137/0207033 · Cited by 391
Buss, J. F., & Goldsmith, J. (1993) · SIAM Journal on Computing · doi:10.1137/0222038 · Cited by 308
Two strikes against perfect phylogeny
Bodlaender, H. L., Fellows, M. R., & Warnow, T. J. (1992) · Lecture notes in computer science · doi:10.1007/3-540-55719-9_80 · Cited by 214
Self-citationGraph minors. IV. Tree-width and well-quasi-ordering
Robertson, N., & Seymour, P. D. (1990) · Journal of Combinatorial Theory Series B · doi:10.1016/0095-8956(90)90120-o · Cited by 210
On Limited Nondeterminism and the Complexity of the V-C Dimension
Papadimitriou, C. H., & Yannakakis, M. (1996) · Journal of Computer and System Sciences · doi:10.1006/jcss.1996.0058 · Cited by 198
An implementation for a fast public-key cryptosystem
Agnew, G. B., Mullin, R. C., Onyszchuk, I. M., & Vanstone, S. A. (1991) · Journal of Cryptology · doi:10.1007/bf00196789 · Cited by 196
Fixed-parameter tractability and completeness IV: On completeness for W[P] and PSPACE analogues
Abrahamson, K. A., Downey, R. G., & Fellows, M. R. (1995) · Annals of Pure and Applied Logic · doi:10.1016/0168-0072(94)00034-z · Cited by 158
Self-citationOn search decision and the efficiency of polynomial-time algorithms
Fellows, M. R., & Langston, M. A. (1989) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/73007.73055 · Cited by 143
Self-citationFinding a minimum circuit in a graph
Itai, A., & Rodeh, M. (1977) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/800105.803390 · Cited by 136
Exact and Approximate Solutions for the Gate Matrix Layout Problem
Deo, N., Krishnamoorthy, M. S., & Langston, M. A. (1987) · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · doi:10.1109/tcad.1987.1270248 · Cited by 82
On the Amount of Nondeterminism and the Power of Verifying
Cai, L., & Chen, J. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539793258295 · Cited by 57
Fixed-parameter complexity and cryptography
Fellows, M. R., & Koblitz, N. (1993) · Lecture notes in computer science · doi:10.1007/3-540-56686-4_38 · Cited by 47
Self-citationOn limited nondeterminism and the complexity of the V-C dimension
Papadimitriou, C. H., & Yannakakis, M. (2002) · IEEE Conference on Computational Complexity (CCC) · doi:10.1109/sct.1993.336545 · Cited by 42
Valiant, L. G. (2026) · Foundations of Computation and Machine Learning · doi:10.1145/3749740.3749746
Cited by
Invitation to Fixed-Parameter Algorithms
Niedermeier, R. (2006) · doi:10.1093/acprof:oso/9780198566076.001.0001 · Cited by 1,668
The Web as a Graph: Measurements, Models, and Methods
Kleinberg, J. M., Kumar, R., Raghavan, P., Rajagopalan, S., & Tomkins, A. S. (1999) · Lecture Notes in Computer Science · doi:10.1007/3-540-48686-0_1 · Cited by 1,016
Fixed-Parameter Tractability and Completeness I: Basic Results
Downey, R. G., & Fellows, M. R. (1995) · SIAM Journal on Computing · doi:10.1137/s0097539792228228 · Cited by 468
Self-citationFixed Parameter Algorithms for DOMINATING SET and Related Problems on Planar Graphs
Alber, J., Bodlaender, H. L., Fernau, H., Kloks, T., & Niedermeier, R. (2002) · Algorithmica · doi:10.1007/s00453-001-0116-5 · Cited by 304
Metadata
- Authors
- Downey, R. G., & Fellows, M. R.
- Venue
- Feasible Mathematics II
- Publisher
- Birkhäuser Boston
- Published
- 1995
- Pages
- 219-244
- OpenAlex
- W1598441350
- Cited by
- 164
- References
- 23
- FWCI
- 15.03
- Type
- book chapter
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.