1
$\begingroup$

I am looking for some known algorithm that finds, for a given graph, all the maximal sets of vertices that avoid a clique of some given size $k$. I'd prefer one written in MATLAB, but other languages are OK as well. References to known algorithms without implementation would be also great.

For example if $k=2$ then this is just the collection of all maximal independent sets ,since they avoid cliques of size 2, which are just edges. In this case, one can use Bron-Kerbosch maximal independent set and maximal clique algorithm given here

I am interested in the case $k>2$, so I can't use the algorithm above.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ If you are looking for an implementation, then you're in the wrong group. $\endgroup$
    – Gordon Royle
    Commented Apr 26, 2016 at 9:55
  • 2
    $\begingroup$ Is there some other forum that deals with implementations that you suggest? Thanks! (I also edited the question- References to known algorithms without implementation would be also great.) $\endgroup$
    – David
    Commented Apr 26, 2016 at 10:08
  • 1
    $\begingroup$ There is an obvious generalisation of the maximal independent set algorithm to maximal triangle-free sets: maintain the same three lists of vertices that are in, might be in and you have decided are not in, and update based on the formation of triangles rather than the presence of edges. $\endgroup$
    – Ben Barber
    Commented Apr 26, 2016 at 10:44
  • $\begingroup$ Avoid -- definition? $\endgroup$
    – Wlod AA
    Commented Feb 2, 2023 at 9:05

1 Answer 1

Reset to default
0
$\begingroup$

Given the fixed $k$, you could look at all $\binom{n}{k}$ subsets of vertices to see if they form a clique of size $k$ (or do whatever you like to enumerate all cliques of size $k$ -- there might be a variation of Bron-Kerbosch for that). List all your sets of $k$ vertices which violate the structure you seek.

To maximize your selected vertices in your question, you are looking to remove the minimum number of vertices which will 'hit' all your constructed $k$-sets. This is the HITTING-SET problem. Beware that your $k$ value will be the $d$ in the $d$-HITTING-SET problem in most references, while "$k$" will normally be reserved for the number of vertices that will be removed.

The bad news is that HITTING-SET is NP-Complete but the good news:

  • it is Fixed-parameter tractable and there are good exact algorithms for it
  • is very well-studied
  • there are fast approximation algorithms / heuristics with provable bounds
  • most solutions generalize to hitting sets where the input sets are not all of equal size, and vertex-weighted variants
  • hitting set solves a lot of other problems where you are trying to find the max number of vertices with an avoidance property (through the means of removing the fewest number of vertices from subsets that have that property)
  • there are implementations of the problem of finding the hitting set: https://github.com/VeraLiconaResearchGroup/Minimal-Hitting-Set-Algorithms

(This implementation finds all minimal hitting sets, from which you can pick your favorite smallest one, or you can apply a parameter to only generate hitting sets up to a certain size)

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .