<p>According to the <a href="http://fpt.wikidot.com/fpt-races">Parameterized Complexity</a> Wiki, the currently best known FPT algorithm for 3-Hitting-Set has a complexity of $2.076^k \cdot n^{O(1)}$, the algorithm is from the <a href="http://liu.diva-portal.org/smash/get/diva2:23420/FULLTEXT01.pdf">PhD thesis</a> of Magnus Wahlström. </p>

CC BY-SA 3.0
2016-05-30T08:03:33.207Z
2016-05-30T21:13:30.270Z
2016-05-30T21:13:30.270Z
Jan Johannsen
<p>My research problem involves solving a special instance of the 3-Hitting Set problem, and I was wondering whether my result is actually significant (i.e. if it is better than the best known result for 3-Hitting Set).</p>

<p>I'm specifically interested in the case where the parameter is the optimal hitting set size. </p>

<p>I know the paper by <a href="http://www.sciencedirect.com/science/article/pii/S1570866703000091" rel="nofollow">Niedermeier and Rossmanith</a> that presents an algorithm of run-time $O(2.27^k + n)$, but that paper is pretty old. </p>

CC BY-SA 3.0
2016-05-28T04:40:21.157Z
If you look at [the papers that cite that paper](https://scholar.google.com/scholar?cites=9325524540154631169&as_sdt=5,37&sciodt=0,37&hl=en), you'll find better results, e.g., by [Fernau](https://scholar.google.com/scholar?cluster=4059058900921347450&hl=en&as_sdt=5,37&sciodt=0,37). You should probably keep looking
Austin Buchanan
<graph-algorithms><fixed-parameter-tractable>
What is the best known FPT result for 3-hitting set?
user1441057
# What is the best known FPT result for 3-hitting set?

(Asked by: username_0 on 2016-05-27)

My research problem involves solving a special instance of the 3-Hitting Set problem, and I was wondering whether my result is actually significant (i.e. if it is better than the best known result for 3-Hitting Set).

I'm specifically interested in the case where the parameter is the optimal hitting set size.

I know the paper by [Niedermeier and Rossmanith](http://www.sciencedirect.com/science/article/pii/S1570866703000091) that presents an algorithm of run-time $O(2.27^k + n)$, but that paper is pretty old.

**Tags:** graph-algorithms, fixed-parameter-tractable

> **Comments:**
> **username_1**: If you look at [the papers that cite that paper](https://scholar.google.com/scholar?cites=9325524540154631169&as_sdt=5,37&sciodt=0,37&hl=en), you'll find better results, e.g., by [Fernau](https://scholar.google.com/scholar?cluster=4059058900921347450&hl=en&as_sdt=5,37&sciodt=0,37). You should probably keep looking  

---

## 1 answers

### Answer by username_2 on 2016-05-30. Score: 10 | Accepted answer

According to the [Parameterized Complexity](http://fpt.wikidot.com/fpt-races) Wiki, the currently best known FPT algorithm for 3-Hitting-Set has a complexity of $2.076^k \cdot n^{O(1)}$, the algorithm is from the [PhD thesis](http://liu.diva-portal.org/smash/get/diva2:23420/FULLTEXT01.pdf) of Magnus Wahlström.


---

