I'm stuck with a problem and wonder whether you can help me. I guess the biggest problem is that I don't even know what I have to google for to find information about my problem. I'll try to explain it as good as I can:

I have a delaunay triangulation $G = (V,E)$ with $n$ vertices. I know it is a planar graph, so I can find a maximum vertex cover with $\leq\frac{3n}{4}$ vertices (4-color theorem).

Now I'm looking at the $k$-uniform hypergraph $H_k = (V,E_k)$ that raises from $G$ by taking every hyperedge consisting of $k$ connected vertices of G, i.e. $$ E_k = \{h \mid h \text{ is the set of vertices of a}\\ \text{connected, induced subgraph of G with exactly k vertices}\} $$ and what to find a maximum hitting set of this hypergraph.

Even when I'm trying this with general planar graphs, I can't get to a solution. I'm just not experienced enough in hypergraphs or graph theory in general. I thank you for any help and hope that maybe you know where I have to look for to find some help.

Another different but very connected question: The delaunay triangulation gives me the vertices that are "neighbours", i.e. that are closest to each other. Is there a generalization of the delaunay triangulation that gives me the $2$nd-closest, $3$rd-closest and up to the $k$th-closest neighbours. I want to find all hyperedges of $k$ vertices $\{v_1, \dots, v_k\}$ where $v_1$ is the closest vertex to $v_2$, the $2$nd-closest to $v_3$, up to the $(k$-$1)$th-closest to $v_k$ and finally a maximum hitting set on the associated hypergraph.

Best, op_mickey


Your Answer

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

Browse other questions tagged or ask your own question.