Tamanho mínimo de contratação de um DAG em um novo DAG

15

Nós temos um DAG. Temos uma função nos nós (falando livremente, numeramos os nós). Gostaríamos de criar um novo gráfico direcionado com estas regras:F:VN

  1. Somente nós com o mesmo número podem ser contratados no mesmo novo nó. . (No entanto, .)F(x)F(y)xyxyF(x)F(y)
  2. Adicionamos todas as arestas antigas entre os novos nós: (x,y)Exy(x,y)E .
  3. Este novo gráfico ainda é um DAG.

Qual é o mínimo |V|? O que é um algoritmo que cria um novo gráfico mínimo?

chx
fonte
11
Portanto, o problema de decisão parece ser: dado um DAG da cor do vértice e um número inteiro , decida se existe um DAG com no máximo vértices formados pela contratação de vértices da mesma cor. kkk
András Salamon
11
Se você contrata dois nós conectados, obtém um auto-loop proibido?
Yuval Filmus
11
Não. Leia 2. novamente: só adicionamos a borda se os dois nós após a contração ainda forem diferentes. Se dois nós forem contratados em um, não adicionamos a borda.
Chx #
11
@chx Você está pedindo "mínimo" ou "mínimo"?
Realz Slaw
11
você pode dar alguma motivação / bkg?
vzn

Respostas:

5

Uma abordagem para resolver esse problema seria usar a programação linear inteira (ILP). Vamos abordar a versão de decisão do problema: dado , existe uma maneira de contratar vértices da mesma cor para obter um DAG de tamanho k ?kk

Isso pode ser expresso como uma instância de ILP usando técnicas padrão. Recebemos a cor de cada vértice no gráfico original. Sugiro que rotulemos cada vértice com um rótulo em ; todos os vértices com a mesma etiqueta e a mesma cor serão contratados. Portanto, o problema de decisão se torna: existe uma rotulagem, de modo que a contratação de todos os vértices da mesma cor da mesma etiqueta produza um DAG?{1,2,,k}

Para expressar isso como um programa linear inteiro, introduza uma variável inteira para cada vértice v , para representar o rótulo no vértice v . Adicione a desigualdade 1 vk .vvv1vk

A próxima etapa é expressar o requisito de que o gráfico contratado deve ser um DAG. Observe que, se houver uma rotulagem do formulário listado acima, sem perda de generalidade, existe uma rotulagem em que os rótulos induzem uma classificação topológica no gráfico contratado (ou seja, se precede w no gráfico contratado, o rótulo de v é menor que o rótulo de w ). Portanto, para cada aresta v w no gráfico original, adicionaremos a restrição de que v e w têm a mesma etiqueta e a mesma cor, ou então o rótulo de v é menor que o rótulo de w . Especificamente, para cada aresta vvwvwvwvwvw no gráfico inicial em que v , w tem a mesma cor, adicione a desigualdadevw . Para cada aresta v w onde v , w tem cores diferentes, adicione a desigualdadev < w .vwv,wvwvwv,wv<w

Agora veja se existe alguma solução viável para esse programa linear inteiro. Haverá uma solução viável se, e somente se, a etiqueta tiver a forma desejada (por exemplo, a contratação de todos os vértices da mesma etiqueta da mesma cor produz um DAG). Em outras palavras, haverá uma solução viável se, e somente se, houver uma maneira de contratar o gráfico original para um DAG de tamanho . Podemos usar qualquer solucionador de programação linear inteiro; se o solucionador de ILP nos der uma resposta, temos uma resposta para o problema de decisão original.k

Obviamente, isso não garante que seja concluído em tempo polinomial. Não há garantias. No entanto, os solucionadores de ILP ficaram muito bons. Eu esperaria que, para um gráfico de tamanho razoável, você tenha uma chance decente de que um solucionador de ILP possa resolver esse problema em um período de tempo razoável.

Também é possível codificar isso como uma instância SAT e usar um solucionador SAT. Não sei se isso seria mais eficaz. A versão do ILP é provavelmente mais fácil de se pensar.

(Espero que esteja certo. Não verifiquei todos os detalhes com cuidado; portanto, verifique novamente meu raciocínio! Espero não ter dado errado em algum lugar.)


Atualização (21/10): Parece que os ILPs deste formulário podem ser resolvidos em tempo linear, processando o DAG em ordem topológica e mantendo o controle do limite inferior no rótulo de cada vértice. Isso me desconfia da minha solução: cometi um erro em algum lugar?

DW
fonte
Obrigado pela resposta detalhada! Eu recebo as restrições e elas parecem razoáveis. No entanto, embora eu não seja muito versado em ILP, pensei que a programação linear inteira precisava de uma função que você queria maximizar (ou minimizar) e não vejo isso em lugar algum. Eu verifiquei apenas na Wikipedia para estar errado.
Chx #
@chx, estou usando o ILP para testar a viabilidade das restrições. Isso pode ser feito pedindo ao solucionador ILP para maximizar qualquer função objetiva que você gosta (por exemplo, maximizar 0) e, em seguida, ignorando o valor da função objetiva e procurando apenas ver se a ILP é viável ou não. O solucionador de ILP responde "Inviável" (o que significa que não há DAG contratado de tamanho ) ou responde "Viável" e fornece o melhor valor da função objetiva que poderia encontrar; nesse caso, você ignora o valor da função objetivo (e sabe que existe um DAG de tamanho k ). kk
DW
Veja, por exemplo, engineering.purdue.edu/~engelb/abe565/… ("Eu só quero saber se existe ou não uma solução viável .")
DW
Em relação à sua solução de tempo linear; Como não digeri sua formulação de ILP, não posso julgá-la, mas tenho certeza de que posso provar que o problema é difícil de NP, o que tornaria uma solução de tempo linear bastante útil: P. Vou postar em breve.
Realz Slaw
@RealzSlaw, obrigado! Nesse caso, suspeito fortemente que possa ter errado em algum lugar (embora ainda não tenha certeza de onde).
DW
5

NOTA: AFAICT, DW encontrou um buraco nessa redução e está errado (consulte os comentários). Mantê-lo aqui por razões históricas.

Introdução : primeiro vou reduzir o problema do Monotone 3SAT ao nosso problema. Embora o problema do Monotone 3SAT seja trivialmente satisfatório, nosso problema pode resolver ainda mais o problema do Mínimo Verdadeiro Monotone 3SAT , que é difícil para NP; portanto, esse problema é difícil de NP.

Redução do Monotone 3SAT para o nosso problema

Temos uma fórmula booleana monótona expressa como uma sequência de variáveis ​​e uma sequência de cláusulas. O CNF tem a forma tal que:Φ=(V,C)

e

(ciC) ci=(xjxkxl)||(xj,xk,xlV)

i=1nci|ciC,n=|C|.

Conversão

Construímos um gráfico, . Cada vértice em G ' tem um rótulo; vértices com o mesmo rótulo são elegíveis para contração.G=V,EG

Primeiro, construímos o gráfico da seguinte maneira: para cada , criamos dois nós, cada um rotulado x i , e uma aresta direcionada de um para o outro (clique nas imagens para visualizar em alta resolução).xiVxi

insira a descrição da imagem aqui

É claro que esses nós podem ser contratados porque têm o mesmo rótulo. Consideraremos variáveis ​​/ nós contratados como valor falso e aqueles que não forem contratados como valor verdadeiro :

insira a descrição da imagem aqui

V2|V|ciC, ci=(xjxkxl)|xj,xk,xlVci

insira a descrição da imagem aqui

ci1ci

2|V|+|C|

xixj xkcici

Aqui está outra visualização, desenrolando a restrição de cláusula:

insira a descrição da imagem aqui

Assim, cada restrição de cláusula requer que pelo menos uma das variáveis ​​que ela contenha permaneça não contratada; como os nós não contratados são avaliados como verdadeiros, isso requer que uma das variáveis ​​seja verdadeira; exatamente o que o Monotone SAT exige para suas cláusulas.

Redução do Mínimo Verdadeiro Monótono 3SAT

O monótono 3SAT é trivialmente satisfatório; você pode simplesmente definir todas as variáveis ​​como true.

No entanto, como nosso problema de minimização do DAG é encontrar o maior número de contrações, isso significa encontrar a atribuição satisfatória que produz as variáveis ​​mais falsas em nossa CNF; que é o mesmo que encontrar as variáveis ​​verdadeiras mínimas. Às vezes, esse problema é chamado Minimum True Monotone 3SAT ou aqui (como um problema de otimização ou problema de decisão) ou k-True Monotone 2SAT (como um problema de decisão mais fraco); problemas NP-difíceis. Assim, o nosso problema é difícil para o NP.


Referências:

Fontes do gráfico:

Realz Slaw
fonte
11
Uau. então a solução da DW deve estar errada (ou provamos NP = P que duvido um pouco: P) - mas onde?
chx
(x1 1x2x6)(x1 1x4x5)(x3x4x6)x1=x4=x6=False x2=x3=x5=Truec1x1x4x6c1
@DW Também é bom falar com você novamente: D, e boa sorte, se ambos estivermos certos, podemos ter P = NP em sua resposta! / jk
Realz Slaw
(x1,x3)
@RealzSlaw, receio que ainda não o siga ... Não vejo nenhuma razão pela qual minha fórmula precise ser convertida. Acredito que já é uma instância do Minimum True Monotone 3SAT. Mas deixe-me subir de nível. De forma mais ampla, vejo uma redução proposta, mas não vejo nenhum argumento de que a redução esteja correta - está faltando. Para que a redução esteja correta, é necessário mapear instâncias YES para instâncias YES e NO, para NO. Suspeito que, se você tentar redigir uma prova de correção para sua redução, terá um problema ao considerar a fórmula que dei.
DW
1

A cada substituição (exceto as substituições pai-filho diretas), você adiciona novos relacionamentos de ancestrais-descendentes que tornam pouco trivial determinar qual deles realmente vale a pena a longo prazo. Portanto, um algoritmo ganancioso simples falhará no caso geral. No entanto, se você fizer uma abordagem de força bruta, poderá determinar o menor gráfico:

Python-ish (não testado):

def play((V,E),F,sequence=[]):
  """
  (V,E) -- a dag.
  V     -- a set of vertices.
  E     -- a set of directed-edge-tuples.
  F     -- a function that takes a vertex, returns an integer.
  sequence -- the sequence of moved taken so far; starts with/defaults to
              an empty list, will contain tuples of the form (x,y)
              where x is removed and replaced with y.

  Returns the best recursively found solution.
  """

  #find all the integer values in the graph, remember which
  # values correspond to what vertices. Of the form {integer => {vertices}}.
  n2v = {}
  for x in V:
    n = F(x)

    #for each integer, make sure you have a set to put the vertices in.
    if n not in n2v:
      n2v[n] = set()

    #for each integer, add the vertex to the equivalent set.
    n2v[n].add(v)

  #record the best sequence/solution. You start with the current sequence,
  # and see if you can obtain anything better.
  best_solution = list(sequence)

  #Now you will try to combine a single pair of vertices, obtain a new
  # graph and then recursively play the game again from that graph. 

  #for each integer and equivalent set of vertices,
  for n,vset in n2v.iteritems():

    #pick a pair of vertices
    for x in vset:
      for y in vset:

        #no point if they are the same.
        if x == y:
          continue

        #If there is a path from x => y or y => x, then you will be
        # introducing a cycle, breaking a rule. So in that case, disregard
        # this pair.
        #However, the exception is when one is a direct child of the other;
        # in that case you can safely combine the vertices.
        if pathtest((V,E),x,y) and (x,y) not in E and (x,y) not in E:
          continue

        #combine the vertices (function is defined below), discard x,
        # replace it with y, obtain the new graph, (V',E').
        Vp,Ep = combine_vertex((V,E),x,y))

        #record the sequence for this move.
        sequencep = list(sequence) + [(x,y)]

        #recurse and play the game from this new graph.
        solution = play(Vp,Ep,F,sequencep)

        #if the returned solution is better than the current best,
        if len(solution) > len(best_solution):
          #record the new best solution
          best_solution = solution
  #return the best recorded solution
  return best_solution


def combine_vertex((V0,E0),x,y):
  """
  (V0,E0)   -- an initial digraph.
  V0        -- a set of vertices.
  E0        -- a set of directed-edge-tuples.
  x         -- vertex to discard.
  y         -- vertex to replace it with.

  returns a new digraph replacing all relationships to and from x to relate
   to y instead, and removing x from the graph entirely.
  """

  #the final vertex set will have everything except x
  V = set(V0)
  V.discard(x)

  #now you construct the edge set.
  E = set()

  #for every edge,
  for (u0,v0) in E0:
    #recreate the edge in the new graph, but replace any occurence
    # of x.  
    u,v = u0,v0
    #if x is in the edge: replace it
    if u == x:
      u = y
    if v == x:
      v == y

    #sometimes u=v=y and can now be pointing to itself, don't add that
    # edge
    if u == v:
      continue

    #add the new/replaced edge into the edge-set.
    E.add( (u,v) )
  return (V,E)

Não tenho certeza se é realmente um problema difícil, mas brincar com alguns gráficos manualmente parece muito combinatório. Estou curioso para saber se algo difícil pode ser reduzido a esse problema ou se existe um algoritmo com melhor tempo de execução.

Realz Slaw
fonte
11
Estou curioso também :)
chx