Generalização do teorema de Dilworth para DAGs rotulados

Um antichain em um DAG é um subconjunto de vértices que são emparelhados inacessível, ou seja, não há nenhum tal que é acessível a partir de em . Do teorema de Dilworth na teoria de ordem parcial, sabe-se que se o DAG não possui antichain de tamanho , ele pode ser decomposto em uma união de no máximo cadeias disjuntas, ou seja, caminhos direcionados. $(V, E)$ $A \subseteq V$ $v \neq v' \in A$ $v$ $v'$ $E$ $k \in \mathbb{N}$ $k-1$

$v$ $\lambda(v)$ $\Sigma$ $A \subseteq V$ $\Sigma$ $A$ $\min_{a \in \Sigma} |\{v \in A \mid \lambda(v) = a\}|$ $k \in \mathbb{N}$ , o que posso assumir sobre sua estrutura? Posso decompor de alguma maneira especial? Eu já estou intrigado com o caso de , mas também estou interessado no caso de um conjunto de rótulos finitos gerais. $\Sigma = \{a, b\}$

Visualizar isso para , dizer que não possui antichain de tamanho rotulado significa que não há antichain contendo pelo menos vértices rotulados e vértices rotulados ; pode haver antichains arbitrariamente grandes, mas eles devem conter apenas elemento ou apenas elementos , até no máximo exceções . Parece que não permitindo grandes antichains deve impor que a DAG essencialmente "suplentes" entre partes de grande largura de vértices marcados com, e grande largura de $\Sigma = \{a, b\}$ $G$ $k$ $k$ $a$ $k$ $b$ $a$ $b$ $k-1$ $a$ $b$ com vértices, mas não pude formalizar essa intuição. (Obviamente, uma caracterização estrutural adequada deve falar sobre os rótulos dos vértices, além da forma do DAG, porque já para e em a condição é satisfeita por DAGs completamente arbitrários sempre que todos os vértices têm o mesmo rótulo.) $k \geq 1$ $\{a, b\}$

reference-request graph-theory directed-acyclic-graph partial-order a3nm
fonte

@ Saeed, Não, isso não funciona. Sua confusão vem do fato de que, se uma letra não aparecer em um antichain, seu tamanho será . Tomemos, por exemplo, um gráfico bipartido completo G = (A, B, E), cada aresta orientada de A a B. Rotule todos os vértices de A com e todos os vértices de B com . Então cada antichain tem no máximo uma cor e, portanto, possui o tamanho , mas você não pode cobri-lo com cadeias disjuntas. Mesmo com um DAG que você rotular com única.

0

$0$

a

$a$

b

$b$

0

$0$

m (k - 1)

$m(k-1)$

a

$a$

Holf

@holf, certo, eu pensei em contar sobre os rótulos onde eles aparecem no antichain, eu não percebi que min abrange todos os elementos do sigma. Eu acho que é uma definição um pouco estranha.

Saeed #

@Saeed: O objetivo é proibir antichains com uma grande variedade de símbolos. A intuição para isso é que estamos estudando a complexidade de um problema nos DAGs, que se torna trivial quando você tem um grande número de cadeias (ocorrências suficientes de símbolos incomparáveis). Para mostrar a rastreabilidade geral, precisamos apenas lidar com o caso de DAGs onde esse padrão não ocorre, portanto, queremos descobrir como esses DAGs podem ser decompostos para projetar um algoritmo tratável para eles. (No caso não marcado, por exemplo, os fios de decomposição da cadeia a de um algoritmo de dinâmica.)

a3nm

Com Charles Paperman , conseguimos obter esse resultado para DAGs rotulados com o alfabeto . Essencialmente, pode-se mostrar que, dado um DAG que tem grandes antichains de elementos marcados com, grandes antichains de marcado com elementos, mas não há grandes antichains contendo tanto muitos marcado com e elementos marcados com, em seguida, existe uma decomposio de como uma partição , em que: $\{a, b\}$ $G$ $a$ $b$ $a$ $b$ $G$ $L_1, \ldots, L_n$

a partição é o que chamamos de "camadas", ou seja:
- cada é um conjunto convexa, isto é, se e , em seguida, $L_i$ $x, y \in L_i$ $x \leq z \leq y$ $z \in L_i$
- para todo , não há e tal forma que $i < j$ $x \in L_i$ $y \in L_j$ $y \leq x$
para qualquer antichain de , há alguns tais que está "quase contido" em , ou seja,é menor que uma constante $A$ $G$ $i$ $A$ $L_i$ $|A \setminus L_i|$
para cada , um dos seguintes é verdadeiro:
- $L_i$ contém uma grande antichain de elementos marcados com e não contém nenhum grande antichain de marcado com elementos $a$ $b$
- $L_i$ contém uma grande antichain de marcado com elementos, mas não contém nenhuma grande antichain de elementos marcados com $b$ $a$

Além disso, essa partição pode ser calculada em PTIME.

Publiquei nossa prova atual on-line . É muito difícil e, essencialmente, não é revisado porque não temos utilidade para o resultado no momento, mas eu ainda achava mais ordenado adicionar uma resposta a essa pergunta do CStheory com nosso progresso atual. Não hesite em entrar em contato comigo se estiver interessado no resultado, mas não conseguir entender a prova.

a3nm
fonte

Generalização do teorema de Dilworth para DAGs rotulados

Respostas: