Parameterized Complexity of Generalizations of Edge Dominating Set
摘要
The objective of this article is to propose two natural generalizations of covering edges by edges (Edge Dominating Set) and study these problems from the multivariate lens. The first is simply considering Edge Dominating Set on hypergraphs, called Hyperedge Dominating Set. Given a hypergraph \(\mathcal{H}=( \mathcal U,\mathcal{F})\) , a set \(F \subseteq \mathcal{F}\) is called a hyperedge dominating set if all hyperedges intersect with at least one hyperedge \(e \in F\) . The objective of the Hyperedge Dominating Set problem is to determine whether a hyperedge dominating set of size at most k exists. We find it quite surprising that such generalization is missing from the literature. The second extension we consider is the t-Path Edge Dominating Set problem. In this problem, the input consists of a graph G and an integer k, and the goal is to find a set \(\mathcal{P}\) of at most k paths, each of length at most t, such that for every edge in G, at least one of its endpoints belongs to the vertex set V(P) for some \(P \in \mathcal{P}\) . We show the following results and add to the literature on Edge Dominating Set.