On the public citation graph

Linear FPT reductions and computational lower bounds

https://doi.org/10.1145/1007352.1007391
0 signed · 116 inferred · view as graph

Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.

Is this your work? Sign in with ORCID and put your name on the claims that are yours.
Claim with ORCID
Reference health. See whether every reference in this work resolves to a known work and none has been retracted — and get a dated CiteStamped badge you can embed.
See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1006/jagm.2001.1186openalex-snapshot
Vertex Cover: Further Observations and Further Improvements
inferredcites →https://doi.org/10.1006/jcss.1996.0058openalex-snapshot
On Limited Nondeterminism and the Complexity of the V-C Dimension
inferredcites →https://doi.org/10.1006/jcss.1997.1490openalex-snapshot
On Fixed-Parameter Tractability and Approximability of NP Optimization Problems
inferredcites →https://doi.org/10.1006/jcss.1999.1626openalex-snapshot
On the Complexity of Database Queries
inferredcites →https://doi.org/10.1006/jcss.2001.1774openalex-snapshot
Which Problems Have Strongly Exponential Complexity?
inferredcites →https://doi.org/10.1007/3-540-45465-9_63openalex-snapshot
A PTAS for Distinguishing (Sub)string Selection
inferredcites →https://doi.org/10.1007/978-3-540-45077-1_19openalex-snapshot
On Exact and Approximation Algorithms for Distinguishing Substring Selection
inferredcites →https://doi.org/10.1007/s00453-001-0116-5openalex-snapshot
Fixed Parameter Algorithms for DOMINATING SET and Related Problems on Planar Graphs
inferredcites →https://doi.org/10.1016/0020-0190(91)90003-zopenalex-snapshot
Characterizing parallel hierarchies by reducibilities
inferredcites →https://doi.org/10.1016/0022-0000(91)90023-xopenalex-snapshot
Optimization, approximation, and complexity classes
inferredcites →https://doi.org/10.1016/0168-0072(94)00034-zopenalex-snapshot
Fixed-parameter tractability and completeness IV: On completeness for W[P] and PSPACE analogues
inferredcites →https://doi.org/10.1016/0196-6774(86)90032-5openalex-snapshot
Algorithms for maximum independent sets
inferredcites →https://doi.org/10.1016/s0022-0000(03)00074-6openalex-snapshot
On the existence of subexponential parameterized algorithms
inferredcites →https://doi.org/10.1016/s0022-0000(03)00075-8openalex-snapshot
Solving large FPT problems on coarse-grained parallel machines
inferredcites →https://doi.org/10.1016/s0747-7171(08)80013-2openalex-snapshot
Matrix multiplication via arithmetic progressions
inferredcites →https://doi.org/10.1016/s0898-1221(00)90183-4openalex-snapshot
Complexity and approximation: Combinatorial optimization problems and their approximability properties
inferredcites →https://doi.org/10.1016/s1571-0661(04)00301-9openalex-snapshot
Parameterized Complexity
inferredcites →https://doi.org/10.1109/ccc.2004.37openalex-snapshot
Tight lower bounds for certain parameterized NP-hard problems
inferredcites →https://doi.org/10.1109/tc.1986.1676847openalex-snapshot
An O(20.304n) Algorithm for Solving Maximum Independent Set Problem
inferredcites →https://doi.org/10.1137/0206038openalex-snapshot
Finding a Maximum Independent Set
inferredcites →https://doi.org/10.1137/s0097539701397825openalex-snapshot
Genetic Design of Drugs Without Side-Effects
inferredcites →https://doi.org/10.4086/cjtcsopenalex-snapshot
Chicago Journal of Theoretical Computer Science

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.1007/11496199_43openalex-snapshot
On Product Covering in Supply Chain Models: Natural Complete Problems for W[3] and W[4]
inferred← citeshttps://doi.org/10.1007/11533719_98openalex-snapshot
W-Hardness Under Linear FPT-Reductions: Structural Properties and Further Applications
inferred← citeshttps://doi.org/10.1007/11780441_16openalex-snapshot
Solving the Maximum Agreement SubTree and the Maximum Compatible Tree Problems on Many Bounded Degree Trees
inferred← citeshttps://doi.org/10.1007/11809678_16openalex-snapshot
Lower Bounds and Parameterized Approach for Longest Common Subsequence
inferred← citeshttps://doi.org/10.1007/978-0-387-34735-6_24openalex-snapshot
On PTAS for Planar Graph Problems
inferred← citeshttps://doi.org/10.1007/978-1-4419-7997-1_19openalex-snapshot
Complexity Issues on PTAS
inferred← citeshttps://doi.org/10.1007/978-1-4471-5298-9_9openalex-snapshot
A Retrospective on Genomic Preprocessing for Comparative Genomics
inferred← citeshttps://doi.org/10.1007/978-1-4614-1168-0_13openalex-snapshot
Multivariate Complexity Theory
inferred← citeshttps://doi.org/10.1007/978-3-030-39881-1_27openalex-snapshot
Parameterized Algorithms for the Happy Set Problem
inferred← citeshttps://doi.org/10.1007/978-3-319-66700-3_25openalex-snapshot
Stable Marriage with Covering Constraints–A Complete Computational Trichotomy
inferred← citeshttps://doi.org/10.1007/978-3-540-28639-4_10openalex-snapshot
On Miniaturized Problems in Parameterized Complexity Theory
inferred← citeshttps://doi.org/10.1007/978-3-540-30219-3_37openalex-snapshot
Integrating Sample-Driven and Pattern-Driven Approaches in Motif Finding
inferred← citeshttps://doi.org/10.1007/978-3-540-73437-6_14openalex-snapshot
Non-breaking Similarity of Genomes with Gene Repetitions
inferred← citeshttps://doi.org/10.1007/978-3-540-73556-4_31openalex-snapshot
A Lower Bound on Approximation Algorithms for the Closest Substring Problem
inferred← citeshttps://doi.org/10.1007/978-3-540-74126-8_14openalex-snapshot
A Graph Clustering Approach to Weak Motif Recognition
inferred← citeshttps://doi.org/10.1007/978-3-540-85097-7_30openalex-snapshot
On Recovering Syntenic Blocks from Comparative Maps
inferred← citeshttps://doi.org/10.1007/978-3-642-02017-9_10openalex-snapshot
Approximability and Fixed-Parameter Tractability for the Exemplar Genomic Distance Problems
inferred← citeshttps://doi.org/10.1007/978-3-642-02017-9_20openalex-snapshot
On Parameterized Exponential Time Complexity
inferred← citeshttps://doi.org/10.1007/978-3-642-11269-0_14openalex-snapshot
An Exponential Time 2-Approximation Algorithm for Bandwidth
inferred← citeshttps://doi.org/10.1007/978-3-642-14444-8_1openalex-snapshot
Universality, Tolerance, Chaos and Order
inferred← citeshttps://doi.org/10.1007/978-3-642-28050-4_14openalex-snapshot
Safe Approximation and Its Relation to Kernelization
inferred← citeshttps://doi.org/10.1007/978-3-642-28050-4_19openalex-snapshot
Parameterized Maximum Path Coloring
inferred← citeshttps://doi.org/10.1007/978-3-642-30891-8_20openalex-snapshot
What’s Next? Future Directions in Parameterized Complexity
inferred← citeshttps://doi.org/10.1007/978-3-642-33293-7_4openalex-snapshot
The Exponential Time Hypothesis and the Parameterized Clique Problem
inferred← citeshttps://doi.org/10.1007/978-3-642-40627-0_32openalex-snapshot
Blowing Holes in Various Aspects of Computational Problems, with Applications to Constraint Satisfaction
inferred← citeshttps://doi.org/10.1007/s00453-011-9554-xopenalex-snapshot
Algorithmic Meta-theorems for Restrictions of Treewidth
inferred← citeshttps://doi.org/10.1007/s00453-019-00636-yopenalex-snapshot
Stable Matchings with Covering Constraints: A Complete Computational Trichotomy
inferred← citeshttps://doi.org/10.1007/s10458-025-09711-xopenalex-snapshot
Hedonic seat arrangement problems
inferred← citeshttps://doi.org/10.1007/s10878-006-7137-6openalex-snapshot
On the computational hardness based on linear FPT-reductions
inferred← citeshttps://doi.org/10.1007/s10878-008-9141-5openalex-snapshot
Parameterized dominating set problem in chordal graphs: complexity and lower bound
inferred← citeshttps://doi.org/10.1007/s10878-009-9233-xopenalex-snapshot
On recovering syntenic blocks from comparative maps
inferred← citeshttps://doi.org/10.1007/s10878-010-9317-7openalex-snapshot
Parameterized complexity and inapproximability of dominating set problem in chordal and near chordal graphs
inferred← citeshttps://doi.org/10.1007/s11390-005-0003-7openalex-snapshot
Parameterized Computation and Complexity: A New Approach Dealing with NP-Hardness
inferred← citeshttps://doi.org/10.1016/j.comgeo.2011.06.005openalex-snapshot
Fixed-parameter tractability and lower bounds for stabbing problems
inferred← citeshttps://doi.org/10.1016/j.dam.2021.07.005openalex-snapshot
Parameterized algorithms for the Happy Set problem
inferred← citeshttps://doi.org/10.1016/j.ic.2019.03.008openalex-snapshot
Some lower bounds in parameterized AC0
inferred← citeshttps://doi.org/10.1016/j.ipl.2008.10.014openalex-snapshot
Efficient algorithms for clique problems
inferred← citeshttps://doi.org/10.1016/j.ipl.2010.05.031openalex-snapshot
There is no EPTAS for two-dimensional knapsack
inferred← citeshttps://doi.org/10.1016/j.ipl.2014.10.014openalex-snapshot
On finding the longest antisymmetric path in directed acyclic graphs
inferred← citeshttps://doi.org/10.1016/j.jcss.2006.04.007openalex-snapshot
Strong computational lower bounds via parameterized complexity
inferred← citeshttps://doi.org/10.1016/j.jcss.2006.11.001openalex-snapshot
Genus characterizes the complexity of certain graph problems: Some tight results
inferred← citeshttps://doi.org/10.1016/j.jcss.2009.04.001openalex-snapshot
On problems without polynomial kernels
inferred← citeshttps://doi.org/10.1016/j.tcs.2005.10.003openalex-snapshot
On miniaturized problems in parameterized complexity theory
inferred← citeshttps://doi.org/10.1016/j.tcs.2006.07.016openalex-snapshot
On product covering in 3-tier supply chain models: Natural complete problems for W[3] and W[4]
inferred← citeshttps://doi.org/10.1016/j.tcs.2009.03.006openalex-snapshot
On parameterized exponential time complexity
inferred← citeshttps://doi.org/10.1016/j.tcs.2013.01.012openalex-snapshot
Parameterized maximum path coloring
inferred← citeshttps://doi.org/10.1016/j.tcs.2013.03.024openalex-snapshot
An exponential time 2-approximation algorithm for bandwidth
inferred← citeshttps://doi.org/10.1016/j.tcs.2014.07.011openalex-snapshot
On the approximability of the exemplar adjacency number problem for genomes with gene repetitions
inferred← citeshttps://doi.org/10.1016/j.tcs.2015.03.009openalex-snapshot
Constructing NP-intermediate problems by blowing holes with parameters of various properties
inferred← citeshttps://doi.org/10.1080/00207160.2014.976210openalex-snapshot
On the independent set problem in random graphs
inferred← citeshttps://doi.org/10.1093/comjnl/bxm035openalex-snapshot
Parameterized Complexity and Biopolymer Sequence Comparison
inferred← citeshttps://doi.org/10.1093/comjnl/bxm048openalex-snapshot
Parameterized Complexity and Approximation Algorithms
inferred← citeshttps://doi.org/10.1109/ccc.2006.8openalex-snapshot
An Isomorphism between Subexponential and Parameterized Complexity Theory
inferred← citeshttps://doi.org/10.1109/focs.2006.56openalex-snapshot
On the Optimality of the Dimensionality Reduction Method
inferred← citeshttps://doi.org/10.1109/focs.2007.26openalex-snapshot
On the Optimality of Planar and Geometric Approximation Schemes
inferred← citeshttps://doi.org/10.1109/focs.2007.50openalex-snapshot
Space-Efficient Identity Based EncryptionWithout Pairings
inferred← citeshttps://doi.org/10.1109/focs.2016.61openalex-snapshot
The Constant Inapproximability of the Parameterized Dominating Set Problem
inferred← citeshttps://doi.org/10.1109/focs.2017.74openalex-snapshot
From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More
inferred← citeshttps://doi.org/10.1109/focs57990.2023.00008openalex-snapshot
Clique Is Hard on Average for Unary Sherali-Adams
inferred← citeshttps://doi.org/10.1109/imsccs.2006.84openalex-snapshot
Maximum Common Subgraph: Upper Bound and Lower Bound Results
inferred← citeshttps://doi.org/10.1109/imsccs.2007.50openalex-snapshot
Parameterized Graph Problems in Computational Biology
inferred← citeshttps://doi.org/10.1109/imsccs.2007.69openalex-snapshot
A mobile ad hoc network with mobile satellite earth-stations
inferred← citeshttps://doi.org/10.1109/imsccs.2008.26openalex-snapshot
Addressing Bio-sequence and Bio-structure Problems
inferred← citeshttps://doi.org/10.1109/sfcs.2005.70openalex-snapshot
The Closest Substring problem with small distances
inferred← citeshttps://doi.org/10.1137/100812653openalex-snapshot
Sparse Balanced Partitions and the Complexity of Subgraph Problems
inferred← citeshttps://doi.org/10.1145/2000807.2000811openalex-snapshot
Geometric clustering
inferred← citeshttps://doi.org/10.1145/2582112.2582124openalex-snapshot
The limited blessing of low dimensionality
inferred← citeshttps://doi.org/10.1145/2733376openalex-snapshot
On the Variable Hierarchy of First-Order Spectra
inferred← citeshttps://doi.org/10.1145/3038912.3052636openalex-snapshot
A Fast and Provable Method for Estimating Clique Counts Using Turán's Theorem
inferred← citeshttps://doi.org/10.1145/3188745.3188856openalex-snapshot
Clique is hard on average for regular resolution
inferred← citeshttps://doi.org/10.1145/3212622openalex-snapshot
The Parameterized Complexity of the k -Biclique Problem
inferred← citeshttps://doi.org/10.1145/3336191.3371839openalex-snapshot
The Power of Pivoting for Exact Clique Counting
inferred← citeshttps://doi.org/10.1145/3449352openalex-snapshot
Clique Is Hard on Average for Regular Resolution
inferred← citeshttps://doi.org/10.1145/3452021.3458814openalex-snapshot
Modern Lower Bound Techniques in Database Theory and Constraint Satisfaction
inferred← citeshttps://doi.org/10.1145/3591251openalex-snapshot
Optimal Reads-From Consistency Checking for C11-Style Memory Models
inferred← citeshttps://doi.org/10.1186/1471-2105-7-s4-s6openalex-snapshot
Maximum common subgraph: some upper bound and lower bound results
inferred← citeshttps://doi.org/10.14257/ijast.2014.67.07openalex-snapshot
AVSA, Modified Vertex Support Algorithm for Approximation of MVC
inferred← citeshttps://doi.org/10.14257/ijunesst.2014.7.6.07openalex-snapshot
Experimental Comparison of Five Approximation Algorithms for Minimum Vertex Cover
inferred← citeshttps://doi.org/10.1515/gmj-2021-2090openalex-snapshot
On the induced matching problem in hamiltonian bipartite graphs
inferred← citeshttps://doi.org/10.22028/d291-26018openalex-snapshot
Kernelization of generic problems : upper and lower bounds
inferred← citeshttps://doi.org/10.3390/a10010024openalex-snapshot
Problems on Finite Automata and the Exponential Time Hypothesis
inferred← citeshttps://doi.org/10.3390/a13060146openalex-snapshot
A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms
inferred← citeshttps://doi.org/10.4086/toc.2010.v006a005openalex-snapshot
inferred← citeshttps://doi.org/10.4230/lipics.icalp.2022.90openalex-snapshot
On Lower Bounds of Approximating Parameterized $k$-Clique
inferred← citeshttps://doi.org/10.48550/arxiv.1206.2436openalex-snapshot
A Proof Checking View of Parameterized Complexity
inferred← citeshttps://doi.org/10.48550/arxiv.1406.3700openalex-snapshot
The Parameterized Complexity of k-Biclique
inferred← citeshttps://doi.org/10.48550/arxiv.1511.00075openalex-snapshot
The Constant Inapproximability of the Parameterized Dominating Set Problem
inferred← citeshttps://doi.org/10.48550/arxiv.1602.08230openalex-snapshot
Stable Marriage with Covering Constraints: A Complete Computational Trichotomy
inferred← citeshttps://doi.org/10.48550/arxiv.1606.08014openalex-snapshot
Some lower bounds in parameterized ${\rm AC}^0$
inferred← citeshttps://doi.org/10.48550/arxiv.1612.01171openalex-snapshot
The limited blessing of low dimensionality: when $1-1/d$ is the best possible exponent for $d$-dimensional geometric problems
inferred← citeshttps://doi.org/10.48550/arxiv.2107.06261openalex-snapshot
Tight running times for minimum $\ell_q$-norm load balancing: beyond exponential dependencies on $1/ε$
inferred← citeshttps://doi.org/10.5277/ord150401openalex-snapshot
A new and fast approximation algorithm for vertex cover using a maximum independent set (VCUMI)
inferred← citeshttps://doi.org/10.5555/1109557.1109558openalex-snapshot
Confronting hardness using a hybrid approach
inferred← citeshttps://doi.org/10.5555/1283383.1283415openalex-snapshot
Improved algorithms for path, matching, and packing problems
Editorial review for independent work. ICSAC — the Institute for Complexity Science and Advanced Computing — runs a structured editorial panel for researchers publishing outside journals, and publishes on CiteStamp rails. Submission is free and goes through ORCID: icsacinstitute.org/submit.