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

DOI10.1007/S10878-022-00884-9MaRDI QIDQ2165280zbMATH OpenOpenAlexFDO

Authors D. H. Aneesh, Arusamy Mohanapriya, P. Renjith, N. Sadagopan

Publication date 19 August 2022

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

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

zbMATH Keywords

\(k\)-star caterpillar convex bipartite graphschordal bipartite graphsconvex bipartite graphsSteiner tree

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

Abstract: The class of $k$-star caterpillar convex bipartite graphs generalizes the class of convex bipartite graphs. 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 $k$-star caterpillar on $X$ is imaginary and if the imaginary structure is a path ($0$-star caterpillar), then it is the class of convex bipartite graphs. The minimum Steiner tree problem (STREE) is defined as follows: given a connected graph $G=(V,E)$ and a subset of vertices $RsubseteqV(G)$, the objective is to find a minimum cardinality set $SsubseteqV(G)$ such that the set $RcupS$ induces a connected subgraph. STREE is known to be NP-complete on general graphs as well as for special graph classes such as chordal graphs, bipartite graphs, and chordal bipartite graphs. The complexity of STREE in convex bipartite graphs, which is a popular subclass of chordal bipartite graphs, is open. In this paper, we introduce $k$-star caterpillar convex bipartite graphs, and 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). In cite{muller1987np}, it is shown that STREE in chordal bipartite graphs is NP-complete. A close look at the reduction instances reveal that the instances are $3$-star caterpillar convex bipartite graphs, and in this paper, we strengthen the result of cite{muller1987np}.

Recommendations

• The Steiner tree in \(K_{1,r}\)-free split graphs -- a dichotomy
• scientific article; zbMATH DE number 3963856
• Complexity of Steiner tree in split graphs -- dichotomy results
• Tree Convex Bipartite Graphs: $\mathcal{NP}$ -Complete Domination, Hamiltonicity and Treewidth
• Steiner trees, connected domination and strongly chordal graphs

Cites work

• Algorithmic graph theory and perfect graphs
• Complexity of domination, Hamiltonicity and treewidth for tree convex bipartite graphs
• Distance-Hereditary Graphs, Steiner Trees, and Connected Domination
• Domination in convex and chordal bipartite graphs
• Generation of maximum independent sets of a bipartite graph and maximum cliques of a circular-arc graph
• scientific article; zbMATH DE number 3679885 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Incompressibility through Colors and IDs
• Introduction to algorithms.
• Link-Length Minimization in Networks
• Parameterized algorithms
• Permutation graphs: Connected domination and Steiner trees
• Steiner trees, connected domination and strongly chordal graphs
• Steiner's problem in graphs and its implications
• The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
• The steiner problem in graphs
• The Steiner tree in \(K_{1,r}\)-free split graphs -- a dichotomy

Cited in

(7)

• Steiner trees in uniformly quasi-bipartite graphs.
• The Steiner tree in \(K_{1,r}\)-free split graphs -- a dichotomy
• Complexity of Steiner tree in split graphs -- dichotomy results
• P versus NPC: minimum Steiner trees in convex split graphs
• On convexity in split graphs: complexity of Steiner tree and domination
• Constrained Hitting Set and Steiner Tree in SCk and 2K2-free Graphs
• Spanning caterpillar in biconvex bipartite graphs

This page was built for publication: Steiner tree in \(k\)-star caterpillar convex bipartite graphs: a dichotomy

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