Let's say we have a graph $G$ with $|V|$ nodes. We wish to select the smallest set of nodes $S$ that:
$dis(i, j) \le k, \forall i \in S, j\in V-S$,
where $k$ denotes a certain distance threshold.
Smallest means the least number of nodes.
1
-
1$\begingroup$ What is your question? $\endgroup$– NathanielNov 9, 2022 at 12:55
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
Reduce from dominating set, let $k=1$.
$\begingroup$
$\endgroup$
1
This looks quite NP-complete to me (just guessing). Obviously if S is not connected then you split it into connected sub-graphs and solve each one individually. Call two nodes a, b connected if their distance is at most k.
Since this is NP-complete, just a heuristic: Put the nodes in some order. If a comes before b, and a is connected to everyone that b is connected to, then we wouldn't put b into S (because exchanging it with a would be better or the same). This reduces the number of candidates to put into S.
Look for the node with the most connections to nodes not in S and not connected to a node in S, and move it into S. Repeat until everything is connected to S.
A second algorithm: Look for nodes with many connections to nodes not in S and not connected to a node in S, pick one at random, and move it into S. Repeat until everything is connected to S. Count the nodes in S. Then try again until it looks like better solutions are hard to find.
A third algorithm: Same as the second, put prefer nodes with connections that don't have many connections themselves.
That's just some ideas. You can find an optimal S by using backtracking. You definitely prefer a node to put into S that is connected to everyone in S, and if there is no such node then you prefer two nodes that are together connected to everyone not in S. Just try out different things, and measure the time.
-
$\begingroup$ Thank you for the useful advice. The possible solution seems to be a greedy algorithm with some rules. $\endgroup$– ly2Nov 10, 2022 at 13:46