论文标题
在拆分图中的凸面：施纳树的复杂性和统治
On Convexity in Split graphs: Complexity of Steiner tree and Domination
论文作者
论文摘要
给定带有终端集$ r \ subseteq v（g）$的图形$ g $，steiner树问题（stree）要求提供一个$ s \ subseteq v（g）\ setminus r $，使得在$ s \ cup cup r $上引起的图形连接。拆分图是一个可以将其划分为集团和独立集的图形。众所周知，在拆分图\ cite {white1985steiner}上，stree是np complete。为了加强这一结果，我们在其中一个分区（集团或独立集）上介绍了凸的订购，并证明stree是可解决的多项式时间，用于在集团上使用凸的树 - 孔口拆分图（$ k $）（$ k $），而stree则是在树上convex splate in convex splate on Indeppential in Ipderitional in Ipderitional in Ipdifsita in Ipperiade in Ipderitiate in Ipperiade（$ i i $ i $ i $ i $ i $ i $ i $）。我们通过建立二分法来进一步增强NP完整结果，该二分法说，对于Unerary-Tree-Convex拆分图（路径 - 串联拆分图），stree是可溶解的多项式时间，而对于二进制 - 树 - 串联拆分图（Comb-convex splater graphs），则可以溶解多项式时间。我们还表明，对于$ i $上的凸面和圆形 - 凸口拆分图，stree是可溶解的多项式时间。此外，我们表明，串可以用作拆分图上主导集问题（DS）的框架，因此，对于所有这些拆分图的子类别，stree和ds的经典复杂性（p vs npc）都是相同的。此外，重要的是要强调，在\ cite {chlebik20081264}中，错误地声称，在$（1-ε）\ ln | v（g）中，找到最低限度的统治地图的问题不能近似于$> $ time $> $ time> 0 $ time> y除非\ log n）} $。当输入仅限于拆分图时，我们表明最小统治设置问题的$ 2- \ frac {1} {| i |} $ - 在多项式时间内运行的近似算法。
Given a graph $G$ with a terminal set $R \subseteq V(G)$, the Steiner tree problem (STREE) asks for a set $S\subseteq V(G) \setminus R$ such that the graph induced on $S\cup R$ is connected. A split graph is a graph which can be partitioned into a clique and an independent set. It is known that STREE is NP-complete on split graphs \cite{white1985steiner}. To strengthen this result, we introduce convex ordering on one of the partitions (clique or independent set), and prove that STREE is polynomial-time solvable for tree-convex split graphs with convexity on clique ($K$), whereas STREE is NP-complete on tree-convex split graphs with convexity on independent set ($I$). We further strengthen our NP-complete result by establishing a dichotomy which says that for unary-tree-convex split graphs (path-convex split graphs), STREE is polynomial-time solvable, and NP-complete for binary-tree-convex split graphs (comb-convex split graphs). We also show that STREE is polynomial-time solvable for triad-convex split graphs with convexity on $I$, and circular-convex split graphs. Further, we show that STREE can be used as a framework for the dominating set problem (DS) on split graphs, and hence the classical complexity (P vs NPC) of STREE and DS is the same for all these subclasses of split graphs. Furthermore, it is important to highlight that in \cite{CHLEBIK20081264}, it is incorrectly claimed that the problem of finding a minimum dominating set on split graphs cannot be approximated within $(1-ε)\ln |V(G)|$ in polynomial-time for any $ε>0$ unless NP $\subseteq$ DTIME $n^{O(\log \log n)}$. When the input is restricted to split graphs, we show that the minimum dominating set problem has $2-\frac{1}{|I|}$-approximation algorithm that runs in polynomial time.
