Partial vertex covers and the complexity of some problems concerning static and dynamic monopolies
share
Let G be a graph and τ be an assignment of nonnegative integer thresholds to the vertices of G. Denote the average of thresholds in τ by τ̅. A subset of vertices D is said to be a τ-dynamic monopoly, if V(G) can be partitioned into subsets D_0, D_1, ..., D_k such that D_0=D and for any i∈{0, ..., k-1}, each vertex v in D_i+1 has at least τ(v) neighbors in D_0∪...∪ D_i. Denote the size of smallest τ-dynamic monopoly by dyn_τ(G). Also a subset of vertices M is said to be a τ-static monopoly (or simply τ-monopoly) if any vertex v∈ V(G)∖ M has at least τ(v) neighbors in M. Denote the size of smallest τ-monopoly by mon_τ(G). For a given positive number t, denote by Sdyn_t(G) (resp. Smon_t(G)), the minimum dyn_τ(G) (resp. mon_τ(G)) among all threshold assignments τ with τ≥ t. In this paper we consider the concept of partial vertex cover as follows. Let G=(V, E) be a graph and t be any positive integer. A subset S⊆ V is said to be a t-partial vertex cover of G, if S covers at least t edges of G. Denote the smallest size of a t-partial vertex cover of G by Pβ_t(G). Let ρ, 0<ρ<1 be any fixed number and G be a given bipartite graph with m edges. We first prove that to determine the smallest cardinality of a set S⊆ V(G) such that S covers at least ρ m edges of G, is an NP-hard problem. Then we prove that for any constant t, Sdyn_t(G)=Pβ_nt-m(G) and Smon_t(G)=Pβ_nt/2(G), where n and m are the order and size of G, respectively.
READ FULL TEXT