Complexity of Steiner tree in split graphs -- dichotomy results

DOI10.1007/978-3-319-29221-2_27MaRDI QIDQ2795958zbMATH OpenOpenAlexFDO

Authors Madhu Illuri, P. Renjith, N. Sadagopan

Publication date 23 March 2016

Published in Algorithms and Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1511.01668

Mathematics Subject Classification ID

Trees (05C05) Connectivity (05C40) Analysis of algorithms and problem complexity (68Q25)

Abstract: Given a connected graph $G$ and a terminal set $RsubseteqV(G)$, {em Steiner tree} asks for a tree that includes all of $R$ with at most $r$ edges for some integer $rgeq0$. It is known from [ND12,Garey et. al cite{steinernpc}] that Steiner tree is NP-complete in general graphs. {em Split graph} is a graph which can be partitioned into a clique and an independent set. K. White et. al cite{white} has established that Steiner tree in split graphs is NP-complete. In this paper, we present an interesting dichotomy: we show that Steiner tree on $K_{1,4}$-free split graphs is polynomial-time solvable, whereas, Steiner tree on $K_{1,5}$-free split graphs is NP-complete. We investigate $K_{1,4}$-free and $K_{1,3}$-free (also known as claw-free) split graphs from a structural perspective. Further, using our structural study, we present polynomial-time algorithms for Steiner tree in $K_{1,4}$-free and $K_{1,3}$-free split graphs. Although, polynomial-time solvability of $K_{1,3}$-free split graphs is implied from $K_{1,4}$-free split graphs, we wish to highlight our structural observations on $K_{1,3}$-free split graphs which may be used in other combinatorial problems.

Recommendations

• The Steiner tree in \(K_{1,r}\)-free split graphs -- a dichotomy
• Steiner trees for hereditary graph classes: a treewidth perspective
• Parameterized complexity dichotomy for \textsc{Steiner Multicut}
• On the computational difficulty of the terminal connection problem
• Steiner tree in \(k\)-star caterpillar convex bipartite graphs: a dichotomy

Cites work

• A linear time recognition algorithm for proper interval graphs
• A simple algorithm to find Hamiltonian cycles in proper interval graphs
• Finding Hamiltonian circuits in interval graphs
• Hamiltonian circuits in interval graph generalizations
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2119644 (Why is no real title available?)
• Incompressibility through Colors and IDs
• Introduction to algorithms.
• Linear-time certifying algorithms for the path cover and Hamiltonian cycle problems on interval graphs
• On the history of the Euclidean Steiner tree problem
• Parameterized Complexity of Directed Steiner Tree on Sparse Graphs
• Saving an epsilon: a 2-approximation for the k-MST problem in graphs
• Steiner tree problems in telecommunications
• Steiner trees, connected domination and strongly chordal graphs
• Steiner trees, partial 2–trees, and minimum IFI networks
• The Complexity of Computing Steiner Minimal Trees
• The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
• The Rectilinear Steiner Tree Problem is NP-Complete
• The steiner problem in graphs

Cited in

(9)

• On the algorithmic aspects of strong subcoloring
• Steiner trees for hereditary graph classes
• Steiner tree in \(k\)-star caterpillar convex bipartite graphs: a dichotomy
• The Steiner tree in \(K_{1,r}\)-free split graphs -- a dichotomy
• Hamiltonicity in Split Graphs - A Dichotomy
• scientific article; zbMATH DE number 3963856 (Why is no real title available?)
• Vertex deletion on split graphs: beyond 4-hitting set
• On the computational difficulty of the terminal connection problem
• On convexity in split graphs: complexity of Steiner tree and domination

This page was built for publication: Complexity of Steiner tree in split graphs -- dichotomy results

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2795958)