Computing Forest Degree Realizations with Minimum Cardinality Domination
Amotz Bar-Noy, Omri Kosary, David Peleg, Dror Rawitz
In the Degree Realization problem with respect to a family $\mathcal{P}$ of graphs the input is a non-increasing sequence $d = (d_1,\ldots,d_n)$ of positive integers, and the goal is to decide whether there exists a simple undirected graph $G \in \mathcal{P}$, whose degrees correspond to $d$, i.e., such that $deg(G) = d$. In this paper we consider the version of Degree Realization in which the realization is required to be a forest (i.e., $\mathcal{P}$ is the family of forests). We consider \emph{optimized} Degree Realization in which the goal is to obtain a realization that minimizes an objective function $f$. That is, the goal is to find a realization $G$ that minimizes $f(G)$ among the realizations of the given input sequence. More specifically, we focus on the following functions: the size of an optimal \emph{vertex cover} and the size of an optimal \emph{dominating set}. We also consider the \emph{total} and \emph{paired} versions of both Min Vertex Cover and Min Dominating Set. We provide characterizations and linear time realization algorithms for all the above-mentioned problems. Since Min Paired Vertex Cover is closely related to Min Edge Dominating Set, our results for Degree Realization with respect to the former extend to the latter.
尚无 AI 解读，展示原文摘要