This is in a series of posts. Previous quetion: Vertex cover with covering radius 2

Other series: Karp hardness of searching for a matching split

In this problem, our cover for a given undirected graph consists of midpoints of edges. From a midpoint of an edge $e$, with radius $1$, this midpoint will cover $e$ and halves of edges incident to $e$ (only those halves directly incident to $e$ which means those further halves of these incident edges are still not covered by the mentioned midpoint). And an edge is covered if both halves of its are covered.

So, what is the complexity of this problem: Given an undirected graph $G$ and a natural number $k$, decide whether it is possible to choose $k$ edge-midpoints of $G$ to cover the graph.

It might be of help to mention that edge-midpoints cover with radius $1.5$ is edge dominating set which is known to be $\mathrm{NP}$-complete.


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.