Clique máximo no gráfico de intervalo

Question

De acordo com Algoritmos eficientes para gráficos de intervalo e gráficos de arco circular há um $O(n\logn)$ algoritmo para encontrar o clique máximo em um gráfico de intervalo, assumindo que você tenha o modelo de intervalo.Infelizmente, nem o artigo nem as referências realmente elaboram o que é o algoritmo, além de dizer que você pode modificar o algoritmo bem conhecido para colorir gráficos de intervalo de maneira ideal (onde você colore avidamente o gráfico na ordem gerada pela classificação lexicográfica dos intervalos) para calcular o clique máximo.Isso faz sentido, pois a maior cor usada em uma coloração ideal é o tamanho do clique máximo em um gráfico perfeito (e os gráficos de intervalo são perfeitos).Infelizmente, além disso, não sei como calcular o clique máximo.A abordagem óbvia é modificar alguma estrutura de dados toda vez que a cor máxima aumenta, mas não consigo descobrir exatamente qual estrutura de dados usar ou como modificá-la.

Alguém conhece uma referência para esse algoritmo ou pode reinventar uma descrição dele?

Answer 1

Os gráficos de intervalo são gráficos CHORDAL, para que você possa usar um algoritmo de tempo linear para encontrar Max Clique em um gráfico de chordos.Isso pode ser feito pela primeira vez encontrando uma encomenda de eliminação perfeita e, em seguida, usando o fato de que toda vez que um vértice é eliminado, ele se forma uma clique junto com seus vizinhos que ainda não são eliminados.Além disso, todos os cliques maximais aparecem nesse processo.

Para encontrar a encomenda de eliminação perfeita, a pesquisa máxima de cardinalidade (MCS) é o algoritmo mais simples e funciona em tempo linear.(Eu não sei por que a Wikipedia menciona lexbfs primeiro, é muito mais complicado.)

Answer 2

def mex(m):
  for i in [0 ..]:
    if not(m.contains(i)):
      return i

def maxCliqueOfIntervals(intervals):
  maxClique = []
  map = {}
  for interval in intervals.sort():
    // map should only contain intervals that overlap with the current interval
    map.filter(lambda x: overlaps(x, interval));
    // choose the smallest color not in the map to color the current interval
    map.insert(mex(map), interval);
    // the map now comprises a clique, if it is larger than the current max clique,
    // replace the max clique with the current map
    if map.size() > maxClique.size():
      maxClique = map.elems();
  return maxClique;

Acredito que esta seja uma implementação correta baseada no algoritmo de coloração de intervalo executado em $O(n\logn)$ tempo.

Se você se preocupa apenas com o clique máximo, isso pode ser um pouco simplificado:

def maxCliqueOfIntervals(intervals):
  maxClique = []
  active = []
  for interval in intervals.sort():
    active.filter(\x -> overlaps(x, interval));
    active.push(interval);
    if active.size() > maxClique.size():
      maxClique = active;
  return maxClique;