On the public citation graph
Known Algorithms on Graphs of Bounded Treewidth Are Probably Optimal
0 signed · 102 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.
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.
What this work says
Outgoing claims: the papers this work cites, builds on, or argues with.
inferredcites →https://doi.org/10.1006/jcss.2001.1774openalex-snapshot
Which Problems Have Strongly Exponential Complexity?
inferredcites →https://doi.org/10.1007/3-540-45995-2_52openalex-snapshot
Improved Tree Decomposition Based Algorithms for Domination-like Problems
inferredcites →https://doi.org/10.1007/3-540-57155-8_284openalex-snapshot
Practical algorithms on partial k-trees with an application to domination-like problems
inferredcites →https://doi.org/10.1007/978-3-319-57586-5_29openalex-snapshot
Fine-Grained Parameterized Complexity Analysis of Graph Coloring Problems
inferredcites →https://doi.org/10.1007/978-3-642-04128-0_51openalex-snapshot
Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
inferredcites →https://doi.org/10.1007/978-3-642-11269-0_6openalex-snapshot
The Complexity of Satisfiability of Small Depth Circuits
inferredcites →https://doi.org/10.1007/978-3-642-39206-1_17openalex-snapshot
Deterministic Single Exponential Time Algorithms for Connectivity Problems Parameterized by Treewidth
inferredcites →https://doi.org/10.1007/978-3-662-43948-7_64openalex-snapshot
Parameterized Approximation Schemes Using Graph Widths
inferredcites →https://doi.org/10.1007/s00224-007-9089-3openalex-snapshot
Enumerate and Expand: Improved Algorithms for Connected Vertex Cover and Tree Cover
inferredcites →https://doi.org/10.1007/s00453-007-9133-3openalex-snapshot
On Two Techniques of Combining Branching and Treewidth
inferredcites →https://doi.org/10.1007/s00453-013-9759-2openalex-snapshot
Inclusion/Exclusion Meets Measure and Conquer
inferredcites →https://doi.org/10.1007/s004530010020openalex-snapshot
Diameter and Treewidth in Minor-Closed Graph Families
inferredcites →https://doi.org/10.1007/s10878-006-7137-6openalex-snapshot
On the computational hardness based on linear FPT-reductions
inferredcites →https://doi.org/10.1016/0304-3975(94)00160-kopenalex-snapshot
Mixed searching and proper-path-width
inferredcites →https://doi.org/10.1016/j.dam.2007.08.013openalex-snapshot
Planar graph bipartization in linear time
inferredcites →https://doi.org/10.1016/j.disopt.2007.08.001openalex-snapshot
Linear-programming design and analysis of fast algorithms for Max 2-CSP
inferredcites →https://doi.org/10.1016/j.ic.2014.12.008openalex-snapshot
Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
inferredcites →https://doi.org/10.1016/j.jalgor.2004.12.001openalex-snapshot
Cutwidth I: A linear time fixed parameter algorithm
inferredcites →https://doi.org/10.1016/j.jcss.2006.04.007openalex-snapshot
Strong computational lower bounds via parameterized complexity
inferredcites →https://doi.org/10.1016/j.jctb.2016.10.001openalex-snapshot
Irrelevant vertices for the planar Disjoint Paths Problem
inferredcites →https://doi.org/10.1093/acprof:oso/9780198566076.003.0013openalex-snapshot
PARAMETERIZED COMPLEXITY THEORY
inferredcites →https://doi.org/10.1093/comjnl/bxm033openalex-snapshot
The Bidimensionality Theory and Its Algorithmic Applications
inferredcites →https://doi.org/10.1109/focs.2007.50openalex-snapshot
Space-Efficient Identity Based EncryptionWithout Pairings
inferredcites →https://doi.org/10.1109/focs.2011.23openalex-snapshot
Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
inferredcites →https://doi.org/10.1109/focs.2014.53openalex-snapshot
Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems
inferredcites →https://doi.org/10.1109/focs.2015.14openalex-snapshot
Tight Hardness Results for LCS and Other Sequence Similarity Measures
inferredcites →https://doi.org/10.1137/1.9781611973402.10openalex-snapshot
Efficient Computation of Representative Sets with Applications in Parameterized and Exact Algorithms
inferredcites →https://doi.org/10.1137/130910932openalex-snapshot
Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width
inferredcites →https://doi.org/10.1137/130947076openalex-snapshot
Known Algorithms for Edge Clique Cover are Probably Optimal
inferredcites →https://doi.org/10.1145/1101821.1101823openalex-snapshot
Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
inferredcites →https://doi.org/10.1145/1250790.1250801openalex-snapshot
Fourier meets möbius: fast subset convolution
inferredcites →https://doi.org/10.1145/2027216.2027219openalex-snapshot
Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth
inferredcites →https://doi.org/10.1145/2488608.2488646openalex-snapshot
Fast hamiltonicity checking via bases of perfect matchings
inferredcites →https://doi.org/10.1145/2488608.2488673openalex-snapshot
Fast approximation algorithms for the diameter and radius of sparse graphs
inferredcites →https://doi.org/10.1145/2746539.2746594openalex-snapshot
Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
inferredcites →https://doi.org/10.1145/2746539.2746612openalex-snapshot
Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
inferredcites →https://doi.org/10.1145/2886094openalex-snapshot
Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms
inferredcites →https://doi.org/10.4230/lipics.icalp.2016.28openalex-snapshot
Double-Exponential and Triple-Exponential Bounds for Choosability Problems Parameterized by Treewidth
inferredcites →https://doi.org/10.4230/lipics.ipec.2015.17openalex-snapshot
Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
inferredcites →https://doi.org/10.4230/lipics.ipec.2016.8openalex-snapshot
Optimal Dynamic Program for r-Domination Problems over Tree Decompositions
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.2139/ssrn.4673490openalex-extracted
Parameterized Problems Complete for Nondeterministic Fpt Time and Logarithmic Space
inferred← citeshttps://doi.org/10.1007/978-3-030-24766-9_13openalex-snapshot
Parameterized Complexity of Conflict-Free Graph Coloring
inferred← citeshttps://doi.org/10.1007/978-3-030-59901-0_3openalex-snapshot
An Optimal Algorithm for Bisection for Bounded-Treewidth Graph
inferred← citeshttps://doi.org/10.1007/978-3-030-60440-0_6openalex-snapshot
On the Complexity of Finding Large Odd Induced Subgraphs and Odd Colorings
inferred← citeshttps://doi.org/10.1007/978-3-030-75242-2_14openalex-snapshot
Upper Dominating Set: Tight Algorithms for Pathwidth and Sub-exponential Approximation
inferred← citeshttps://doi.org/10.1007/978-3-031-21534-6_6openalex-snapshot
Recent Advances in Practical Data Reduction
inferred← citeshttps://doi.org/10.1007/978-3-031-23101-8_3openalex-snapshot
Solving Cut-Problems in Quadratic Time for Graphs with Bounded Treewidth
inferred← citeshttps://doi.org/10.1007/978-3-031-43380-1_28openalex-snapshot
Tight Algorithms for Connectivity Problems Parameterized by Modular-Treewidth
inferred← citeshttps://doi.org/10.1007/978-3-031-55601-2_10openalex-snapshot
Induced Tree Covering and the Generalized Yutsis Property
inferred← citeshttps://doi.org/10.1007/978-3-031-63021-7_40openalex-snapshot
Parameterized Complexity of Paired Domination
inferred← citeshttps://doi.org/10.1007/978-3-032-11835-6_8openalex-snapshot
Concurrency Constrained Scheduling with Tree-Like Constraints
inferred← citeshttps://doi.org/10.1007/978-3-032-27732-9_13openalex-snapshot
Dominating Set with Quotas: Balancing Coverage and Constraints
inferred← citeshttps://doi.org/10.1007/s00224-022-10103-xopenalex-snapshot
Digraph Coloring and Distance to Acyclicity
inferred← citeshttps://doi.org/10.1007/s00453-021-00830-xopenalex-snapshot
On the Complexity of Finding Large Odd Induced Subgraphs and Odd Colorings
inferred← citeshttps://doi.org/10.1007/s00453-024-01265-wopenalex-snapshot
Anti-factor is FPT Parameterized by Treewidth and List Size (but Counting is Hard)
inferred← citeshttps://doi.org/10.1007/s00453-024-01274-9openalex-snapshot
XNLP-Completeness for Parameterized Problems on Graphs with a Linear Structure
inferred← citeshttps://doi.org/10.1007/s00453-025-01293-0openalex-snapshot
Tight Bounds for Chordal/Interval Vertex Deletion Parameterized by Treewidth
inferred← citeshttps://doi.org/10.1016/j.cosrev.2026.100919openalex-snapshot
An invitation to “Fine-grained complexity of NP-complete problems”
inferred← citeshttps://doi.org/10.1016/j.dam.2020.03.052openalex-snapshot
Structurally parameterized d -scattered set
inferred← citeshttps://doi.org/10.1016/j.dam.2021.12.026openalex-snapshot
Structural parameterization for minimum conflict-free colouring
inferred← citeshttps://doi.org/10.1016/j.ic.2024.105195openalex-snapshot
Parameterized problems complete for nondeterministic FPT time and logarithmic space
inferred← citeshttps://doi.org/10.1016/j.ipl.2021.106168openalex-snapshot
List k-colouring P-free graphs: A Mim-width perspective
inferred← citeshttps://doi.org/10.1016/j.jcss.2025.103636openalex-snapshot
Induced tree covering and the generalized Yutsis property
inferred← citeshttps://doi.org/10.1016/j.tcs.2019.08.006openalex-snapshot
Computing the chromatic number using graph decompositions via matrix rank
inferred← citeshttps://doi.org/10.1016/j.tcs.2021.04.023openalex-snapshot
A (probably) optimal algorithm for Bisection on bounded-treewidth graphs
inferred← citeshttps://doi.org/10.1016/j.tcs.2022.05.013openalex-snapshot
Upper Dominating Set: Tight algorithms for pathwidth and sub-exponential approximation
inferred← citeshttps://doi.org/10.1016/j.tcs.2026.116201openalex-snapshot
Fair Short Paths in Vertex-Colored Graphs
inferred← citeshttps://doi.org/10.1016/j.tcs.2026.116249openalex-snapshot
Parameterized algorithms for variations of vertex-edge domination in graphs
inferred← citeshttps://doi.org/10.1137/1.9781611975031.70openalex-snapshot
A Tight Lower Bound for Counting Hamiltonian Cycles via Matrix Rank
inferred← citeshttps://doi.org/10.1137/1.9781611975994.97openalex-snapshot
Fine-grained complexity of graph homomorphism problem for bounded-treewidth graphs
inferred← citeshttps://doi.org/10.1137/1.9781611976465.14openalex-snapshot
FPT-approximation for FPT Problems
inferred← citeshttps://doi.org/10.1137/1.9781611977073.22openalex-snapshot
Counting list homomorphisms from graphs of bounded treewidth: tight complexity bounds
inferred← citeshttps://doi.org/10.1137/1.9781611977554.ch124openalex-snapshot
Polynomial formulations as a barrier for reduction-based hardness proofs
inferred← citeshttps://doi.org/10.1137/19m1280326openalex-snapshot
Finer Tight Bounds for Coloring on Clique-Width
inferred← citeshttps://doi.org/10.1137/20m1385779openalex-snapshot
Grundy Distinguishes Treewidth from Pathwidth
inferred← citeshttps://doi.org/10.1145/3293465openalex-snapshot
On Problems Equivalent to (min,+)-Convolution
inferred← citeshttps://doi.org/10.1145/3368631openalex-snapshot
Finding Hamiltonian Cycle in Graphs of Bounded Treewidth
inferred← citeshttps://doi.org/10.1145/3406325.3451068openalex-snapshot
Vertex deletion parameterized by elimination distance and even less
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/3519935.3520032openalex-snapshot
Hardness for triangle problems under even more believable hypotheses: reductions from real APSP, real 3SUM, and OV
inferred← citeshttps://doi.org/10.1145/3640814openalex-snapshot
Counting List Homomorphisms from Graphs of Bounded Treewidth: Tight Complexity Bounds
inferred← citeshttps://doi.org/10.1145/3665156openalex-snapshot
Structural Parameterizations for Two Bounded Degree Problems Revisited
inferred← citeshttps://doi.org/10.1145/3708509openalex-snapshot
Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part II: Hardness Results
inferred← citeshttps://doi.org/10.1145/3721134openalex-snapshot
Polynomial Formulations as a Barrier for Reduction-Based Hardness Proofs
inferred← citeshttps://doi.org/10.1145/3731452openalex-snapshot
Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs—Part I: Algorithmic Results
inferred← citeshttps://doi.org/10.1145/3798129.3800747openalex-snapshot
Path Cover, Hamiltonicity, and Independence Number: An FPT Perspective
inferred← citeshttps://doi.org/10.1145/3798129.3800927openalex-snapshot
Fine-Grained Bounds for Courcelle’s Theorem
inferred← citeshttps://doi.org/10.3390/math11153325openalex-snapshot
Clique Transversal Variants on Graphs: A Parameterized-Complexity Perspective
inferred← citeshttps://doi.org/10.3390/sym14040676openalex-snapshot
Remarks on Parameterized Complexity of Variations of the Maximum-Clique Transversal Problem on Graphs
inferred← citeshttps://doi.org/10.4230/lipics.ipec.2021.21openalex-snapshot
Close Relatives (Of Feedback Vertex Set), Revisited
inferred← citeshttps://doi.org/10.4230/lipics.ipec.2022.17openalex-snapshot
Towards Exact Structural Thresholds for Parameterized Complexity
inferred← citeshttps://doi.org/10.4230/lipics.stacs.2020.29openalex-snapshot
Solving Connectivity Problems Parameterized by Treedepth in Single-Exponential Time and Polynomial Space
inferred← citeshttps://doi.org/10.4230/lipics.stacs.2021.56openalex-snapshot
Fine-Grained Complexity of the List Homomorphism Problem: Feedback Vertex Set and Cutwidth
inferred← citeshttps://doi.org/10.4230/lipics.stacs.2022.36openalex-snapshot
Tight Bounds for Counting Colorings and Connected Edge Sets Parameterized by Cutwidth
inferred← citeshttps://doi.org/10.46298/dmtcs.6824openalex-snapshot
New Algorithms for Mixed Dominating Set
inferred← citeshttps://doi.org/10.48550/arxiv.1803.00927openalex-snapshot
Finding Hamiltonian Cycle in Graphs of Bounded Treewidth: Experimental Evaluation
inferred← citeshttps://doi.org/10.70675/80f73784z475az47adzb2ccz764d88c268e2openalex-snapshot
Contributions to approximation and parameterization in combinatorial optimization
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.