  The independent set on a graph $G=(V,E)$ is a subset of $V$ such that no two
vertices in the subset have an edge between them. The MIS problem on $G$ seeks
to identify an independent set with maximum cardinality, i.e. maximum
independent set or MIS. $V* \subseteq V$ is a vertex cover $G=(V,E)$ if every
edge in the graph is incident upon at least one vertex in $V*$. $V* \subseteq
V$ is dominating set of $G=(V,E)$ if forall $v \in V$ either $v \in V*$ or
$\exists u \in V*$ and $(u,v) \in E$. A connected dominating set, CDS, is a
dominating set that forms a single component in $G$. The MVC problem on $G$
seeks to identify a vertex cover with minimum cardinality, i.e. minimum vertex
cover or MVC. Likewise, CVC seeks a connected vertex cover (CVC) with minimum
cardinality. The problems MDS and CDS seek to identify a dominating set and a
connected dominating set respectively of minimum cardinalities. MVC, CVC, MDS,
and CDS on a general graph are known to be NP-complete. On certain classes of
graphs they can be computed in polynomial time. Such algorithms are known for
bipartite graphs, chordal graphs, cycle graphs, comparability graphs, claw-free
graphs, interval graphs and circular arc graphs for some of these problems. In
this article we introduce a new class of graphs called a layered graph and show
that if the number of vertices in a layer is $O(\log \mid V \mid)$ then MIS,
MVC, CVC, MDS and CDC can be computed in polynomial time. The restrictions that
are employed on graph classes that admit polynomial time solutions for hard
problems, e.g. lack of cycles, bipartiteness, planarity etc. are not applicable
for this class. \\ Key words: Independent set, vertex cover, dominating set,
dynamic programming, complexity, polynomial time algorithms.
