-1

Note: this is not a duplicate of the question How to remove vertices from a graph that are not coverable by cliques?. That question is asking how we can remove vertices that are not in a clique, and this question is asking how we can remove as many vertices as possible (regardless of whether they are in cliques or not) while ensuring that specific vertices are still covered by cliques.

Given a set of specific vertices V* in a graph, how can I remove as many vertices from the graph as possible while still ensuring that the vertices in V* are each covered by a clique of size k?

Here is a toy example and solution:

The vertices with a white "x" are in V*. k = 3. The vertices that are light orange are the vertices that should be removed from the graph.

enter image description here

So far, I have tried finding a clique for each vertex in V*, and then removing all vertices form the graph that are not in those cliques, but this takes a long time, when the graph is large. I am wondering if there is a faster way.

thunderbird30
  • 37
  • 3
  • 4
    You've [already asked this question](https://stackoverflow.com/questions/77003318/how-to-remove-vertices-from-a-graph-that-are-not-coverable-by-cliques). Please edit that one instead of reasking the same question again. – cafce25 Aug 30 '23 at 11:05
  • This question is slightly different from the other question. In the other question, I am trying to remove vertices that are not in cliques. In this question, I am trying to remove as many vertices as possible while still ensuring certain vertices are in cliques (the vertices that are removed could be in cliques). – thunderbird30 Aug 30 '23 at 16:20
  • I will edit the question so that the difference is more evident. – thunderbird30 Aug 30 '23 at 16:23

0 Answers0