On Spanning Trees Constraints Variants and Generalizations

Abstract

The objective of this thesis is to study a constraint, a generalization and variants of the spanning tree problem. The research spectrum includes structural and algorithmic views of the problems and dichotomy results. The following are some of the main results presented in this thesis and we highlight them under three heads. newlineDichotomy results in split graphs newlineThe Steiner tree problem is a classical combinatorial optimization problem which is a generalization of the spanning tree problem. We study the Steiner tree problem in split graphs. We present a structural characterization of K1;3-free split graphs and K1;4-free split graphs. Further, using the structural characterization, we present bounds on the Steiner set in K1;4-free split graphs. Subsequently, we obtain characterizations of K1;4-free split graphs for possible Steiner set sizes. We present a polynomial-time algorithm for solving the Steiner tree problem in K1;4-free split graphs. K. White et.al. [4] have shown a polynomial-time reduction from the Exact-3-Cover problem to the Steiner tree problem in split graphs. We have done a microscopic study to show that the Steiner tree problem is NP-complete in K1;5-free split graphs. Thus we obtain a dichotomy result for the problem in subclasses of split graphs. newlineSubsequently, we study the Hamiltonian cycle problem, a variant of the spanning tree problem and the Hamiltonian path problem, a constrained spanning tree problem in the context of split graphs. We present a similar dichotomy for the Hamiltonian cycle problem and the Hamiltonian path problem in subclasses of split graphs. That is, the Hamiltonian cycle problem and the Hamiltonian path problem are NP-complete inK1;5-free split graphs, and polynomial-time solvable in K1;4-free split graphs.