Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time

DOI10.1109/FOCS.2011.23zbMath1292.68122OpenAlexW2059273723MaRDI QIDQ5494962

Michał Pilipczuk, Marcin Pilipczuk, Jakub Onufry Wojtaszczyk, Jesper Nederlof, Johan M. M. van Rooij, Marek Cygan

Publication date: 30 July 2014

Published in: 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1109/focs.2011.23

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)

Related Items

On the Exact Complexity of Hamiltonian Cycle and q-Colouring in Disk Graphs, Spotting Trees with Few Leaves, On Computing the Hamiltonian Index of 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, Grouped domination parameterized by vertex cover, twin cover, and beyond, Parameterized complexity of finding a spanning tree with minimum reload cost diameter, Detours in directed graphs, Hitting Minors on Bounded Treewidth Graphs. IV. An Optimal Algorithm, Unnamed Item, Unnamed Item, Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space, Graph burning and non-uniform \(k\)-centers for small treewidth, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, 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, Computing the Chromatic Number Using Graph Decompositions via Matrix Rank, On the Optimality of Pseudo-polynomial Algorithms for Integer Programming, In)approximability of Maximum Minimal FVS, Improved FPT Algorithms for Deletion to Forest-Like Structures., The Asymmetric Travelling Salesman Problem In Sparse Digraphs., Parameterized algorithms for the happy set problem, Unnamed Item, Slightly Superexponential Parameterized Problems, Unnamed Item, Unnamed Item, An improved FPT algorithm for independent feedback vertex set, Parameterized Complexity of Directed Steiner Tree on Sparse Graphs, An optimal XP algorithm for Hamiltonian cycle on graphs of bounded clique-width, Minimum reload cost graph factors, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, The parameterized complexity of cycle packing: indifference is not an issue, On the Parameterized Complexity of [1,j-Domination Problems], Hitting Forbidden Induced Subgraphs on Bounded Treewidth Graphs, Decomposition of Map Graphs with Applications., Packing Cycles Faster Than Erdos--Posa, Derandomizing Isolation in Space-Bounded Settings, Unnamed Item, Contraction-Bidimensionality of Geometric Intersection Graphs, On the Parameterized Complexity of Contraction to Generalization of Trees., On the Complexity of Bounded Context Switching., Dynamic programming for graphs on surfaces, More Applications of the $d$-Neighbor Equivalence: Acyclicity and Connectivity Constraints, Unnamed Item, Finding Hamiltonian Cycle in Graphs of Bounded Treewidth: Experimental Evaluation, On Treewidth and Related Parameters of Random Geometric Graphs, Faster exact algorithms for some terminal set problems, A parameterized complexity view on collapsing \(k\)-cores, Contraction bidimensionality of geometric intersection graphs, An improved deterministic parameterized algorithm for cactus vertex deletion, Spotting Trees with Few Leaves, Linear Time Parameterized Algorithms for Subset Feedback Vertex Set, On the Equivalence among Problems of Bounded Width, Unnamed Item, Unnamed Item, Rural postman parameterized by the number of components of required edges, Fixed-Parameter Tractability of Treewidth and Pathwidth, Graph Minors and Parameterized Algorithm Design, What’s Next? Future Directions in Parameterized Complexity, On the feedback number of 3-uniform linear extremal hypergraphs, New analysis and computational study for the planar connected dominating set problem, Algorithms and kernels for \textsc{Feedback Set} problems in generalizations of tournaments, Known Algorithms for Edge Clique Cover are Probably Optimal, Bivariate Complexity Analysis of Almost Forest Deletion, Unnamed Item, Simultaneous feedback edge set: a parameterized perspective, Hitting forbidden subgraphs in graphs of bounded treewidth, Towards a polynomial kernel for directed feedback vertex set, Computing the largest bond and the maximum connected cut of a graph, Linear kernels for outbranching problems in sparse digraphs, Extending the kernel for planar Steiner tree to the number of Steiner vertices, A polynomial kernel for block graph deletion, Efficient FPT algorithms for (strict) compatibility of unrooted phylogenetic trees, Space saving by dynamic algebraization based on tree-depth, Kernels for deletion to classes of acyclic digraphs, A \(9k\) kernel for nonseparating independent set in planar graphs, Minimum connected transversals in graphs: new hardness results and tractable cases using the price of connectivity, Parameterized edge Hamiltonicity, Generalized Pseudoforest Deletion: Algorithms and Uniform Kernel, Beyond bidimensionality: parameterized subexponential algorithms on directed graphs, Odd cycle transversal in mixed graphs, On the complexity landscape of connected \(f\)-factor problems, Effective computation of immersion obstructions for unions of graph classes, Improved Steiner tree algorithms for bounded treewidth, Generalized Pseudoforest Deletion: Algorithms and Uniform Kernel, Bivariate complexity analysis of \textsc{Almost Forest Deletion}, Fast exact algorithms for some connectivity problems parameterized by clique-width, A faster parameterized algorithm for pseudoforest deletion, On the optimality of pseudo-polynomial algorithms for integer programming, A randomized polynomial kernel for subset feedback vertex set, Catalan structures and dynamic programming in \(H\)-minor-free graphs, On computing the Hamiltonian index of graphs, Contracting graphs to paths and trees, An improved parameterized algorithm for the independent feedback vertex set problem, Confronting intractability via parameters, On the Maximum Weight Minimal Separator, Backdoor Sets for CSP., Clifford algebras meet tree decompositions, Enumerating minimal subset feedback vertex sets, Practical algorithms for MSO model-checking on tree-decomposable graphs, Solving the 2-disjoint connected subgraphs problem faster than \(2^n\), Edge bipartization faster than \(2^k\), On directed covering and domination problems, On feedback vertex set: new measure and new structures, Explicit linear kernels for packing problems, Subset Feedback Vertex Set Is Fixed-Parameter Tractable, An improved FPT algorithm for almost forest deletion problem, A new upper bound for the traveling salesman problem in cubic graphs, On parameterized independent feedback vertex set, Scheduling partially ordered jobs faster than \(2^n\), On the parameterized complexity of contraction to generalization of trees, An improved FPT algorithm and a quadratic kernel for pathwidth one vertex deletion, Algebraic methods in the congested clique, Faster deterministic \textsc{Feedback Vertex Set}, Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms, Dynamic parameterized problems, Structural parameterizations of undirected feedback vertex set: FPT algorithms and kernelization, On the parameterized complexity of \([1,j\)-domination problems], An approximation algorithm for the \(l\)-pseudoforest deletion problem, Subexponential parameterized algorithms and kernelization on almost chordal graphs, The role of planarity in connectivity problems parameterized by treewidth, Improved analysis of highest-degree branching for feedback vertex set, A single-exponential FPT algorithm for the \(K_4\)-\textsc{minor cover} problem, Hitting minors on bounded treewidth graphs. III. Lower bounds, Hitting forbidden induced subgraphs on bounded treewidth graphs, (In)approximability of maximum minimal FVS, Many-visits TSP revisited, Half-integrality, LP-branching, and FPT Algorithms, Hitting minors on bounded treewidth graphs. II. Single-exponential algorithms, Subset feedback vertex set on graphs of bounded independent set size, Upper and lower degree-constrained graph orientation with minimum penalty, Computing the number of \(k\)-component spanning forests of a graph with bounded treewidth, Finding Hamiltonian Cycle in Graphs of Bounded Treewidth, Kernelization of Graph Hamiltonicity: Proper $H$-Graphs, Parameterised algorithms for deletion to classes of DAGs, The parameterized complexity of the minimum shared edges problem, How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?, Computing the chromatic number using graph decompositions via matrix rank, Euler Digraphs, On the maximum weight minimal separator, Speeding up dynamic programming with representative sets: an experimental evaluation of algorithms for Steiner Tree on tree decompositions, Fixed-parameter tractability for subset feedback set problems with parity constraints, Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth, A generic convolution algorithm for join operations on tree decompositions, On group feedback vertex set parameterized by the size of the cutset, Solving Hamiltonian cycle by an EPT algorithm for a non-sparse parameter