2026-08-16T11:52:46Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20059 2024-05-31T13:11:11Z ddc:004 open_access

Fixed-Parameter Tractable Certified Algorithms for Covering and Dominating in Planar Graphs and Beyond Bumpus, Benjamin Merlin Jansen, Bart M. P. Venne, Jaime fixed-parameter tractability certified algorithms For a positive real γ ≥ 1, a γ-certified algorithm for a vertex-weighted graph optimization problem is an algorithm that, given a weighted graph (G,w), outputs a re-weighting of the graph obtained by scaling each weight individually with a factor between 1 and γ, along with a solution which is optimal for the perturbed weight function. Here we provide (1+ε)-certified algorithms for Dominating Set and H-Subgraph-Free-Deletion which, for any ε > 0, run in time f(1/ε)⋅n^𝒪(1) on minor-closed classes of graphs of bounded local tree-width with polynomially-bounded weights. We obtain our algorithms as corollaries of a more general result establishing FPT-time certified algorithms for problems admitting, at an intuitive level, certain "local solution-improvement properties". These results improve - in terms of generality, running time and parameter dependence - on Angelidakis, Awasthi, Blum, Chatziafratis and Dan’s XP-time (1+ε)-certified algorithm for Independent Set on planar graphs (ESA2019). Furthermore, our methods are also conceptually simpler: our algorithm is based on elementary local re-optimizations inspired by Baker’s technique, as opposed to the heavy machinery of the Sherali-Adams hierarchy required in previous work. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Benjamin Merlin Bumpus and Bart M. P. Jansen and Jaime Venne 2024 Is Part Of LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2024.19 urn:nbn:de:0030-drops-200595 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.19 eng https://creativecommons.org/licenses/by/4.0/legalcode