Approximating connected safe sets in weighted trees

DOI10.1016/J.DAM.2019.11.017zbMATH Open1440.05109arXiv1711.11412OpenAlexW2994296736MaRDI QIDQ2184684FDOQ2184684

Authors: Stefan Ehard, Dieter Rautenbach 

Publication date: 29 May 2020

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: For a graph $G$ and a non-negative integral weight function $w$ on the vertex set of $G$, a set $S$ of vertices of $G$ is $w$-safe if $w(C)geqw(D)$ for every component $C$ of the subgraph of $G$ induced by $S$ and every component $D$ of the subgraph of $G$ induced by the complement of $S$ such that some vertex in $C$ is adjacent to some vertex of $D$. The minimum weight $w(S)$ of a $w$-safe set $S$ is the safe number $s(G,w)$ of the weighted graph $(G,w)$, and the minimum weight of a $w$-safe set that induces a connected subgraph of $G$ is its connected safe number $cs(G,w)$. Bapat et al. showed that computing $cs(G,w)$ is NP-hard even when $G$ is a star. For a given weighted tree $(T,w)$, they described an efficient $2$-approximation algorithm for $cs(T,w)$ as well as an efficient $4$-approximation algorithm for $s(T,w)$. Addressing a problem they posed, we present a PTAS for the connected safe number of a weighted tree. Our PTAS partly relies on an exact pseudopolynomial time algorithm, which also allows to derive an asymptotic FPTAS for restricted instances. Finally, we extend a bound due to Fujita et al. from trees to block graphs.

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

Recommendations

• Safe sets, network majority on weighted trees
• Models and algorithms for the weighted safe set problem
• On the weighted safe set problem on paths and cycles
• Network majority on tree topological network
• Stable structure on safe set problems in vertex-weighted graphs

zbMATH Keywords

block graphsafe setconnected safe set

Mathematics Subject Classification ID

Trees (05C05) Deterministic network models in operations research (90B10) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Combinatorial aspects of block designs (05B05) Signed and weighted graphs (05C22) Graph designs and isomorphic decomposition (05C51)

Cites Work

• Combinatorial optimization. Theory and algorithms.
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Safe set problem on graphs
• Network majority on tree topological network
• Safe sets, network majority on weighted trees
• Safe sets in graphs: graph classes and structural parameters
• On the weighted safe set problem on paths and cycles

Cited In (8)

• Safe sets and in-dominating sets in digraphs
• On the connected safe number of some classes of graphs
• Stable structure on safe set problems in vertex-weighted graphs
• A combinatorial branch and bound for the safe set problem
• Parameterized complexity of safe set
• On the weighted safe set problem on paths and cycles
• Models and algorithms for the weighted safe set problem
• Safe sets, network majority on weighted trees

This page was built for publication: Approximating connected safe sets in weighted trees

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