Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth

DOI10.1016/j.ic.2014.12.008zbMath1327.68126OpenAlexW4238913085WikidataQ59567423 ScholiaQ59567423MaRDI QIDQ2347800

Jesper Nederlof, Marek Cygan, Stefan Kratsch, Hans L. Bodlaender

Publication date: 9 June 2015

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2014.12.008

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering ⋮ Computing directed Steiner path covers ⋮ On the Exact Complexity of Hamiltonian Cycle and q-Colouring in Disk Graphs ⋮ On Computing the Hamiltonian Index of Graphs ⋮ Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs ⋮ Four Shorts Stories on Surprising Algorithmic Uses of Treewidth ⋮ Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices ⋮ Fast Algorithms for Join Operations on Tree Decompositions ⋮ Contraction bidimensionality of geometric intersection graphs ⋮ On exploring always-connected temporal graphs of small pathwidth ⋮ An efficient polynomial time approximation scheme for the vertex cover \(P_3\) problem on planar graphs ⋮ Fixed-parameter algorithms for rectilinear Steiner tree and rectilinear traveling salesman problem in the plane ⋮ Structural parameterizations with modulator oblivion ⋮ Unnamed Item ⋮ Steiner trees for hereditary graph classes: a treewidth perspective ⋮ Computing the largest bond and the maximum connected cut of a graph ⋮ Extending the kernel for planar Steiner tree to the number of Steiner vertices ⋮ On the parameterized complexity of the connected flow and many visits TSP problem ⋮ The homogeneous broadcast problem in narrow and wide strips. I: Algorithms ⋮ Structure of Graphs with Locally Restricted Crossings ⋮ On the minimum cycle cover problem on graphs with bounded co-degeneracy ⋮ Grouped domination parameterized by vertex cover, twin cover, and beyond ⋮ Parameterized algorithms and data reduction for the short secluded s‐t‐path problem ⋮ Treelength of series-parallel graphs ⋮ Fast exact algorithms for some connectivity problems parameterized by clique-width ⋮ Solving Steiner trees: Recent advances, challenges, and perspectives ⋮ Clique-based separators for geometric intersection graphs ⋮ Grouped domination parameterized by vertex cover, twin cover, and beyond ⋮ Kernelization for feedback vertex set via elimination distance to a forest ⋮ Detours in directed graphs ⋮ Counting cycles on planar graphs in subexponential time ⋮ Solving cut-problems in quadratic time for graphs with bounded treewidth ⋮ Hitting Minors on Bounded Treewidth Graphs. IV. An Optimal Algorithm ⋮ A faster parameterized algorithm for pseudoforest deletion ⋮ An ETH-Tight Exact Algorithm for Euclidean TSP ⋮ Counting cycles on planar graphs in subexponential time ⋮ Weighted connected matchings ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space ⋮ On \(d\)-stable locally checkable problems parameterized by mim-width ⋮ FPT and kernelization algorithms for the induced tree problem ⋮ Unnamed Item ⋮ On computing the Hamiltonian index of graphs ⋮ The complexity of routing problems in forbidden-transition graphs and edge-colored graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Hitting Minors on Bounded Treewidth Graphs. I. General Upper Bounds ⋮ Lower Bounds for Dynamic Programming on Planar Graphs of Bounded Cutwidth ⋮ Clifford algebras meet tree decompositions ⋮ FPT Algorithms for FVS Parameterized by Split and Cluster Vertex Deletion Sets and Other Parameters ⋮ Waypoint routing on bounded treewidth graphs ⋮ Computing the Chromatic Number Using Graph Decompositions via Matrix Rank ⋮ How to Secure Matchings against Edge Failures ⋮ In)approximability of Maximum Minimal FVS ⋮ The Asymmetric Travelling Salesman Problem In Sparse Digraphs. ⋮ Unnamed Item ⋮ Slightly Superexponential Parameterized Problems ⋮ Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms ⋮ Unnamed Item ⋮ Dynamic parameterized problems ⋮ Structural parameterizations of undirected feedback vertex set: FPT algorithms and kernelization ⋮ Mim-width. II. The feedback vertex set problem ⋮ Subexponential parameterized algorithms and kernelization on almost chordal graphs ⋮ An optimal XP algorithm for Hamiltonian cycle on graphs of bounded clique-width ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Walking through waypoints ⋮ The complexity of tree partitioning ⋮ Hitting minors on bounded treewidth graphs. III. Lower bounds ⋮ Hitting forbidden induced subgraphs on bounded treewidth graphs ⋮ (In)approximability of maximum minimal FVS ⋮ Finding Detours is Fixed-Parameter Tractable ⋮ Hitting minors on bounded treewidth graphs. II. Single-exponential algorithms ⋮ Travelling on graphs with small highway dimension ⋮ A Framework for Exponential-Time-Hypothesis--Tight Algorithms and Lower Bounds in Geometric Intersection Graphs ⋮ How to Secure Matchings Against Edge Failures ⋮ Hitting Forbidden Induced Subgraphs on Bounded Treewidth Graphs ⋮ Computing permanents and counting Hamiltonian cycles by listing dissimilar vectors ⋮ Computing the number of \(k\)-component spanning forests of a graph with bounded treewidth ⋮ Finding Hamiltonian Cycle in Graphs of Bounded Treewidth ⋮ Revisiting connected vertex cover: FPT algorithms and lossy kernels ⋮ Computing the chromatic number using graph decompositions via matrix rank ⋮ On the maximum weight minimal separator ⋮ Finding, hitting and packing cycles in subexponential time on unit disk graphs ⋮ More Applications of the $d$-Neighbor Equivalence: Acyclicity and Connectivity Constraints ⋮ Fine-Grained Complexity of the Graph Homomorphism Problem for Bounded-Treewidth Graphs ⋮ Node multiway cut and subset feedback vertex set on graphs of bounded mim-width ⋮ Finding Hamiltonian Cycle in Graphs of Bounded Treewidth: Experimental Evaluation ⋮ A generic convolution algorithm for join operations on tree decompositions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Catalan structures and dynamic programming in \(H\)-minor-free graphs
• Boolean-width of graphs
• Graph minors. III. Planar tree-width
• Improved algorithms for feedback vertex set problems
• Finding paths of length \(k\) in \(O^{*}(2^k)\) time
• On two techniques of combining branching and treewidth
• A parameterized view on matroid optimization problems
• Matching is as easy as matrix inversion
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Communication complexity and combinatorial lattice theory
• Treewidth. Computations and approximations
• Which problems have strongly exponential complexity?
• On limited nondeterminism and the complexity of the V-C dimension
• On the ``log rank-conjecture in communication complexity
• Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions
• Trimmed Moebius inversion and graphs of bounded degree
• Approximating clique-width and branch-width
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Speeding Up Dynamic Programming with Representative Sets
• Tour Merging via Branch-Decomposition
• Locally checkable proofs
• Problems Parameterized by Treewidth Tractable in Single Exponential Time: A Logical Approach
• Faster Algebraic Algorithms for Path and Packing Problems
• On Feedback Vertex Set New Measure and New Structures
• An Improved Exact Algorithm for Cubic Graph TSP
• Limits and Applications of Group Algebras for Parameterized Problems
• Randomized Divide-and-Conquer: Improved Path, Matching, and Packing Algorithms
• On Linear Time Minor Tests with Depth-First Search
• Color-coding
• Fast Hamiltonicity Checking Via Bases of Perfect Matchings
• On the Number of Hamilton Cycles in Bounded Degree Graphs
• The Traveling Salesman Problem for Cubic Graphs
• STACS 2004
• Deterministic Single Exponential Time Algorithms for Connectivity Problems Parameterized by Treewidth
• Efficient Computation of Representative Sets with Applications in Parameterized and Exact Algorithms
• Multiplying matrices faster than coppersmith-winograd
• Treewidth: Structure and Algorithms
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Proofs from THE BOOK

This page was built for publication: Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth