On Finding Optimal Sub-structures in Graphs

Abstract

In computer science, a problem is said to have an optimal sub-structure if an optimal solution can be constructed from optimal solutions of its sub-problems. These optimal sub-structures are computed in the classical graph-theoretic setting where the graph is a structure with a set of vertices and edges. In computational geometry, the vertex set is usually represented by a set of geometric objects like unit disks, etc., and the edge set is represented by the intersection of these geometric structures. In this thesis, three problems are investigated namely minimum discriminating codes, red-blue separation, and minimum consistent subset.

In the minimum discriminating codes problem, we handle some geometric structures like unit intervals and arbitrary intervals in $\IR$ and axis parallel unit squares in $\IR^2$. We prove the hardness of the problem in both one-dimensional and two-dimensional planes. We also propose PTAS for the unit interval case and a 2-factor approximation algorithm for the arbitrary interval case. In polynomial time we have given approximation algorithms producing constant-factor solution in $\IR^2$ with axis parallel unit square objects. We have also studied a similar problem known as the minimum identifying codes in some geometric settings.

In the red-blue separation problem, we consider a graph whose vertices are coloured red or blue. We study the computational complexity in some graph classes. We design polynomial-time algorithms when one of the coloured classes is bounded by a constant. We also give some tight bounds on the cardinality of the optimal solution.

In the minimum consistent subset problem, we work with simple graph classes like paths, caterpillars, trees, etc. For each of these graphs, we have designed optimal algorithms. We have also considered both undirected and directed versions for a few of the graphs.