

Graphs, such as interval graphs, trapezoid graphs, and circular arc graphs Agnarsson et al. The problem is polynomially solvable for some intersection Result, for any ϵ > 0, on bipartite graphs is NP-hard (this result Planar bipartite graphs of maximum degree 3 Eto et al. The distance- d independent set (D dIS) problem, for any fixed d ≥ 3, is known to be NP-hard for bipartite graphs Chang and Nemhauser ( 1984) and The objective of the minimum distance- d dominating set (MD dDS) problem is to find a D dDS of minimum cardinality in a given graph G. A D dDS for an integer d ≥ 1 in a simple unweighted graph G = ( V, E ) is defined as a set of vertices V ′ ⊆ V such that, for each vertex u ∈ V, either (i) u ∈ V ′, or (ii) v ∈ V ′ such that, the shortest path distance between u and v is at most d. We define a generalized version of MDS problem as distance- d dominating set (D dDS) problem. The objective of MDS problem is to find a dominating set of minimum cardinality in G. The dominating set of minimum cardinality in a graph G is called the minimum dominating set (MDS) of G. In a simple unweighted graph G = ( V, E ), dominating set is defined as a set of vertices V ′ ⊆ V such that for each vertex u ∈ V, either (i) u ∈ V ′, or (ii) there exist v ∈ V ′ such that v is a neighbor of u. In fact for d = 2, the D dIS problem and MIS problem are the same. Observe that the D dIS problem is a generalization of the MIS problem and Is called as maximum distance- d independent set (MD dIS). Given unweighted graph G, the objective of the maximum distance- d independent setĬardinality in G. Of G such that the shortest path distance (i.e., the number of edges on a shortest path)īetween every pair of vertices in I is at least d. Independent set (D dIS) of an unweighted graph G = ( V, E ) is an independent set I Unweighted graph G, and such a set is called as maximum independent The maximum independent set problemĪsks to find an independent set of maximum size in a given Vertices of G is known as an independent set of G.

Given an unweighted graph G = ( V, E ), a non-empty subset of pairwise non-adjacent
