Slightly Superexponential Parameterized Problems
From MaRDI portal
Publication:5745079
DOI10.1137/16M1104834zbMath1393.68077arXiv1902.08723OpenAlexW2803460775MaRDI QIDQ5745079
Saket Saurabh, Daniel Lokshtanov, Dániel Marx
Publication date: 5 June 2018
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1902.08723
Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Algorithms on strings (68W32)
Related Items
Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths ⋮ On the parameterized complexity of maximum degree contraction problem ⋮ Exploiting $c$-Closure in Kernelization Algorithms for Graph Problems ⋮ A Subexponential Parameterized Algorithm for Directed Subset Traveling Salesman Problem on Planar Graphs ⋮ Streaming deletion problems Parameterized by vertex cover ⋮ Hitting Minors on Bounded Treewidth Graphs. IV. An Optimal Algorithm ⋮ Solving infinite-domain CSPs using the patchwork property ⋮ MCSP is hard for read-once nondeterministic branching programs ⋮ Unnamed Item ⋮ General lower bounds and improved algorithms for infinite-domain CSPs ⋮ Unnamed Item ⋮ Hitting Minors on Bounded Treewidth Graphs. I. General Upper Bounds ⋮ On the Parameterized Complexity of Maximum Degree Contraction Problem. ⋮ Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms ⋮ Measuring what matters: a hybrid approach to dynamic programming with treewidth ⋮ On the complexity of finding large odd induced subgraphs and odd colorings ⋮ Parameterized complexity of conflict-free set cover ⋮ Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth. ⋮ Finding Hamiltonian Cycle in Graphs of Bounded Treewidth ⋮ Approximation Algorithms for Low-Distortion Embeddings into Low-Dimensional Spaces ⋮ Offensive alliances in graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Tight complexity bounds for FPT subgraph problems parameterized by the clique-width
- Bandwidth and distortion revisited
- A three-string approach to the closest string problem
- An exact algorithm for minimum distortion embedding
- Finding odd cycle transversals.
- Cuts, trees and \(\ell_1\)-embeddings of graphs
- Improved upper bounds for vertex cover
- On the computational complexity of vertex integrity and component order connectivity
- Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
- Simple and improved parameterized algorithms for multiterminal cuts
- Generalized coloring for tree-like graphs
- Fixed-parameter algorithms for CLOSEST STRING and related problems
- On the complexity of finding common approximate substrings.
- Distinguishing string selection problems.
- Which problems have strongly exponential complexity?
- On the existence of subexponential parameterized algorithms
- Graph minors. XIII: The disjoint paths problem
- Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions
- Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
- An \(\mathcal O(2^{O(k)}n^{3})\) FPT algorithm for the undirected feedback vertex set problem
- Covering things with things
- Parametrized complexity theory.
- Bounded fixed-parameter tractability and \(\log^{2}n\) nondeterministic bits
- Tour Merging via Branch-Decomposition
- Distortion is Fixed Parameter Tractable
- Problems Parameterized by Treewidth Tractable in Single Exponential Time: A Logical Approach
- Planar Subgraph Isomorphism Revisited
- Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms
- Parameterized Vertex Deletion Problems for Hereditary Graph Classes with a Block Property
- On the closest string and substring problems
- Closest Substring Problems with Small Distances
- Covering a Set of Points with a Minimum Number of Lines
- Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
- Low distortion maps between point sets
- Low-distortion embeddings of general metrics into the line
- More Efficient Algorithms for Closest String and Substring Problems
- Fast FAST
- Interval Completion Is Fixed Parameter Tractable
- Storing a Sparse Table with 0 (1) Worst Case Access Time
- On the Computational Complexity of Combinatorial Problems
- Color-coding
- Subgraph Isomorphism in Planar Graphs and Related Problems
- Linear Recognition of Almost Interval Graphs
- Efficient Algorithms for the Closest String and Distinguishing String Selection Problems
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Parameterized Algorithms
- Graph Drawing
- A Subexponential Parameterized Algorithm for Proper Interval Completion
- Fundamentals of Computation Theory
