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 <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\mathcal {H}=(\mathcal {U},\mathcal {F})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">H</mi> <mo>=</mo> <mo stretchy="false">(</mo> <mi mathvariant="script">U</mi> <mo>,</mo> <mi mathvariant="script">F</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, a set <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$F\subseteq \mathcal {F}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>F</mi> <mo>⊆</mo> <mi mathvariant="script">F</mi> </mrow> </math></EquationSource> </InlineEquation> is called a hyperedge dominating set if every hyperedge in <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\mathcal {F}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">F</mi> </math></EquationSource> </InlineEquation> intersects at least one hyperedge <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$e\in F$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>e</mi> <mo>∈</mo> <mi>F</mi> </mrow> </math></EquationSource> </InlineEquation>. 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 surprising that this natural 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 <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$\mathcal {P}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">P</mi> </math></EquationSource> </InlineEquation> of at most k paths, each on at most t vertices, such that for every edge of G, at least one of its endpoints belongs to the vertex set V(P) for some <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$P\in \mathcal {P}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>P</mi> <mo>∈</mo> <mi mathvariant="script">P</mi> </mrow> </math></EquationSource> </InlineEquation>. We show the following results and add to the literature on Edge Dominating Set.<UnorderedList Mark="Bullet"> <ItemContent> Hyperedge Dominating Set is FPT parameterized by <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$k+d$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>+</mo> <mi>d</mi> </mrow> </math></EquationSource> </InlineEquation>, where d is the maximum size of a hyperedge in the input hypergraph. </ItemContent> <ItemContent> For every fixed d, Hyperedge Dominating Set admits a polynomial kernel: the reduced hypergraph has <InlineEquation ID="IEq8"> <EquationSource Format="TEX">$\mathcal {O}((dk)^{d^2})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">O</mi> <mo stretchy="false">(</mo> <msup> <mrow> <mo stretchy="false">(</mo> <mi>d</mi> <mi>k</mi> <mo stretchy="false">)</mo> </mrow> <msup> <mi>d</mi> <mn>2</mn> </msup> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> hyperedges and total size <InlineEquation ID="IEq9"> <EquationSource Format="TEX">$\mathcal {O}(d\,(dk)^{d^2})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">O</mi> <mo stretchy="false">(</mo> <mi>d</mi> <mspace width="0.166667em" /> <msup> <mrow> <mo stretchy="false">(</mo> <mi>d</mi> <mi>k</mi> <mo stretchy="false">)</mo> </mrow> <msup> <mi>d</mi> <mn>2</mn> </msup> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, where d is the maximum hyperedge size. </ItemContent> <ItemContent> As a consequence, via hypergraph duality, Hypergraph Dominating Set, the domination of vertices by vertices in a hypergraph, is FPT parameterized by <InlineEquation ID="IEq10"> <EquationSource Format="TEX">$k+d$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>+</mo> <mi>d</mi> </mrow> </math></EquationSource> </InlineEquation> and admits a polynomial kernel for fixed d, where d is the maximum degree (the largest number of hyperedges containing a vertex). </ItemContent> <ItemContent> The problem of finding a Hyperedge Dominating Set is computationally difficult; specifically it is <Emphasis FontCategory="SansSerif">W[2]</Emphasis>-hard when parameterized by k. This hardness result holds even when every vertex is contained in at most two hyperedges and the intersection of any two hyperedges has size at most one. </ItemContent> <ItemContent> t-Path Edge Dominating Set is FPT when parameterized by <InlineEquation ID="IEq11"> <EquationSource Format="TEX">$k+t$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>+</mo> <mi>t</mi> </mrow> </math></EquationSource> </InlineEquation>. Additionally, it admits a kernel with <InlineEquation ID="IEq12"> <EquationSource Format="TEX">$\mathcal {O}(k^3 t^3)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">O</mi> <mo stretchy="false">(</mo> <msup> <mi>k</mi> <mn>3</mn> </msup> <msup> <mi>t</mi> <mn>3</mn> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> vertices and <InlineEquation ID="IEq13"> <EquationSource Format="TEX">$\mathcal {O}(k^4 t^4)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">O</mi> <mo stretchy="false">(</mo> <msup> <mi>k</mi> <mn>4</mn> </msup> <msup> <mi>t</mi> <mn>4</mn> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> edges. </ItemContent> </UnorderedList>

Parameterized Complexity of Generalizations of Edge Dominating Set

期刊论文
发表日期：

2026年7月14日

查看全文

Shubhada Aute,
Fahad Panolan,
Souvik Saha,
Saket Saurabh,
Anannya Upasana

摘要

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})$ $H = (U, F)$ , a set $F\subseteq \mathcal {F}$ $F \subseteq F$ is called a hyperedge dominating set if every hyperedge in $\mathcal {F}$ $F$ intersects at least one hyperedge $e\in F$ $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 surprising that this natural 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}$ $P$ of at most k paths, each on at most t vertices, such that for every edge of G, at least one of its endpoints belongs to the vertex set V(P) for some $P\in \mathcal {P}$ $P \in P$ . We show the following results and add to the literature on Edge Dominating Set.

Hyperedge Dominating Set is FPT parameterized by $k+d$ $k + d$ , where d is the maximum size of a hyperedge in the input hypergraph.

For every fixed d, Hyperedge Dominating Set admits a polynomial kernel: the reduced hypergraph has $\mathcal {O}((dk)^{d^2})$ $O ({(d k)}^{d^{2}})$ hyperedges and total size $\mathcal {O}(d\,(dk)^{d^2})$ $O (d {(d k)}^{d^{2}})$ , where d is the maximum hyperedge size.

As a consequence, via hypergraph duality, Hypergraph Dominating Set, the domination of vertices by vertices in a hypergraph, is FPT parameterized by $k+d$ $k + d$ and admits a polynomial kernel for fixed d, where d is the maximum degree (the largest number of hyperedges containing a vertex).

The problem of finding a Hyperedge Dominating Set is computationally difficult; specifically it is W[2]-hard when parameterized by k. This hardness result holds even when every vertex is contained in at most two hyperedges and the intersection of any two hyperedges has size at most one.

t-Path Edge Dominating Set is FPT when parameterized by $k+t$ $k + t$ . Additionally, it admits a kernel with $\mathcal {O}(k^3 t^3)$ $O (k^{3} t^{3})$ vertices and $\mathcal {O}(k^4 t^4)$ $O (k^{4} t^{4})$ edges.