Which problems have strongly exponential complexity?

From MaRDI portal

Publication:1604206

Jump to:navigation, search

DOI10.1006/jcss.2001.1774zbMath1006.68052OpenAlexW1995725694WikidataQ55891730 ScholiaQ55891730MaRDI QIDQ1604206

Russell Impagliazzo, Ramamohan Paturi, Francis Zane

Publication date: 4 July 2002

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcss.2001.1774

zbMATH Keywords

NP-complete problems sub-exponential reduction family

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

On miniaturized problems in parameterized complexity theory, Separating OR, SUM, and XOR circuits, Efficiently approximating color-spanning balls, A substring-substring LCS data structure, On the copy complexity of width 3 Horn constraint systems, Structural parameterizations of clique coloring, (Total) vector domination for graphs with bounded branchwidth, The complexity of finding arc-disjoint branching flows, On residual approximation in solution extension problems, On the optimality of exact and approximation algorithms for scheduling problems, Scaffolding problems revisited: complexity, approximation and fixed parameter tractable algorithms, and some special cases, The relative exponential time complexity of approximate counting satisfying assignments, The complexity of depth-3 circuits computing symmetric Boolean functions, On the parameterised complexity of string morphism problems, Constraint satisfaction with bounded treewidth revisited, Block interpolation: a framework for tight exponential-time counting complexity, Computational complexity of distance edge labeling, Strong computational lower bounds via parameterized complexity, Polynomial kernels for weighted problems, Strong partial clones and the time complexity of SAT problems, Courcelle's theorem for triangulations, Problems on finite automata and the exponential time hypothesis, A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion, The parameterized complexity of local search for TSP, more refined, Covering problems for partial words and for indeterminate strings, Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs, Time-approximation trade-offs for inapproximable problems, Multivariate complexity analysis of geometric \textsc{Red Blue Set Cover}, Tight complexity bounds for FPT subgraph problems parameterized by the clique-width, Incremental list coloring of graphs, parameterized by conservation, Beyond bidimensionality: parameterized subexponential algorithms on directed graphs, Parameterized complexity of MaxSat above average, On exact algorithms for the permutation CSP, Lower bounds on the complexity of \(\mathsf{MSO}_1\) model-checking, Exponential approximation schemata for some network design problems, Interval scheduling and colorful independent sets, Towards NP-P via proof complexity and search, Parameterized and subexponential-time complexity of satisfiability problems and applications, On the hardness of labeled correlation clustering problem: a parameterized complexity view, Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms, Exact algorithms for dominating set, On the (adjacency) metric dimension of corona and strong product graphs and their local variants: combinatorial and computational results, Algorithms solving the matching cut problem, On making directed graphs transitive, Tight lower bounds for the workflow satisfiability problem based on the strong exponential time hypothesis, Fixing improper colorings of graphs, Sparsification and subexponential approximation, A note on hardness of diameter approximation, Catalan structures and dynamic programming in \(H\)-minor-free graphs, New plain-exponential time classes for graph homomorphism, Complexity and lowers bounds for power edge set problem, Parameterized proof complexity, The parameterized complexity of \(k\)-flip local search for SAT and MAX SAT, Subexponential parameterized algorithms, Exact algorithms for finding well-connected 2-clubs in sparse real-world graphs: theory and experiments, Colouring graphs when the number of colours is almost the maximum degree, A new algorithm for finding trees with many leaves, Searching the \(k\)-change neighborhood for TSP is W[1-hard], Confronting intractability via parameters, Subexponential-time algorithms for maximum independent set in \(P_t\)-free and broom-free graphs, Fine-grained dichotomies for the Tutte plane and Boolean \#CSP, Practical algorithms for MSO model-checking on tree-decomposable graphs, Approximating MAX SAT by moderately exponential and parameterized algorithms, Fixed-parameter approximations for \(k\)-center problems in low highway dimension graphs, Efficient algorithms for the \textsc{max~\(k\)-vertex cover problem}, Multivariate algorithmics for finding cohesive subnetworks, A fast and simple subexponential fixed parameter algorithm for one-sided crossing minimization, On finding optimal polytrees, Refining complexity analyses in planning by exploiting the exponential time hypothesis, Fixed-parameter algorithms for DAG partitioning, On optimal approximability results for computing the strong metric dimension, An initial study of time complexity in infinite-domain constraint satisfaction, Dealing with 4-variables by resolution: an improved MaxSAT algorithm, Solving connected dominating set faster than \(2^n\), On the parameterized complexity of reconfiguration problems, An improved semidefinite programming hierarchy for testing entanglement, An improved lower bound on approximation algorithms for the closest substring problem, Tractable structures for constraint satisfaction with truth tables, Lower bounds for kernelizations and other preprocessing procedures, Improved upper bounds for vertex cover, Cluster editing with locally bounded modifications, Computing vertex-surjective homomorphisms to partially reflexive trees, A note on width-parameterized SAT: an exact machine-model characterization, Bounded-depth succinct encodings and the structure they imply on graphs, The ordered covering problem, Linear kernels and linear-time algorithms for finding large cuts, Complexity of token swapping and its variants, Structural parameterizations of undirected feedback vertex set: FPT algorithms and kernelization, Approximating vector scheduling: almost matching upper and lower bounds, On the computational complexity of vertex integrity and component order connectivity, The complexity ecology of parameters: An illustration using bounded max leaf number, Into the square: on the complexity of some quadratic-time solvable problems, Approximating the maximum clique minor and some subgraph homeomorphism problems, On parameterized exponential time complexity, Pathwidth of cubic graphs and exact algorithms, On the \textsc{Distance Identifying Set} meta-problem and applications to the complexity of identifying problems on graphs, Multivariate analysis of orthogonal range searching and graph distances, Dual parameterization of weighted coloring, 3SUM, 3XOR, triangles, Algorithms and almost tight results for 3-colorability of small diameter graphs, Improved Lower Bounds for Graph Embedding Problems, Fine-Grained Parameterized Complexity Analysis of Graph Coloring Problems, Cluster Editing, Computing list homomorphisms in geometric intersection graphs, Complexity of \(C_k\)-coloring in hereditary classes of graphs, Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter, Parameterized algorithms and data reduction for the short secluded s‐t‐path problem, A note on hardness of computing recursive teaching dimension, On the complexity of the storyplan problem, Linear‐time algorithms for eliminating claws in graphs, The 2CNF Boolean formula satisfiability problem and the linear space hypothesis, Improved (In-)Approximability Bounds for d-Scattered Set, Hitting Minors on Bounded Treewidth Graphs. IV. An Optimal Algorithm, How to find a good explanation for clustering?, Non-interactive universal arguments, FPT algorithms for packing \(k\)-safe spanning rooted sub(di)graphs, Solving infinite-domain CSPs using the patchwork property, A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs, A survey of parameterized algorithms and the complexity of edge modification, What Is Known About Vertex Cover Kernelization?, Unnamed Item, Unnamed Item, Balanced connected partitions of graphs: approximation, parameterization and lower bounds, Computing maximum matchings in temporal graphs, Unnamed Item, Subsequences in bounded ranges: matching and analysis problems, A polyhedral perspective on tropical convolutions, Filling crosswords is very hard, The pumping lemma for regular languages is hard, Communication and information complexity, Unnamed Item, Counting Solutions to Polynomial Systems via Reductions, Unnamed Item, Many Visits TSP Revisited, The Optimal Design of Low-Latency Virtual Backbones, Finding Temporal Paths Under Waiting Time Constraints., Slightly Superexponential Parameterized Problems, On the complexity of \(k\)-SAT, Component order connectivity in directed graphs, Intersection graphs of non-crossing paths, Strong triadic closure in cographs and graphs of low maximum degree, Efficient algorithms for measuring the funnel-likeness of DAGs, Parameterized aspects of triangle enumeration, When can graph hyperbolicity be computed in linear time?, Ruling out FPT algorithms for weighted coloring on forests, Default logic and bounded treewidth, Optimality program in segment and string graphs, Can Romeo and Juliet meet? Or rendezvous games with adversaries on graphs, Bounding the Running Time of Algorithms for Scheduling and Packing Problems, On Structural Parameterizations of Hitting Set: Hitting Paths in Graphs Using 2-SAT, Parameterized Complexity of Directed Steiner Tree on Sparse Graphs, On Structural Parameterizations of Hitting Set: Hitting Paths in Graphs Using 2-SAT, On the complexity of finding internally vertex-disjoint long directed paths, On cycle transversals and their connected variants in the absence of a small linear forest, Parameterized complexity of min-power asymmetric connectivity, Your rugby mates don't need to know your colleagues: triadic closure with edge colors, On the complexity of finding large odd induced subgraphs and odd colorings, Parameterized complexity of conflict-free set cover, The double exponential runtime is tight for 2-stage stochastic ILPs, Graph square roots of small distance from degree one graphs, Computing maximum independent set on outerstring graphs and their relatives, Obtaining a proportional allocation by deleting items, The perfect matching cut problem revisited, The double exponential runtime is tight for 2-stage stochastic ILPs, Recognizing \(k\)-clique extendible orderings, The perfect matching cut problem revisited, An EPTAS for scheduling on unrelated machines of few different types, A Subexponential Parameterized Algorithm for Proper Interval Completion, Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions), Parameterized complexity of diameter, Matching cut in graphs with large minimum degree, Rank Vertex Cover as a Natural Problem for Algebraic Compression, Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses, Dynamic programming for graphs on surfaces, Fine-Grained Complexity of the Graph Homomorphism Problem for Bounded-Treewidth Graphs, Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic $\tilde{O}(n^{5/3})$ Time, Unnamed Item, Unnamed Item, Unnamed Item, Offensive alliances in graphs, Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations, Defective Coloring on Classes of Perfect Graphs, Calculation of Discrepancy Measures and Applications, Matching Triangles and Basing Hardness on an Extremely Popular Conjecture, Destroying Bicolored $P_3$s by Deleting Few Edges, On the Fine Grained Complexity of Finite Automata Non-emptiness of Intersection, Four Shorts Stories on Surprising Algorithmic Uses of Treewidth, Games, Puzzles and Treewidth, Exploiting $c$-Closure in Kernelization Algorithms for Graph Problems, Maximum Minimal Vertex Cover Parameterized by Vertex Cover, Parameterized Algorithms for Power-Efficient Connected Symmetric Wireless Sensor Networks, On Treewidth and Stable Marriage: Parameterized Algorithms and Hardness Results (Complete Characterization), Known Algorithms for Edge Clique Cover are Probably Optimal, On the Complexity of Scaffolding Problems: From Cliques to Sparse Graphs, Parameterized Lower Bound and NP-Completeness of Some H-Free Edge Deletion Problems, Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs, Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Unless SETH is False), Parameterized Algorithms for Power-Efficiently Connecting Wireless Sensor Networks: Theory and Experiments, The Time Complexity of Constraint Satisfaction, Parameterized (Approximate) Defective Coloring, Moderately Exponential Approximation: Bridging the Gap Between Exact Computation and Polynomial Approximation, Unnamed Item, Tight Lower Bounds for the Complexity of Multicoloring, Unnamed Item, From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More, Finding Points in General Position, Unnamed Item, Unnamed Item, Unnamed Item, Graph Motif Problems Parameterized by Dual, Revisiting Decomposition by Clique Separators, Hitting Minors on Bounded Treewidth Graphs. I. General Upper Bounds, Finer Tight Bounds for Coloring on Clique-Width, Lower Bounds for Dynamic Programming on Planar Graphs of Bounded Cutwidth, ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network, Approximate Clustering with Same-Cluster Queries, Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds, KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation, Temporal Vertex Cover with a Sliding Time Window, Fine-grained Lower Bounds on Cops and Robbers, Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut, Dual parameterization of Weighted Coloring, Computing the Chromatic Number Using Graph Decompositions via Matrix Rank, On the Optimality of Pseudo-polynomial Algorithms for Integer Programming, Lower Bounds for Kernelizations and Other Preprocessing Procedures, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, On the Complexity of Solving Restricted Word Equations, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Parameterized Complexity of the Workflow Satisfiability Problem, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, On Geometric Set Cover for Orthants, Longest common substring made fully dynamic, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Fast approximation of eccentricities and distances in hyperbolic graphs, Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs, The Parameterized Complexity of k-Flip Local Search for SAT and MAX SAT, Complexity of Computing the Anti-Ramsey Numbers for Paths., Testing the Complexity of a Valued CSP Language, Coloring Graphs with Constraints on Connectivity, Hitting Forbidden Induced Subgraphs on Bounded Treewidth Graphs, Fine-Grained Reductions and Quantum Speedups for Dynamic Programming., Path Contraction Faster Than 2^n, A Simple Gap-Producing Reduction for the Parameterized Set Cover Problem, Decomposition of Map Graphs with Applications., Packing Arc-Disjoint Cycles in Tournaments, Algorithmic Applications of Tree-Cut Width, Unnamed Item, Unnamed Item, Comparing Degenerate Strings, Balanced Hashing, Color Coding and Approximate Counting, The Complexity of Satisfiability of Small Depth Circuits, Time Complexity of Constraint Satisfaction via Universal Algebra, Improved Bounds for 3SUM, k-SUM, and Linear Degeneracy, Does Looking Inside a Circuit Help, Subexponential parameterized algorithms for graphs of polynomial growth, Fine-Grained Complexity of Rainbow Coloring and its Variants., A Linear-Time Parameterized Algorithm for Node Unique Label Cover, Tight Lower Bounds for List Edge Coloring, More Applications of the $d$-Neighbor Equivalence: Acyclicity and Connectivity Constraints, Toward Tight Approximation Bounds for Graph Diameter and Eccentricities, Parameterized Approximation Algorithms for Bidirected Steiner Network Problems, Backdoors into Two Occurrences, Unnamed Item, Unnamed Item, Unnamed Item, Maximal Common Subsequence Algorithms, Linear-Time Algorithm for Long LCF with k Mismatches, Quantum de Finetti theorems under local measurements with applications, Tight Complexity Bounds for FPT Subgraph Problems Parameterized by Clique-Width, Simultaneous Approximation of Constraint Satisfaction Problems, Lower Bounds for the Graph Homomorphism Problem, Linear Time Parameterized Algorithms for Subset Feedback Vertex Set, On the Fine-Grained Complexity of Rainbow Coloring, Subexponential Time Algorithms for Finding Small Tree and Path Decompositions, On the Equivalence among Problems of Bounded Width, Weighted proper orientations of trees and graphs of bounded treewidth, Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis, A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter, Unnamed Item, The Birth and Early Years of Parameterized Complexity, A Basic Parameterized Complexity Primer, Parameterized Complexity and Subexponential-Time Computability, Studies in Computational Aspects of Voting, FPT Suspects and Tough Customers: Open Problems of Downey and Fellows, What’s Next? Future Directions in Parameterized Complexity, Parameterized Vertex Deletion Problems for Hereditary Graph Classes with a Block Property, Arithmetic Circuits, Monomial Algebras and Finite Automata, Genus characterizes the complexity of certain graph problems: Some tight results, Partition into triangles on bounded degree graphs, Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis, ON OPTIMAL INVERTERS, Parameterized complexity classes beyond para-NP, Narrow sieves for parameterized paths and packings, Polynomial kernelization for removing induced claws and diamonds, A faster diameter problem algorithm for a chordal graph, with a connection to its center problem, Simultaneous feedback edge set: a parameterized perspective, The graph motif problem parameterized by the structure of the input graph, A subexponential-time algorithm for the maximum independent set problem in \(P_t\)-free graphs, A tight lower bound for vertex planarization on graphs of bounded treewidth, The hierarchical Chinese postman problem: the slightest disorder makes it hard, yet disconnectedness is manageable, On the complexity of various parameterizations of common induced subgraph isomorphism, Hitting forbidden subgraphs in graphs of bounded treewidth, Packing arc-disjoint cycles in tournaments, Sparsification upper and lower bounds for graph problems and not-all-equal SAT, An FPT algorithm and a polynomial kernel for linear rankwidth-1 vertex deletion, Parameterized complexity dichotomy for \((r, \ell)\)-\textsc{Vertex Deletion}, Parameterized and Subexponential-Time Complexity of Satisfiability Problems and Applications, Treewidth-aware reductions of normal \textsc{ASP} to \textsc{SAT} - is normal \textsc{ASP} Harder than \textsc{SAT} after all?, On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem, On the Exact Complexity of Polyomino Packing, The Relative Exponential Time Complexity of Approximate Counting Satisfying Assignments, Algorithms Solving the Matching Cut Problem, Can Romeo and Juliet meet? Or rendezvous games with adversaries on graphs, On the complexity landscape of connected \(f\)-factor problems, Longest common substring with approximately \(k\) mismatches, Mean isoperimetry with control on outliers: exact and approximation algorithms, On the parameterized complexity of grid contraction, Subquadratic algorithms for succinct stable matching, Multidimensional Binary Vector Assignment Problem: Standard, Structural and Above Guarantee Parameterizations, Complement, Complexity, and Symmetric Representation, Further parameterized algorithms for the \(\mathcal{F}\)-free edge deletion problem, Knapsack problems: a parameterized point of view, Super-polynomial approximation branching algorithms, Solving projected model counting by utilizing treewidth and its limits, Parameterized complexity of envy-free resource allocation in social networks, Structural parameters, tight bounds, and approximation for \((k, r)\)-center, Parameterized complexity of computing maximum minimal blocking and hitting sets, Fast exact dynamic time warping on run-length encoded time series, On the optimality of pseudo-polynomial algorithms for integer programming, The parameterized complexity of stabbing rectangles, Invited talks, A tight lower bound for edge-disjoint paths on planar DAGs, A multistage view on 2-satisfiability, New exact algorithms for the 2-constraint satisfaction problem, Grundy Coloring and friends, half-graphs, bicliques, The complexity of routing problems in forbidden-transition graphs and edge-colored graphs, Unnamed Item, Algorithmic Aspects of the Maximum Colorful Arborescence Problem, Tight bounds for parameterized complexity of cluster editing with a small number of clusters, Predecessor existence problems for finite discrete dynamical systems, Ranking and Drawing in Subexponential Time, Path Contraction Faster than $2^n$, Computing Vertex-Surjective Homomorphisms to Partially Reflexive Trees, Satisfiability Certificates Verifiable in Subexponential Time, The complexity of Unique \(k\)-SAT: An isolation lemma for \(k\)-CNFs, Exact algorithms for the Hamiltonian cycle problem in planar graphs, On the Exact Complexity of Evaluating Quantified k-CNF, Exponential Time Complexity of Weighted Counting of Independent Sets, The Exponential Time Complexity of Computing the Probability That a Graph Is Connected, The role of planarity in connectivity problems parameterized by treewidth, Partition into Triangles on Bounded Degree Graphs, Half-integrality, LP-branching, and FPT Algorithms, On the Solvability Problem for Restricted Classes of Word Equations, A Framework for Exponential-Time-Hypothesis--Tight Algorithms and Lower Bounds in Geometric Intersection Graphs, Complexity Theory Basics: NP and NL, k-SAT Is No Harder Than Decision-Unique-k-SAT, New Plain-Exponential Time Classes for Graph Homomorphism, Parameterized Algorithmics for Graph Modification Problems: On Interactions with Heuristics, Polynomial Kernelization for Removing Induced Claws and Diamonds, Exploring the Subexponential Complexity of Completion Problems, A Multivariate Approach for Checking Resiliency in Access Control, Problems on Finite Automata and the Exponential Time Hypothesis, Tight lower bounds for certain parameterized NP-hard problems, Parameterized computation and complexity: a new approach dealing with NP-hardness, Moderately exponential time and fixed parameter approximation algorithms, Balanced branchings in digraphs, Characterization and complexity results on jumping finite automata, Length-bounded cuts: proper interval graphs and structural parameters, Scheduling lower bounds via AND subset sum, On the existence of subexponential parameterized algorithms, Improved exact algorithms for MAX-SAT, Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity, Efficient computation of sequence mappability, On minimizing regular expressions without Kleene star, Complexity and approximation results on the shared transportation problem, A primal-dual approximation algorithm for \textsc{minsat}, Quantifying hierarchical conflicts in homology statements, Component order connectivity in directed graphs, Learning from positive and negative examples: dichotomies and parameterized algorithms, Parameterized complexity of fair deletion problems, Why did the shape of your network change? (On detecting network anomalies via non-local curvatures), Parameterized orientable deletion, Subexponential algorithm for \(d\)-cluster edge deletion: exception or rule?, On the exact complexity of polyomino packing, Dominating set based exact algorithms for \(3\)-coloring, On the complexity of detecting hazards, On the exact complexity of evaluating quantified \(k\)-\textsc{cnf}, The \textsc{Maximum Colorful Arborescence} problem: how (computationally) hard can it be?, Parsimonious formulations for low-diameter clusters, On closest pair in Euclidean metric: monochromatic is as hard as bichromatic, Parameterized \(k\)-clustering: tractability island, On structural parameterizations of the bounded-degree vertex deletion problem, Finding temporal paths under waiting time constraints, Waypoint routing on bounded treewidth graphs, The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems, Approximation and hardness of shift-Bribery, Subexponential fixed-parameter algorithms for partial vector domination, Complexity of Grundy coloring and its variants, Algorithms, kernels and lower bounds for the flood-it game parameterized by the vertex cover number, Improved integrality gap upper bounds for traveling salesperson problems with distances one and two, On the approximability of robust network design, A tight lower bound for planar Steiner orientation, Algorithms for dominating clique problems, A multi-parameter analysis of hard problems on deterministic finite automata, The inverse Voronoi problem in graphs. I: Hardness, Temporal vertex cover with a sliding time window, Pursuing a fast robber on a graph, On the parameterized complexity of the geodesic hull number, Tight conditional lower bounds for longest common increasing subsequence, New tools and connections for exponential-time approximation, Revenue maximization in Stackelberg pricing games: beyond the combinatorial setting, Routing with congestion in acyclic digraphs, Aspects of upper defensive alliances, Soft clustering-based scenario bundling for a progressive hedging heuristic in stochastic service network design, A note on the fine-grained complexity of MIS on regular graphs, Producing genomic sequences after genome scaffolding with ambiguous paths: complexity, approximation and lower bounds, Subexponential parameterized algorithms and kernelization on almost chordal graphs, Reducing graph transversals via edge contractions, Sliding window temporal graph coloring, Measuring what matters: a hybrid approach to dynamic programming with treewidth, A polynomial kernel for trivially perfect editing, Beating treewidth for average-case subgraph isomorphism, Faster algorithms for counting subgraphs in sparse graphs, Metric dimension parameterized by treewidth, On the computational complexity of length- and neighborhood-constrained path problems, A unifying model for locally constrained spanning tree problems, On the parameterized complexity of graph modification to first-order logic properties, Hitting minors on bounded treewidth graphs. III. Lower bounds, Hitting forbidden induced subgraphs on bounded treewidth graphs, Many-visits TSP revisited, Fine-grained complexity of rainbow coloring and its variants, Efficiently enumerating hitting sets of hypergraphs arising in data profiling, Minimum fill-in: inapproximability and almost tight lower bounds, Hitting minors on bounded treewidth graphs. II. Single-exponential algorithms, Sparsification lower bound for linear spanners in directed graphs, Stable matchings with covering constraints: a complete computational trichotomy, The complexity of dependency detection and discovery in relational databases, Structurally parameterized \(d\)-scattered set, Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression, On the complexity of solution extension of optimization problems, On some FPT problems without polynomial Turing compressions, Deleting vertices to graphs of bounded genus, On knot-free vertex deletion: fine-grained parameterized complexity analysis of a deadlock resolution graph problem, Maximal common subsequence algorithms, Refined parameterizations for computing colored cuts in edge-colored graphs, Computing the chromatic number using graph decompositions via matrix rank, On subgraph complementation to \(H\)-free Graphs, Tractability of König edge deletion problems, Finding, hitting and packing cycles in subexponential time on unit disk graphs, CNF satisfiability in a subspace and related problems, Colouring non-even digraphs, Moderate exponential-time algorithms for scheduling problems, On subexponential and FPT-time inapproximability, Pure Nash equilibria in graphical games and treewidth, On sparsification for computing treewidth, Constructing NP-intermediate problems by blowing holes with parameters of various properties, Hardness of approximation for knapsack problems, Sitting closer to friends than enemies, revisited, Fast diameter and radius BFS-based computation in (weakly connected) real-world graphs, Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth, On the isomorphism problem for decision trees and decision lists, Fine-grained parameterized complexity analysis of graph coloring problems, An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems, A complexity and approximation framework for the maximization scaffolding problem, Tight bounds on subexponential time approximation of set cover and related problems, \(k\)-approximate quasiperiodicity under Hamming and edit distance, ProCount: weighted projected model counting with graded project-join trees

Cites Work

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:1604206&oldid=13901292"