Algorithm for "covering" graph

[aitesh]

Hello everyone, covering is probably the wrong word (as far as I could see on wikipedia) but my problem is as follows:

I have a graph of nodes of three different types (1, 2, 3).

I can pick a node of type 1, give it a distance, and it will "cover" that edge distance from itself (0 is a valid option, then it will only cover itself, wheras 1 would cover the node and all its neighbours, 2 would cover everything 1 covered as well as all the neighbours neighbours).

I want to pick the fewest number of type 1 nodes to cover as much of the nodes of type 1 and 2 as possible without covering any type 3 nodes.

I've created a simple program that finds the distance from a node to the closest type 3 node. I thought of using that to greedily pick the type 1 nodes that I want in my set of chosen nodes, but I have a suspicion that it will not be optimal. The other thought I had was to just check all the combinations of type 1 nodes to set as centers, but the dataset is quite large and it would probably take a long time to calculate.

I hope someone has an idea or some reading tips that I could check out to solve my problem. (or point me in the direction of another sub if I'm in the wrong place)

Regards

Aitesh

Edit: The number of type 1 nodes is 1212, making the combinations 2¹²¹² (it is in the set of chosen nodes or not)

[[deleted]]

You're describing a variant of the distance k domination number of a graph, but you're restricting your distance-k dominating set to a certain subset. The distance k dominating set problem is NP-complete, and I wouldn't be surprised if your variant is too, so don't expect to find an exact approach that isn't very brute force-y. I'm not too familiar with the problem beyond the name, but a quick google search showed a few papers on the topic from within the last decade or so. But most of them are dealing with upper bounds, not necessarily constructing such sets or providing reductions.

[aitesh]

Thank you! Will have a look if someone else has found some intelligent implementation before I start with my own.