In the A-Multi3-Hitting Set problem (A-M3HS), where <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1300_Article_IEq1.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="97" /> </InlineMediaObject> <EquationSource Format="TEX">$A \subseteq \{1,2,3\}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>A</mi> <mo>⊆</mo> <mo stretchy="false">{</mo> <mn>1</mn> <mo>,</mo> <mn>2</mn> <mo>,</mo> <mn>3</mn> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation>, the input is a hypergraph G in which the hyperedges have sizes at most 3 and an integer k, and the goal is to decide if there is a set S of at most k vertices such that <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1300_Article_IEq2.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="87" /> </InlineMediaObject> <EquationSource Format="TEX">$|S \cap e| \in A$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">|</mo> <mi>S</mi> <mo>∩</mo> <mi>e</mi> <mo stretchy="false">|</mo> <mo>∈</mo> <mi>A</mi> </mrow> </math></EquationSource> </InlineEquation> for every hyperedge e. In this paper we give <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1300_Article_IEq3.gif" Format="GIF" Height="21" Rendition="HTML" Resolution="72" Type="Linedraw" Width="77" /> </InlineMediaObject> <EquationSource Format="TEX">$O^(2.027^k)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mi>O</mi> <mo>∗</mo> </msup> <mrow> <mo stretchy="false">(</mo> <mn>2</mn> <mo>.</mo> <msup> <mn>027</mn> <mi>k</mi> </msup> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>-time algorithms for <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1300_Article_IEq4.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="31" /> </InlineMediaObject> <EquationSource Format="TEX">$\{1\}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">{</mo> <mn>1</mn> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation>-M3HS and <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1300_Article_IEq5.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="47" /> </InlineMediaObject> <EquationSource Format="TEX">$\{1,3\}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">{</mo> <mn>1</mn> <mo>,</mo> <mn>3</mn> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation>-M3HS, and an <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1300_Article_IEq6.gif" Format="GIF" Height="21" Rendition="HTML" Resolution="72" Type="Linedraw" Width="77" /> </InlineMediaObject> <EquationSource Format="TEX">$O^(1.381^k)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mi>O</mi> <mo>∗</mo> </msup> <mrow> <mo stretchy="false">(</mo> <mn>1</mn> <mo>.</mo> <msup> <mn>381</mn> <mi>k</mi> </msup> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>-time algorithm for <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1300_Article_IEq7.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="31" /> </InlineMediaObject> <EquationSource Format="TEX">$\{2\}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">{</mo> <mn>2</mn> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation>-M3HS.

Faster parameterized algorithms for variants of 3-Hitting Set

期刊论文
出版模式：

开放获取
发表日期：

2025年5月7日

查看全文

Dekel Tsur

摘要

In the A-Multi3-Hitting Set problem (A-M3HS), where $A \subseteq \{1,2,3\}$ $A \subseteq {1, 2, 3}$ , the input is a hypergraph G in which the hyperedges have sizes at most 3 and an integer k, and the goal is to decide if there is a set S of at most k vertices such that $|S \cap e| \in A$ $| S \cap e | \in A$ for every hyperedge e. In this paper we give $O^*(2.027^k)$ $O^{*} (2 . 027^{k})$ -time algorithms for $\{1\}$ ${1}$ -M3HS and $\{1,3\}$ ${1, 3}$ -M3HS, and an $O^*(1.381^k)$ $O^{*} (1 . 381^{k})$ -time algorithm for $\{2\}$ ${2}$ -M3HS.