For a graph G = (V, E), a set S ⊆ V is a dominating set for G, if for each v ∈ V , either v ∈ S, or a neighbor of v in G is in S. The Dominating Set problem takes as input a graph G = (V, E) and an integer k, and the objective is to test if there is a dominating set of size at most k in G.
The Dominating Set problem is a classical NP-hard problem, which together with its variants, is a well-studied problem in Computer Science. A variant of the Dominating Set that is of particular
interest to us, is the one where we have an additional constraint that the number of neighbors in the closed neighborhood that a vertex has in a dominating set is bounded by a given integer as input.
As Dominating Set is a notoriously hard problem in itself, so naturally, the above condition does not make the problem any easier. The above variant has been studied in the literature, and several hardness results are known for it. We remove the size requirement of the dominating set that we are seeking, and attempt to study the complexity variation for such a simplification. We call this version of the Dominating Set problem as Minimum Membership Dominating Set (MMDS, for short). For a graph G = (V, E), a vertex u ∈ V and a set S ⊆ V , the membership of u in S is
M(u, S) = | N[u]∩S |. Given a graph G = (V, E) and an integer k, the MMDS problem seeks to find a dominating set S ⊆ V of G such that for each v ∈ V , | N[v]∩S | is at most k. We investigate the parameterized complexity of the problem and obtain the following results:
1. W[1]-hardness of the problem parameterized by the pathwidth (and thus, treewidth) of the
input graph.
2. W[1]-hardness parameterized by k on split graphs.
3. An algorithm running in time 2^O(vc)|V |^O(1), where vc is the size of a minimum-sized vertex cover of the input graph.
4. An ETH-based lower bound showing that the algorithm mentioned in the previous item is optimal.
Minimum Membership Hitting Set(MMHS) is a problem in similar lines of MMDS which has been studied in literature. We take a special case of MMHS namely Exact Hitting Set. Given a set system X = {U, S}, where U is a set of elements and S is a set of subsets of U, an exact hitting set U
is a subset of U such that each subset in S contains exactly one element in U. We refer to a set system as exactly hittable if it has an exact hitting set. We study interval graphs which have
intersection models that are exactly hittable and refer to these interval graphs as exactly hittable
interval graphs (EHIG). We present a forbidden structure characterization for EHIG. We also
show that the class of proper interval graphs is a strict subclass of EHIG.