CODEWITHSUNDEEP
algorithmclique
Rajat
Rajat

Reputation: 249

Finding clique cover of a graph

Let say there is a black box (/an algorithm) which gives me a clique of a graph. Is there anyway to find the clique cover from that?

An intuitive idea what I am trying to find is given in the picture. I am trying to find the black box part. Please feel free if further clarification is needed. I have an idea which updates the graph by deleting the edges of the cliques. I do not know how good it will work. Looking forward for any other ideas.

Also, it will be very helpful if you could provide me any good reference of approximate clique covering algorithm. enter image description here

Upvotes: 2

Views: 1224

Answers (1)

Louis Ricci
Louis Ricci

Reputation: 21086

http://mathworld.wolfram.com/CliqueCoveringNumber.html

Removing edges won't help you, since the new graph may be missing a clique that would of been used to solve the cover.

    B
  / | \
A   |  D
  \ | /
    C

You have 2 maximal Cliques, ABC and BCD, if you started with ABC and removed it's edges AB AC and BC your algorithm wouldn't be able to find the BCD clique.

You'll need all of the maximal cliques of the graph before you try to calculate clique cover number.

AllCliques = GetAllCliques()
MaximalCliques = AllCliques
For Each ckA in MaximalCliques
  For Each ckB in MaximalCliques.Excluding(ckA)
    If all vertices in ckA are in ckB Then MaximalCliques.Remove(ckA)
    If all vertices in ckB are in ckA Then MaximalCliques.Remove(ckB)
Return MaximalCliques

Then the naive approach to find the clique cover number from all of the maximal cliques is run through the permutations and check

MinCover = MaximalCliques.Count
For Each ckList in Permute(MaximalCliques)
  Cover = 0
  TestSet = Graph.Vertices
  For Each ck in ckList
    TestSet.Remove(ck.Vertices)
    Cover = Cover + 1
    If TestSet.Count = 0 Then Break
  If Cover < MinCover Then MinCover = Cover
Return MinCover

Upvotes: 1

Related Questions