A faster parameterized algorithm for treedepth

DOI10.1007/978-3-662-43948-7_77MaRDI QIDQ5167804zbMATH OpenOpenAlexFDO

Authors Felix Reidl, Fernando Sánchez Villaamil, Somnath Sikdar, Peter Rossmanith

Publication date 1 July 2014

Published in Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1401.7540

zbMATH Keywords

vertex rankingparameterized algorithmswidth measurestreedepthcentered coloring

Mathematics Subject Classification ID

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

Abstract: The width measure emph{treedepth}, also known as vertex ranking, centered coloring and elimination tree height, is a well-established notion which has recently seen a resurgence of interest. We present an algorithm which---given as input an $n$-vertex graph, a tree decomposition of the graph of width $w$, and an integer $t$---decides Treedepth, i.e. whether the treedepth of the graph is at most $t$, in time $2^{O(wt)}cdotn$. If necessary, a witness structure for the treedepth can be constructed in the same running time. In conjunction with previous results we provide a simple algorithm and a fast algorithm which decide treedepth in time $2^{2^{O(t)}}cdotn$ and $2^{O(t^2)}cdotn$, respectively, which do not require a tree decomposition as part of their input. The former answers an open question posed by Ossona de Mendez and Nesetril as to whether deciding Treedepth admits an algorithm with a linear running time (for every fixed $t$) that does not rely on Courcelle's Theorem or other heavy machinery. For chordal graphs we can prove a running time of $2^{O(tlogt)}cdotn$ for the same algorithm.

Recommendations

• Computing Tree-Depth Faster Than 2 n
• Computing tree-depth faster than \(2^n\)
• Treedepth Parameterized by Vertex Cover Number.
• Improved bounds for the excluded-minor approximation of treedepth
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth

Cited in

(39)

• Polynomial kernels for hitting forbidden minors under structural parameterizations
• On the size of minimal separators for treedepth decomposition
• Computing treedepth in polynomial space and linear FPT time
• Improved bounds for the excluded-minor approximation of treedepth
• On vertex rankings of graphs and its relatives
• A polynomial excluded-minor approximation of treedepth
• Elimination Distance to Bounded Degree on Planar Graphs
• Polynomial treedepth bounds in linear colorings
• Treedepth bounds in linear colorings
• On the lossy kernelization for connected treedepth deletion set
• How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
• Elimination distance to bounded degree on planar graphs preprint
• On the Parameterized Complexity of Clique Elimination Distance
• Faster parameterized algorithms for modification problems to minor-closed classes
• A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs
• Combinatorial generation via permutation languages. IV: Elimination trees
• Parameterized algorithms for queue layouts
• A speed-up for the commute between subword trees and DAWGs.
• A Faster CREW PRAM Algorithm for Computing Cartesian Trees
• Polynomial Kernels for Hitting Forbidden Minors under Structural Parameterizations.
• FPT algorithms to compute the elimination distance to bipartite graphs and more
• Treedepth Parameterized by Vertex Cover Number.
• Algorithmic meta-theorems for combinatorial reconfiguration revisited
• How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
• On the power of tree-depth for fully polynomial FPT algorithms
• Eccentricity queries and beyond using hub labels
• Routing few robots in a crowded network
• scientific article; zbMATH DE number 7525471 (Why is no real title available?)
• Uniformly Automatic Classes of Finite Structures
• (Near)-optimal algorithms for sparse separable convex integer programs
• The PACE 2020 Parameterized Algorithms and Computational Experiments Challenge: Treedepth.
• Computing tree-depth faster than \(2^n\)
• Exploring the gap between treedepth and vertex cover through vertex integrity
• Structural sparsity of complex networks: bounded expansion in random models and real-world graphs
• Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space
• Faster computation of path-width
• Computing Tree-Depth Faster Than 2 n
• Algorithmic meta-theorems for combinatorial reconfiguration revisited
• Parameterized Algorithms for Queue Layouts

This page was built for publication: A faster parameterized algorithm for treedepth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5167804)