0
$\begingroup$

the exact complexity for hypergraph transversal problem is yet unknown and is an open research problem.

However, I would need a fast way to compute, on paper, the minimal transversal of a hypergraph. A transversal intersects all hyperedges of the graph.

A transversal is minimal if it does not contain any transversal as a proper subset.

Let us look at this example, where V = {a,b,c,d,e}

Hyperedge 1: de
Hyperedge 2: abce
Hyperedge 3: bd

How can I compute, on paper, the minimal transversal of this hypergraph? Computing the minimal transversal with only 2 hyperedges is trivial, but in the 3 hyperedges case, the complexity increases.

Looking forward to your input.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Why do you think "computing on paper" is different from "compute with an algorithm"? For small instances, use any algorithm you prefer. $\endgroup$ – Raphael♦ Jul 24 '16 at 10:16
  • $\begingroup$ It was meant to emphasize that I was not looking for an implementation solution.This is what would be great, an algorithm that can help the fast computation of minimal hypergraph transversals. $\endgroup$ – iulia Jul 24 '16 at 13:26
  • $\begingroup$ But algorithm exactly works on paper, computer etc. It does not matter how you use it, these are (without special cases) deterministic steps that you perform. Moreover if you do it on paper then you still use some defined steps (algorithm). $\endgroup$ – Evil Jul 24 '16 at 16:26
  • 1
    $\begingroup$ The problem is NP-hard, so there is no fast algorithm. "On paper" maybe means "small input", so try all possibilities, starting from the smallest ones. This is what I might do. $\endgroup$ – Juho Jul 24 '16 at 22:03
1
$\begingroup$

The problem is NP-hard by a reduction from hitting set. Thus, there is no efficient or "easy" algorithm in this sense. Of course, any algorithm you might execute with pen and paper can also be realized on a computer.

With that being said, just try all possibilities by hand. As you observe, it is easy to see if the solution is of size one or two. It can get much more tedious after that, and the reason is NP-hardness.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.