Uma pergunta sobre extensões lineares de pedidos parciais

Se você receber uma coleção de pedidos parciais, a classificação topológica informará se há uma extensão da coleção para um pedido total (uma extensão nesse caso é um pedido total consistente com cada um dos pedidos parciais).

Eu me deparei com uma variação:

Fixar um conjunto . Você recebe sequências de elementos desenhados a partir de sem repetição (as seqüências têm comprimento entre 1 e ). $V$ $\sigma_1, \ldots \sigma_k$ $V$ $|V|$

Existe uma maneira de fixar orientações para cada uma das seqüências (para frente ou para trás) para que a coleção resultante de cadeias (vista como uma ordem parcial) admita uma extensão?

Esse problema é conhecido?

Nota: A orientação é escolhida para uma sequência inteira. Portanto, se a sequência for , você pode mantê-la assim ou alternar para , mas não pode fazer mais nada. $1-2-4-5$ $5-4-2-1$

ds.algorithms reference-request order-theory Suresh Venkat
fonte

Se cada uma das seqüências tem o comprimento

, pode-se pensar em cada sequência como uma aresta não direcionada e estamos perguntando se um gráfico não direcionado pode ser orientado para ser um DAG - se não houver ciclo. Mas um algoritmo ganancioso também funciona. Comece com uma aresta e oriente-a arbitrariamente e continue o máximo que puder e, se ficar preso, sabe que não é possível. Você tentou isso para a sua variação? Parece que pode funcionar.

2

$2$

Chandra Chekuri

É, todo gráfico não direcionado pode ser orientado para ser um DAG. Basta escolher uma ordem dos vértices e usar essa ordem para orientar as arestas.

David Eppstein

Você está certo, é claro, eu não pensando direito.

Chandra Chekuri

Na minha variação, cada subsequência tem exatamente 4, então a resposta de Yury entra em ação. Minha única esperança neste momento é que as subsequências tenham uma estrutura muito especial e estejam relacionadas umas às outras, então talvez algo específico para o problema ajude. Mas não há martelo geral.

precisa

Respostas:

Se todas as sequências tiverem comprimento 3, o problema será conhecido como intermediação . Até o problema da intermediação é difícil para o NP. Nesse problema, recebemos um conjunto de vértices e um conjunto de restrições da forma entre e . Nosso objetivo é ordenar todos os vértices para maximizar o número de restrições satisfeitas. Opantry [1] provou que a versão de decisão deste problema é NP-difícil. Chor e Sudão [2] provaram que é difícil para o SNP. $u$ $v$ $w$

O algoritmo de aproximação mais conhecido para o problema, por Chor e Sudão, satisfaz 1/2 de todas as restrições se a instância for completamente satisfatória.

J. Opantry. Problema de Pedido Total, SIAM Journal on Computing , 8 (1): 111-114, fevereiro de 1979.

[2] B. Chor e M. Sudan. Uma abordagem geométrica da intermediação , SIAM Journal on Discrete Mathematics, 11 (4): 511-523, novembro de 1998.

Edições: esclareceu que a versão de decisão do problema é NP-hard.

Yury
fonte

Yury, isso significa que o problema de decisão sobre se todas as restrições podem ser satisfeitas também é difícil?

Chandra Chekuri

ϵ > 0

$\epsilon > 0$

1 - ϵ

$1-\epsilon$

1 / 3

$1/3$

1 / 3 + ε

$1/3+ \varepsilon$

O P T = 1 - ε

$OPT = 1 -\varepsilon$

ε > 0

$\varepsilon > 0$

| σ_{i} | = 3

$|\sigma_i| =3$

i

$i$

I

${\cal I}$

y_{i}

$y_i$

σ_{i}

$\sigma_i$

σ_{i}^{'}

$\sigma_i'$

y_{i}

$y_i$

σ_{i}

$\sigma_i$

I^{'}

${\cal I}'$

V \cup {y_{i}}

$V \cup\{y_i\}$

{σ_{i}^{'}}

$\{\sigma_i'\}$

I^{'}

${\cal I}'$

I

${\cal I}$

I

${\cal I}$

y_{i}

$y_i$

V

$V$

V

$V$

σ_{i}

$\sigma_i$

{y_{i}}

$\{y_i\}$