2026-07-26T17:28:07Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6943 2024-03-06T10:38:49Z ddc:004 open_access

Treedepth Parameterized by Vertex Cover Number Kobayashi, Yasuaki Tamaki, Hisao Fixed-parameter algorithm Polynomial kernelization Structural parameterization Treedepth Vertex cover To solve hard graph problems from the parameterized perspective, structural parameters have commonly been used. In particular, vertex cover number is frequently used in this context. In this paper, we study the problem of computing the treedepth of a given graph G. We show that there are an O(tau(G)^3) vertex kernel and an O(4^{tau(G)}*tau(G)*n) time fixed-parameter algorithm for this problem, where tau(G) is the size of a minimum vertex cover of G and n is the number of vertices of G. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yasuaki Kobayashi and Hisao Tamaki 2017 Is Part Of LIPIcs, Volume 63, 11th International Symposium on Parameterized and Exact Computation (IPEC 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2016.18 urn:nbn:de:0030-drops-69438 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2016.18 eng https://creativecommons.org/licenses/by/3.0/legalcode