On Convexity in Split graphs Complexity of Steiner tree and Domination A Mohanapriya1 P Renjith2 and N Sadagopan1
2025-05-02
0
0
767.89KB
25 页
10玖币
侵权投诉
On Convexity in Split graphs: Complexity of Steiner tree and
Domination ???
A Mohanapriya1, P Renjith2, and N Sadagopan1
1Indian Institute of Information Technology, Design and Manufacturing, Kancheepuram, Chennai.
2National Institute of Technology, Calicut
coe19d003@iiitdm.ac.in, renjith@nitc.ac.in, sadagopan@iiitdm.ac.in
Abstract.
Given a graph
G
with a terminal set
R⊆V
(
G
), the Steiner tree problem (STREE) asks
for a set
S⊆V
(
G
)
\R
such that the graph induced on
S∪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 [1]. 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 [2], 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
⊆
DTIME
nO(log log n)
. When the input is restricted to split graphs, we show that
the minimum dominating set problem has 2
−1
|I|
-approximation algorithm that runs in polynomial
time. Finally, from the parameterized perspective with solution size being the parameter, we show that
the Steiner tree problem on split graphs is
W
[2]-hard, whereas when the parameter is treewidth and
the solution size, we show that the problem is fixed-parameter tractable, and if the parameter is the
solution size and the maximum degree of
I
(
d
), then we show that the Steiner tree problem on split
graphs has a kernel of size at most (2d−1)kd−1+k, k =|S|.
Keywords:
Steiner tree, Domination, Split graphs, Tree-convex, Circular-convex split graphs, Approxi-
mation algorithms, Parameterized complexity.
1 Introduction
The classical complexity of the Steiner tree problem (STREE), the dominating set problem (DS), and their
variants for different classes of graphs have been well studied. Given a graph
G
with a terminal set
R⊆V
(
G
),
STREE asks for a set
S⊆V
(
G
)
\R
such that the graph induced on
S∪R
is connected. In the literature,
the set
S
is referred to as the Steiner set. The objective is to minimize the number of vertices in
S
. STREE is
NP-complete for general graphs, chordal bipartite graphs [3], and split graphs [1] whose vertex set can be
partitioned into a clique and an independent set. It is polynomial-time solvable in strongly chordal graphs [1],
series-parallel graphs [4], outerplanar graphs [5], interval graphs [6] and for graphs with fixed treewidth [7].
The only known subclass of split graphs where STREE is polynomial-time solvable is the class of threshold
graphs. Interestingly the results of [8] strengthen the result of [1] by providing a dichotomy result which says
that STREE is polynomial-time solvable in
K1,4
-free split graphs, whereas in
K1,5
-free split graphs, STREE
is NP-complete. In this paper, we focus on new subclasses of split graphs and study the tractability versus
??
A preliminary version of this paper appeared in the proceedings of
8th
International conference, CALDAM 2022,
Lecture Notes in Computer Science, vol. 13179, pp. 128-139, 2022
?This work is partially supported by the DST-ECRA Project— ECR/2017/001442.
arXiv:2210.02288v1 [cs.CC] 5 Oct 2022
intractability status (P vs NPC) of STREE in those subclasses of split graphs.
It is important to highlight that many problems that are NP-complete on bipartite graphs become polynomial-
time solvable when a linear ordering is imposed on one of the partitions. Such graphs are known as convex
bipartite graphs in the literature [9
–
11]. For example, DS is NP-complete on bipartite graphs, whereas
it is polynomial-time solvable in convex bipartite graphs [9]. A bipartite graph
G
= (
X, Y
) is said to be
tree-convex if there is a tree (imaginary tree) on
X
such that the neighborhood of each
y
in
Y
is a subtree in
X
.
Apart from linear ordering (path-convex ordering), tree-convex ordering, comb-convex ordering, star-convex
ordering, triad-convex ordering, and circular-convex ordering on bipartite graphs have been considered in
the literature [12
–
14]. Further, the convex ordering on bipartite graphs yielded many interesting algorithmic
results for STREE, DS, Hamiltonicity, and its variants [6, 11, 12]. Similarly, the feedback vertex set problem
(FVS) is NP-complete on star-convex bipartite graphs, and comb-convex bipartite graphs, whereas it is
polynomial-time solvable on convex bipartite graphs [11]. Thus, the convex ordering on bipartite graphs
reinforces the borderline separating P-versus-NPC instances of many classical combinatorial problems.
Imposing the property convexity on bipartite graphs is a promising direction for further research because many
problems that are NP-complete on bipartite graphs become polynomial-time solvable on convex bipartite
graphs. Further, some of the NP-hard reductions restricted to bipartite graphs can be reinforced further by
introducing convex properties such as star, comb, tree, etc., For example, Hamiltonian cycle and Hamiltonian
path are NP-hard on star-convex bipartite graphs [11]. While convexity in bipartite graphs seems to be a
promising direction in strengthening the existing classical hardness result or in discovering a polynomial-time
algorithm, we wish to investigate this line of research for STREE and DS problems restricted to split graphs.
Since the tractability versus intractability status of many combinatorial problems on bipartite graphs (graphs
with two partitions satisfying some structural properties) can be investigated with the help of convex ordering
on bipartite graphs, it is natural to explore this line of study on graphs having two partitions satisfying
some structural properties. A natural choice after bipartite graphs is the class of split graphs. We wish to
extend this line of study to split graphs by considering convex ordering with respect to the clique part and
independent set part. To the best of our knowledge, this paper makes the first attempt in introducing convex
properties on split graphs for STREE and DS. We believe that our results shall strengthen the result of [1],
and also we discover a dichotomy similar to [8]. As part of this paper, we consider the following convex
properties; path-convex, star-convex, comb-convex, tree-convex, and circular-convex split graphs. Henceforth,
we refer to split graphs satisfying some convex properties (path, star, comb, triad, tree, and circular) as
convex split graphs.
Recently in [6], a framework for STREE and DS was developed, and as per [8], the classical complexity of
STREE is the same as the classical complexity of DS for split graphs. We attempt a similar framework for
STREE and DS, and its variants are restricted to convex split graphs.
For tree-convex and its subclasses, and circular-convex split graphs, the computational complexity of the
following graph problems is studied in this paper.
1. The Steiner tree problem (STREE).
Instance: A graph G, a terminal set R⊆V(G), and a positive integer k.
Question: Does there exist a set S⊆V(G)\Rsuch that |S| ≤ k, and G[S∪R] is connected ?
2. The Dominating set problem (DS).
Instance: A graph G, and a positive integer k.
Question: Does Gadmit a dominating set of size at most k?
3. The Connected Dominating set problem (CDS).
Instance: A graph G, and a positive integer k.
Question: Does Gadmit a connected dominating set of size at most k?
4. The Total Dominating set problem (TDS).
Instance: A graph G, and a positive integer k.
Question: Does Gadmit a total dominating set of size at most k?
Figure 1 illustrates the hierarchical relationship on various convex split graphs. An interesting theoretical
question is
2
Split graphs
convexity on K
convexity on I
Chordal-convex
Circular-convex
Tree-convex
Star-convex
Triad-convex
Comb-convex
Path-convex
Chordal-convex
Circular-convex
Tree-convex
Star-convex
Triad-convex
Comb-convex
Path-convex
Fig. 1: The Hierarchical relationship among subclasses of convex split graphs
-What is the boundary between the tractability and intractability of STREE in split graphs when convex
ordering is imposed on one of the partitions ?
In this paper, we answer this question by imposing a convex ordering on clique or independent set. In
particular, we show that STREE is polynomial-time solvable for tree-convex split graphs with convexity on
K
,
and is NP-complete for star-convex and comb-convex split graphs, and thus for tree-convex split graphs with
convexity on
I
. Further, we investigate path, triad, and circular-convex properties, and show that STREE is
polynomial-time solvable for triad, path-convex split graphs with convexity on
I
, circular-convex split graphs
with convexity on I, and circular-convex split graphs with convexity on K. We then ask
-For which convex property on split graphs with convexity on K, STREE is intractable?
In this paper, we show that if the convex property is chordality, then STREE is NP-complete for chordal-
convex split graphs with convexity on K.
To deal with computationally intractable problems, the practical approach is to use approximation al-
gorithms or parameterized algorithms. Algorithms that output near-optimal solutions in polynomial time are
precisely the class of approximation algorithms. It is known [15], that DS has an approximation algorithm
with approximation ratio (1 +
ln n
) on general graphs. On the negative side, DS does not admit (1
−
)
ln n
on
general graphs, for any
>
0 unless NP
⊆
DTIME (
nO(log log n)
) [2]. In this paper, restricted to split graphs,
we prove that DS exhibits 2 −1
|I|-approximation algorithm.
For decision problems with input size
n
, and a parameter
k
(which can be a tuple of parameters), the goal
of parameterized algorithms is to obtain an algorithm with runtime
f
(
k
)
nO(1)
, where
f
is a function of
k
and independent of
n
. Problems having such algorithms are Fixed-Parameter Tractable (FPT). There is a
hierarchy of intractable parameterized problem classes above FPT [16], they are:
FPT ⊆M[1] ⊆W[1] ⊆M[2] ⊆W[2] ⊆. . . ⊆W[P] ⊆XP.
In [17] it is shown that STREE in general graphs is in FPT if the parameter is the size of the terminal set. It
is known [18] that STREE in general graphs with parameter
|S|
(solution size) is W[2]-hard. We strengthen
the result of [18] by proving that the Steiner tree problem on split graphs is still W[2]-hard with the parameter
being the solution size. Further, the parameterized Steiner tree problem is in FPT, when parameters are
(i) the solution size and the treewidth,
(ii) the solution size and the maximum degree of I.
We reiterate that our FPT results for STREE are true for DS as well, restricted to split graphs.
This paper is structured as follows: In Section 2, we analyze the classical complexity of STREE on convex
3
split graphs and present dichotomy results for convex split graphs with convexity on
I
as well as for convex
split graphs with convexity on
K
. We also identify polynomial-time solvable instances and FPT instances
of STREE on star-convex split graphs with convexity on
I
which we present in Section 2.1.1, and we also
prove that the Steiner tree problem with the parameter being solution size and backbone path length on
comb-convex split graphs is in XP in Section 2.1.2. We then present results on the dominating set problem
and its variants on convex split graphs in Section 3. In Section 4, we present parameterized hardness of
STREE on split graphs, and we also identified parameters for which parameterized version of STREE on split
graphs becomes fixed-parameter tractable. Further, we present 2
−1
I
-approximation algorithm for domination
on split graphs in Section 5.
Graph preliminaries:
In this paper, we consider connected, undirected, unweighted, and simple graphs.
For a graph
G
,
V
(
G
) denotes the vertex set, and
E
(
G
) represents the edge set. For a set
S⊆V
(
G
),
G
[
S
]
denotes the subgraph of
G
induced on the vertex set
S
. The open neighborhood of a vertex
v
in
G
is
NG
(
v
) =
{u| {u, v} ∈ E
(
G
)
}
and the closed neighborhood of
v
in
G
is
NG
[
v
] =
{v} ∪ NG
(
v
). The degree
of vertex
v
in
G
is
dG
(
v
) =
|NG
(
v
)
|
. A split graph
G
is a graph in which
V
(
G
) is partitioned into two
sets; a clique
K
and an independent set
I
. In a split graph, for each vertex
u
in
K
,
NI
G
(
u
) =
NG
(
u
)
∩I
,
dI
G
(
u
) =
|NI
G
(
u
)
|
, and for each vertex
v
in
I
,
NK
G
(
v
) =
NG
(
v
)
∩K
,
dK
G
(
v
) =
|NK
G
(
v
)
|
. For each vertex
u
in
K
,
NI
G
[
u
]=(
NG
(
u
)
∩I
)
∪ {u}
, and for each vertex
v
in
I
,
NK
G
[
v
]=(
NG
(
v
)
∩K
)
∪ {v}
. For a split graph
G
,
∆I
G
=
max{dI
G
(
u
)
}, u ∈K
and
∆K
G
=
max{dK
G
(
v
)
}, v ∈I
. For a set
S
,
G−S
denotes the graph induced on
V(G)\S. For A={x1, . . . , xp}, max(x1, . . . , xp) is xp; the vertex having largest index.
A tree is a connected acyclic graph. A path is a tree
T
with
V
(
T
) =
{v1, . . . , vn}, n ≥
1 and
E
(
T
) =
{{vi, vi+1,
1
≤i≤n−
1
}}
. A cycle is a graph
C
with
V
(
C
) =
{v1, . . . , vn}, n ≥
3 and
E
(
C
) =
{{vi, vi+1,
1
≤i≤n−
1
}} ∪ {{vn, v1}}
. We consider three special kinds of trees, namely, star, comb,
and triad. A star is a tree
T
with
V
(
T
) =
{v1, . . . , vn}, n ≥
2 and
E
(
T
) =
{{v1, vi} |
2
≤i≤n}
. The
root of
T
is
v1
and
v2, . . . , vn
are the pendant vertices in
T
. A comb is a tree
T
with
V
(
T
) =
{v1, . . . , v2n}
and
E
(
T
) =
{{vi, vn+i} |
1
≤i≤n} ∪ {{vi, vi+1} |
1
≤i<n}
. The path on
{v1, v2, . . . , vn}, n ≥
1 is the
backbone of the comb, and
{vn+1, vn+2, . . . , v2n}, n ≥
1 are the teeth of the comb. A triad is a tree
T
with
V
(
T
) =
{u, v1, . . . , vp, w1, . . . , wq, x1, . . . , xr}, p ≥
2
, q ≥
2
, r ≥
2 and
E
(
T
) =
{{u, v1},{u, w1},{u, x1}} ∪
∪{{vi, vi+1} | 1≤i≤p−1} ∪ {{wi, wi+1} | 1≤i≤q−1} ∪ {{xi, xi+1} | 1≤i≤r−1}.
Triad
Star
Comb
v1
v2
v3
v4
v5
v6
v1
v2
v3
v4
v5
v6
v7
v8
u
v1
v2
v3
v4
x1
x2
x3
w1
w2
Fig. 2: An example; Star, Comb, and Triad
Definition 1.
A split graph
G
is called
π
-convex with convexity on
K
if there is an associated structure
π
on Ksuch that for each v∈I,NG(v)induces a connected subgraph in π.
Definition 2.
A split graph
G
is called
π
-convex with convexity on
I
if there is an associated structure
π
on
Isuch that for each v∈K,NI
G(v)induces a connected subgraph in π.
In general
π
can be any arbitrary structure. In this paper, We consider the following structures for
π
; ”tree”,
”star”, ”comb”, ”path”, ”triad”, and ”cycle”. Note that the structure πin Gis an imaginary structure.
In the rest of the sections, we solve STREE for the case
R
=
I
and it is sufficient to look at this case and all
other cases can be solved using
R
=
I
as a black box. In Section 6, we present a transformation using which
we can solve other cases.
4
2 The classical complexity of STREE
In Section 2.1, we analyze the classical complexity of STREE on split graphs with convexity on
I
, and in
Section 2.2, we analyze the classical complexity of STREE on split graphs with convexity on K.
2.1 STREE in split graphs with convexity on I
When we refer to convex split graphs in this section, we refer to convex split graphs with convexity on
I
. For
STREE on split graphs with convexity on I, we establish hardness results for star-convex and comb-convex
split graphs, and polynomial-time algorithms for path-convex, triad-convex, and circular-convex split graphs.
2.1.1 Star-convex split graphs
In this section, we establish a classical hardness of STREE on star-convex split graphs by presenting a
polynomial-time reduction from the Exact-3-Cover problem to STREE on star-convex split graphs.
The decision version of Exact-3-Cover problem (X3C) is defined below:
X3C (X, C)
Instance:
A finite set
X
=
{x1, . . . , x3q}
and a collection
C
=
{C1, C2, . . . , Cm}
of 3-element subsets of
X.
Question:
Is there a subcollection
C0⊆ C
such that for every
x∈X
,
x
belongs to exactly one member
of C0(that is, C0partitions X) ?
The decision version of Steiner tree problem (STREE) is defined below:
STREE (G, R, k)
Instance: A graph G, a terminal set R⊆V(G), and a positive integer k.
Question: Is there a set S⊆V(G)\Rsuch that |S| ≤ k, and G[S∪R] is connected ?
Theorem 1. For star-convex split graphs, STREE is NP-complete.
Proof. STREE is in NP:
Given a star-convex split graph
G
and a certificate
S⊆V
(
G
), we show that
there exists a deterministic polynomial-time algorithm for verifying the validity of
S
. Note that the standard
Breadth First Search (BFS) algorithm can be used to check whether
G
[
S∪R
] is connected. It is easy to
check whether
|S| ≤ k
. The certificate verification can be done in
O
(
|V
(
G
)
|
+
|E
(
G
)
|
). Thus, we conclude
that STREE is in NP.
STREE is NP-Hard:
It is known [19] that X3C is NP-complete. X3C can be reduced in polynomial time
to STREE on star-convex split graphs using the following reduction. We map an instance (
X, C
) of X3C
to the corresponding instance (
G, R, k
) of STREE as follows:
V
(
G
) =
V1∪V2
,
V1
=
{ci|
1
≤i≤m}
,
V2
=
{x1, x2, . . . , x3q, x3q+1}
,
E
(
G
) =
{{ci, xj} | xj∈Ci,
1
≤j≤
3
q,
1
≤i≤m} ∪ {{x3q+1, ci} |
1
≤i≤
m} ∪ {{ci, cj} |
1
≤i≤j≤m}
. Let
R
=
V2
,
k
=
q
. Note that
G
is a split graph with
V1
being a clique and
V2
being an independent set. Now we show that
G
is a star-convex split graph by defining an imaginary star
Ton V2:
Let V(T) = V2and E(T) = {{x3q+1, xi} | 1≤i≤3q}. We see that x3q+1 is the root of the star T.
An illustration for X3C with
X
=
{x1, x2, x3, x4, x5, x6}
and
C
=
{C1
=
{x1, x2, x3}, C2
=
{x2, x3, x4}, C3
=
{x1, x2, x5}, C4
=
{x2, x5, x6}, C5
=
{x1, x5, x6}}
, and the corresponding graph
G
with
R
=
I
,
k
= 2 is shown
in Figure 3. Note that the imaginary star on Iwith the root x7is also shown in Figure 3. For this instance
the solution to X3C is C0={C2, C5}, and the corresponding solution for graph Gis S={c2, c5}.
5
摘要：
展开>>
收起<<
OnConvexityinSplitgraphs:ComplexityofSteinertreeandDomination???AMohanapriya1,PRenjith2,andNSadagopan11IndianInstituteofInformationTechnology,DesignandManufacturing,Kancheepuram,Chennai.2NationalInstituteofTechnology,Calicutcoe19d003@iiitdm.ac.in,renjith@nitc.ac.in,sadagopan@iiitdm.ac.inAbstract.Giv...
声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！
相关推荐
-
曲一线系列初中《5中考3年模拟》2023专题解释全国道德与法治资料包05专题五 走进社会生活 遵守社会规则VIP免费
2024-11-21 1 -
曲一线系列初中《5中考3年模拟》2023专题解释全国道德与法治资料包05专题五 走进社会生活 遵守社会规则VIP免费
2024-11-21 2 -
曲一线系列初中《5中考3年模拟》2023专题解释全国道德与法治资料包03专题三 青春时光 做情绪情感的主人VIP免费
2024-11-21 2 -
曲一线系列初中《5中考3年模拟》2023专题解释全国道德与法治资料包03专题三 青春时光 做情绪情感的主人VIP免费
2024-11-21 3 -
曲一线系列初中《5中考3年模拟》2023专题解释全国道德与法治资料包02专题二 友谊的天空 师长情谊VIP免费
2024-11-21 1 -
曲一线系列初中《5中考3年模拟》2023专题解释全国道德与法治资料包02专题二 友谊的天空 师长情谊VIP免费
2024-11-21 4 -
曲一线系列初中《5中考3年模拟》2023专题解释全国道德与法治资料包01专题一 成长的节拍 生命的思考VIP免费
2024-11-21 1 -
曲一线系列初中《5中考3年模拟》2023专题解释全国道德与法治资料包01专题一 成长的节拍 生命的思考VIP免费
2024-11-21 2 -
曲一线系列初中《5中考3年模拟》2023专题解释全国道德与法治资料包《53中考》全国道德与法治资料包VIP免费
2024-11-21 5 -
曲一线系列初中《5中考3年模拟》2023专题解释全国道德与法治资料包07专题七 坚持宪法至上 崇尚法治精神VIP免费
2024-11-21 2
分类：图书资源
价格：10玖币
属性：25 页
大小：767.89KB
格式：PDF
时间：2025-05-02
作者详情
相关内容
-
2025年小学实践活动教案：（微课制作用）课件
分类：中学教育
时间：2025-06-08
标签：无
格式：PPT
价格：10 玖币
-
2025年教学资料：【通用版】一年级数学重点难点知识总结
分类：中学教育
时间：2025-06-08
标签：无
格式：PDF
价格：10 玖币
-
2025年教学资料：小学生心理健康教育主题班会ppt课件
分类：中学教育
时间：2025-06-08
标签：无
格式：PPTX
价格：10 玖币
-
2013年广东省地理中考试题无答案
分类：中学教育
时间：2025-06-08
标签：无
格式：DOC
价格：10 玖币
-
河南省2020年中考道德与法治试题
分类：中学教育
时间：2025-06-08
标签：无
格式：DOC
价格：10 玖币
渝公网安备50010702506394
