On convexity in split graphs: complexity of Steiner tree and domination

A. Mohanapriya (), P. Renjith () and N. Sadagopan ()
Additional contact information
A. Mohanapriya: Indian Institute of Information Technology, Design and Manufacturing
P. Renjith: National Institute of Technology
N. Sadagopan: Indian Institute of Information Technology, Design and Manufacturing

Journal of Combinatorial Optimization, 2024, vol. 47, issue 2, No 7, 33 pages

Abstract: Abstract Given a graph G with a terminal set $$R \subseteq V(G)$$ R ⊆ V ( G ) , the Steiner tree problem (STREE) asks for a set $$S\subseteq V(G) {\setminus } R$$ S ⊆ V ( G ) \ R such that the graph induced on $$S\cup R$$ 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 White et al. (Networks 15(1):109–124, 1985). 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. 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, 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)k^{d-1}+k,~k=|S|$$ ( 2 d - 1 ) k d - 1 + k , k = | S | .

Keywords: Steiner tree; Domination; Split graphs; Tree-convex; Circular-convex split graphs; Parameterized complexity (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-024-01105-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:47:y:2024:i:2:d:10.1007_s10878-024-01105-1

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-024-01105-1

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().