How to remove vertices from a graph that are not coverable by cliques?

Question

Given a graph G = (V, E), a set of vertices V* in V, and an integer k, how do we remove vertices from G such that the remaining vertices are either in V* or are in a clique of size k with at least one vertex in V*?

Here is a toy example and solution:

The graph G = (V, E) is shown below. 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 G.

I have tried finding a clique for each vertex in V*, keeping track of the vertices covered by those cliques, and then removing the vertices in the graph that are not covered by cliques.

However, finding a clique for each vertex takes a very long time when the graph is large, and I was wondering if there was a simpler way to prune out the vertices that do not belong to any cliques.

Answer 1

finding a clique for each vertex takes a very long time

So, only invoke the clique finding if all other conditions have been met:

- LOOP W over vertices
   - IF W in V*
        - CONTINUE LOOP W
   - BFS from W, visiting X
        - IF X in V*
            - FIND clique containing W
            - If clique size != k
                - MARK W to_be_deleted
- END LOOP W
- DELETE vertices marked to_be_deleted
           

Answer 2

I'll use I(S1, S2) to represent the intersection of two sets.

Let W = V \ V* (set subtraction).

For every vertex w in W
  For every vertex v in I(N(W), V*)
    There is no solution for v & w if |I(N(w), N(v))| < k-2
    Otherwise, search for a clique of size k-2 in that intersection. Two good heuristics for this (if you can use a heuristic) are 'Tabu search' and 'Iterated Greedy' 
    If you find a clique of size k-2, you're done with w as well as with any other vertices of your clique not in V*. Remove those from your queue of vertices to process.
   

If you go this route, I have Rust code that implements the Iterated Greedy approach to finding cliques that I'd be happy to share. High-level description is that for a graph G with n nodes, we start with each node in its own clique in random order.

• Greed: We then greedily merge each node with the leftmost node it can merge with and preserve the clique property. If there is none, it stands alone and future nodes can be merged with it.
• Iterate: We shuffle our cliques, convert them back to vertices (but so all the vertices of the same clique are adjacent; within cliques the order doesn't matter), and we repeat the process.

Note that the total number of cliques can never increase. In practice (in my use case anyway) it often decreases.

For exploring a specific vertex or pair of vertices (not my use case), you'd likely benefit by forcing them or their containing clique to always be leftmost so the greedy step always attempts to merge into it first.

You need to decide when to stop if you don't find a clique of the size you're hoping for. That could be a number of steps with no improvement in the size of the clique containing the vertex you're looking for.

This approach can benefit from simulated annealing. It may be that the initial ordering of vertices caused the pair of vertices you're trying to build a clique around not to have a solution. When you stop without a solution, you might try randomizing the order of the other vertices in the array and retry any number of times.