Tipo topológico Lexicographically mínimo de um DAG rotulado

13

Considere o problema em que nos é dado como entrada um gráfico acíclico direcionado , uma função de rotulação de para um conjunto com uma ordem total (por exemplo, os números inteiros) e onde nos perguntam para calcular o tipo topológico lexicograficamente menor de em termos de . Mais precisamente, um tipo topológico de é uma enumeração de como , tal que para todos os , sempre que houver um caminho de para emλ V L < L G λ G V v = v 1 , , v n i j v i v j G i < j S l = λ ( v 1 ) , , λ ( v n ) | V | l < LEX l iG=(V,E)λVeu<euGλGVv=v1,...,vnEujvEuvjG , então devemos ter . O rótulo dessa classificação topológica é a sequência de elementos de obtidos como . A ordem lexicográfica dessas seqüências (todas com comprimento ) é definida como se houver alguma posição tal que e para todos os . Preste atenção ao fato de que cada etiqueta em pode ser atribuída a vários vértices em (caso contrário, o problema é trivial).Eu<jSeu=λ(v1),...,λ(vn)|V|eu<LEXeuEu l j = l j j < i S VeuEu<eueuEueuj=eujj<EuSV

Esse problema pode ser declarado em uma variante de computação ("calcular a classificação topológica lexicograficamente mínima") ou em uma variante de decisão ("essa palavra de entrada é a classificação topológica mínima?"). Minha pergunta é: qual é a complexidade desse problema ? Está em PTIME (ou em FP, para a variante de computação) ou é NP-difícil? Se o problema geral for difícil para o NP, também estou interessado na versão em que o conjunto de possíveis rótulos é corrigido com antecedência (ou seja, existe apenas um número constante de rótulos possíveis).S

Observações:

Aqui está um pequeno exemplo do mundo real para motivar o problema. Podemos ver o DAG como representando tarefas de um projeto (com um relacionamento de dependência entre eles) e os rótulos são números inteiros que representam o número de dias que cada tarefa leva. Para concluir o projeto, levarei a mesma quantidade total de tempo, independentemente da ordem que eu escolher para as tarefas. No entanto, gostaria de impressionar meu chefe e, para fazer isso, quero concluir o maior número possível de tarefas o mais rápido possível (de maneira gananciosa, mesmo que isso signifique ser muito lento no final, porque as tarefas mais difíceis permanecem). A escolha do pedido lexicograficamente mínimo otimiza o seguinte critério: Desejo escolher um pedido tal que não exista outro pedido e vários dias depois deO ' n n O ' O n O ' m < n o ' ooonndias, eu teria terminado mais tarefas com a ordem que com a ordem (ou seja, se meu chefe olha o tempo , dou uma melhor impressão com ), mas, apesar de todos os eu não concluí menos tarefas com a ordem que com a ordem .oonom<noo

Para dar uma idéia do problema: Eu já sei pelas respostas anteriores que o seguinte problema relacionado é difícil: "existe um tipo topológico que atinge a seguinte sequência"? No entanto, o fato de eu querer uma sequência mínima para essa ordem lexicográfica parece restringir muito as possíveis ordens topológicas que podem alcançá-la (em particular, as reduções nessas outras respostas não parecem mais funcionar). Intuitivamente, há muito menos situações em que temos uma escolha a fazer.

Observe que parece haver reformulações interessantes dos problemas em termos de cobertura de conjuntos (ao restringir o problema a DAGs bipartidos, ou seja, com altura dois): dado um conjunto de conjuntos, enumere-os na ordem que minimiza lexicograficamente a sequência,,, ,. O problema também pode ser reformulado em gráficos não direcionados (expanda progressivamente uma área conectada do gráfico seguindo a ordem que minimiza a sequência lexicográfica dos rótulos descobertos). No entanto, devido ao fato de a sequência terS1,...,Sn|S1||S2S1||S3(S1S2)|...|Sn(S1Sn1)| Para ser ganancioso o tempo todo, por definição da ordem lexicográfica, não consigo obter reduções (por exemplo, da árvore Steiner) para funcionar.

Agradecemos antecipadamente por suas idéias!

a3nm
fonte

Respostas:

12

Com várias cópias da mesma etiqueta permitidas, o problema é NP-rígido, através da redução de cliques em gráficos. Dado um gráfico no qual você deseja encontrar uma classe k , faça um DAG com um vértice de origem para cada vértice de GGkG , um vértice de afundamento para cada aresta de e uma aresta direcionada x y sempre que x for um vértice de G que forma um ponto final da aresta y . Dê aos vértices de G o valor do rótulo 1 e as bordas de G o valor do rótulo 0 .GxyxGyG1G0

Então, existe uma classe em G se, e somente se, a primeira ordem topológica lexicograficamente formar uma sequência de k 1 's e ' s, com seguindo th . Por exemplo, uma camarilha de seis vértices seria representada pela sequência . Essa é a menor seqüência lexicograficamente que poderia começar uma ordem topológica de um DAG rotulado fornecida por essa construção (substituindo qualquer um dos porkGk 1(k2) 0i1 0i111010010001000010000010daria uma sequência com mais arestas do que seria possível encontrar em um gráfico simples com tantos vértices) e só pode ser o início de uma ordenação topológica quando contém a camarilha desejada.G

David Eppstein
fonte
Oh, eu não tinha pensado em panelinhas. É uma boa redução, muito obrigado! Portanto, isso mostra que o problema de computação é difícil de NP, mesmo com o alfabeto de rótulo fixo ). Isso também implica que o problema de decisão "é a seqüência lexicograficamente menor que essa" também é difícil para NP (você pode usá-lo para calcular o mínimo com pesquisa binária). A única pergunta adicional que vejo é se o problema "é essa sequência exata de entrada, a mínima" também é difícil de NP. (Com isso, você não pode testar facilmente se a palavra mínima começa com um prefixo.) Você tem alguma idéia para essa? {0 0,1}
A3nm 14/07/2015
1
Minha suspeita é que o problema "é essa sequência exata possível" é NP-completo, mas não tenho uma redução em mãos. "Essa sequência exata é a mínima" deve estar no segundo nível da hierarquia polinomial, pois requer uma combinação de quantificação existencial (é possível) e quantificação universal (todas são seqüências possíveis, pelo menos, tão grandes).
David Eppstein
Na verdade, eu já sei que testar se uma sequência exata é viável é difícil para NP (em um alfabeto com 3 rótulos) por uma redução da partição 3 unária de Marzio de Biasi esboçada aqui: cstheory.stackexchange.com/a/19415 . Mas acho que isso não indica o status do problema "essa é a sequência mínima possível": quando perguntamos se uma determinada sequência é possível, em geral ela terá poucas chances de ser mínima em alguma ordem lexicográfica. De qualquer forma, o que sua redução mostra ainda é muito interessante, obrigado novamente! :)
a3nm
2

De acordo com essa referência (1), o primeiro problema de ordem topológica lexicograficamente é NLOG-completo.

Convém dar uma olhada mais aprofundada no artigo para garantir que ele cubra os casos em que você está interessado. Em particular, com base na versão do relatório técnico (pdf) desse artigo, parece que eles ' está tratando a ordenação lexicográfica dos vértices como estrita (por exemplo: em sua notação, para u v )), mas não tenho certeza se isso afeta a aplicabilidade do resultado.λ(você)λ(v)vocêv

  1. Shoudai, Takayoshi. " O primeiro problema de ordem topológica lexicograficamente é NLOG-completo. " Information processing letters 33.3 (1989): 121-124.
mhum
fonte
4
NLOG-complete é um subconjunto de tempo polinomial e, (pela sentença "Preste atenção" no primeiro parágrafo do problema), tornar os rótulos dos vértices distintos torna o problema facilmente solucionável por um algoritmo ganancioso em tempo polinomial. A verdadeira questão é o que acontece quando os rótulos não são distintos.
David Eppstein
Esse é um argumento justo. Agora está claro em sua resposta que a repetição de marcadores dificulta o problema do que no caso de marcadores exclusivos.
Mhum 14/07/2015