Steiner tree in k-star caterpillar convex bipartite graphs: a dichotomy

D. H. Aneesh (), A. Mohanapriya (), P. Renjith () and N. Sadagopan ()
Additional contact information
D. H. Aneesh: Indian Institute of Information Technology, Design and Manufacturing, Kancheepuram
A. Mohanapriya: Indian Institute of Information Technology, Design and Manufacturing, Kancheepuram
P. Renjith: Indian Institute of Information Technology, Design and Manufacturing, Kurnool
N. Sadagopan: Indian Institute of Information Technology, Design and Manufacturing, Kancheepuram

Journal of Combinatorial Optimization, 2022, vol. 44, issue 2, No 16, 1247 pages

Abstract: Abstract A bipartite graph G(X, Y) whose vertex set is partitioned into X and Y is a convex bipartite graph, if there is an ordering of $$X=(x_1,\ldots ,x_m)$$ X = ( x 1 , … , x m ) such that for all $$y \in Y$$ y ∈ Y , $$N_G(y)$$ N G ( y ) is consecutive with respect to the ordering of X, and G is said to have convexity with respect to X. A k-star caterpillar is a tree with a collection of stars with each star having k vertices of degree one whose roots are joined by a path. For a bipartite graph with partitions X and Y, we associate a k-star caterpillar on X such that for each vertex in Y, its neighborhood induces a tree. The minimum Steiner tree problem (STREE) is defined as follows: given a connected graph $$G=(V,E)$$ G = ( V , E ) and a subset of vertices $$R \subseteq V(G)$$ R ⊆ V ( G ) , the objective is to find a minimum cardinality set $$S \subseteq V(G)$$ S ⊆ V ( G ) such that the set $$R \cup S$$ R ∪ S induces a connected subgraph. In this paper, we present the following dichotomy result: we show that STREE is NP-complete for 1-star caterpillar convex bipartite graphs and polynomial-time solvable for 0-star caterpillar convex bipartite graphs (also known as convex bipartite graphs). We also strengthen the well-known result of Müller and Brandstädt (Theoret Comput Sci 53(2-3):257-265, 1987), which says STREE in chordal bipartite graphs is NP-complete (reduction instances are 3-star caterpillar convex bipartite graphs). As an application, we use our STREE results to solve: (i) the classical dominating set problem in convex bipartite graphs, (ii) STREE on interval graphs, linear time.

Keywords: k-star caterpillar convex bipartite graphs; Steiner tree; Chordal bipartite graphs; Convex bipartite graphs (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-022-00884-9 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:44:y:2022:i:2:d:10.1007_s10878-022-00884-9

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

DOI: 10.1007/s10878-022-00884-9

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 ().