2026-07-23T01:23:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2318 2024-03-06T10:33:17Z ddc:004 open_access

Subexponential Algorithms for Partial Cover Problems Fomin, Fedor V. Lokshtanov, Daniel Raman, Venkatesh Saurabh, Saket Partial cover problems parameterized complexity subexponential time algorithms irrelevant vertex technique Partial Cover problems are optimization versions of fundamental and well studied problems like {\sc Vertex Cover} and {\sc Dominating Set}. Here one is interested in covering (or dominating) the maximum number of edges (or vertices) using a given number ($k$) of vertices, rather than covering all edges (or vertices). In general graphs, these problems are hard for parameterized complexity classes when parameterized by $k$. It was recently shown by Amini et. al. [{\em FSTTCS 08}\,] that {\sc Partial Vertex Cover} and {\sc Partial Dominating Set} are fixed parameter tractable on large classes of sparse graphs, namely $H$-minor free graphs, which include planar graphs and graphs of bounded genus. In particular, it was shown that on planar graphs both problems can be solved in time $2^{\cO(k)}n^{\cO(1)}$. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Fedor V. Fomin and Daniel Lokshtanov and Venkatesh Raman and Saket Saurabh 2009 Is Part Of LIPIcs, Volume 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2009.2318 urn:nbn:de:0030-drops-23186 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2009.2318 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode