A connected bipartite graph has s(G,w)=cs(G,w) for every positive weight function w exactly when it is an even cycle, a double star, a book graph, K3,3 minus an edge, or one of the explicitly listed D or D* graph families.
Parameterized Complexity of Safe Set
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
In this paper we study the problem of finding a small safe set $S$ in a graph $G$, i.e. a non-empty set of vertices such that no connected component of $G[S]$ is adjacent to a larger component in $G - S$. We enhance our understanding of the problem from the viewpoint of parameterized complexity by showing that (1) the problem is W[2]-hard when parameterized by the pathwidth $pw$ and cannot be solved in time $n^{o(pw)}$ unless the ETH is false, (2) it admits no polynomial kernel parameterized by the vertex cover number $vc$ unless $\mathrm{PH} = \Sigma^{\mathrm{p}}_{3}$, but (3) it is fixed-parameter tractable (FPT) when parameterized by the neighborhood diversity $nd$, and (4) it can be solved in time $n^{f(cw)}$ for some double exponential function $f$ where $cw$ is the clique-width. We also present (5) a faster FPT algorithm when parameterized by solution size.
citation-role summary
background 1
citation-polarity summary
fields
math.CO 1years
2019 1verdicts
ACCEPT 1roles
background 1polarities
unclear 1representative citing papers
citing papers explorer
-
Stable structure on safe set problems in vertex-weighted graphs
A connected bipartite graph has s(G,w)=cs(G,w) for every positive weight function w exactly when it is an even cycle, a double star, a book graph, K3,3 minus an edge, or one of the explicitly listed D or D* graph families.