论文标题
用于本地约束的跨越树问题的统一模型
A Unifying Model for Locally Constrained Spanning Tree Problems
论文作者
论文摘要
给定图形$ g $和一个digraph $ d $，其顶点是$ g $的边缘，我们研究了找到满足$ d $施加的约束的$ g $的生成树的问题。在树上增加边缘的限制取决于其附近的$ d $。在这里，我们通过考虑到$ e（g）$上的输入函数$ \ ell $和$ u $来概括了先前研究的问题，这些功能分别在每个边缘必须满足的约束数量上给出了较低和上限。 \ texttt {g-dcst}表示产生的可行性问题，而优化问题用\ texttt {g-dcmst}表示。我们表明，即使在$ g $和$ d $的结构上，以及功能$ \ ell $和$ u $的结构，即使在强大的假设下，\ texttt {g-dcst}也是NP的完整。从积极的一面来看，我们证明了两个多项式结果，一个结果用于\ texttt {g-dcst}，另一个用于\ texttt {g-dcmst}，还给出了一个简单的指数时间算法，并证明了它在ð下是非最佳的。 Finally, we prove that other previously studied constrained spanning tree (\textsc{CST}) problems can be modeled within our framework, namely, the \textsc{Conflict CST}, the \textsc{Forcing CS, the \textsc{At Least One/All Dependency CST}, the \textsc{Maximum Degree CST}, the \textsc{Minimum Degree CST}, and the \ textsc {固定叶子最低度CST}。
Given a graph $G$ and a digraph $D$ whose vertices are the edges of $G$, we investigate the problem of finding a spanning tree of $G$ that satisfies the constraints imposed by $D$. The restrictions to add an edge in the tree depend on its neighborhood in $D$. Here, we generalize previously investigated problems by also considering as input functions $\ell$ and $u$ on $E(G)$ that give a lower and an upper bound, respectively, on the number of constraints that must be satisfied by each edge. The produced feasibility problem is denoted by \texttt{G-DCST}, while the optimization problem is denoted by \texttt{G-DCMST}. We show that \texttt{G-DCST} is NP-complete even under strong assumptions on the structures of $G$ and $D$, as well as on functions $\ell$ and $u$. On the positive side, we prove two polynomial results, one for \texttt{G-DCST} and another for \texttt{G-DCMST}, and also give a simple exponential-time algorithm along with a proof that it is asymptotically optimal under the Ð. Finally, we prove that other previously studied constrained spanning tree (\textsc{CST}) problems can be modeled within our framework, namely, the \textsc{Conflict CST}, the \textsc{Forcing CS, the \textsc{At Least One/All Dependency CST}, the \textsc{Maximum Degree CST}, the \textsc{Minimum Degree CST}, and the \textsc{Fixed-Leaves Minimum Degree CST}.
