Généralisation du théorème de Dilworth pour les DAG étiquetés

Un antichaîne dans un DAG est un sous - ensemble de sommets qui sont inaccessibles par paires, à savoir, il n'y a pas tel que est accessible à partir de dans . D'après le théorème de Dilworth dans la théorie de l'ordre partiel, on sait que si DAG n'a pas d'antichaîne de taille , alors il peut être décomposé en une union d'au plus chaînes disjointes, c'est-à-dire des chemins dirigés. $(V, E)$ $A \subseteq V$ $v \neq v' \in A$ $v$ $v'$ $E$ $k \in \mathbb{N}$ $k-1$

Maintenant, je m'intéresse aux DAG étiquetés , c'est-à-dire aux DAG où chaque sommet porte une étiquette dans un ensemble fini fixe d'étiquettes. Étant donné une antichaine , je peux définir sa taille étiquetée comme le nombre minimal d'occurrences des étiquettes de dans , à savoir,. Existe-t-il un analogue du théorème de Dilworth dans ce contexte? En d'autres termes, si je suppose qu'un DAG n'a pas d'antichain de taille étiquetée $v$ $\lambda(v)$ $\Sigma$ $A \subseteq V$ $\Sigma$ $A$ $\min_{a \in \Sigma} |\{v \in A \mid \lambda(v) = a\}|$ $k \in \mathbb{N}$ , que puis-je supposer de sa structure? Puis-je le décomposer d'une manière spéciale? Je suis déjà intrigué par le cas de $\Sigma = \{a, b\}$ , mais aussi intéressé par le cas d'un ensemble d'étiquettes finies générales.

Pour visualiser ceci pour , dire que n'a pas d'antichaîne de taille étiquetée signifie qu'il n'y a pas d'antichaîne contenant au moins sommets étiquetés et sommets étiquetés ; il peut être arbitrairement grand antichaînes mais ils doivent contenir seulement des éléments ou seulement éléments, jusqu'à exceptions au plus. Il semble qu'interdire grand antichaînes doit appliquer que le DAG essentiellement « alterne » entre les parties de grande largeur pour des sommets, et grande marqués au large pour $\Sigma = \{a, b\}$ $G$ $k$ $k$ $a$ $k$ $b$ $a$ $b$ $k-1$ $a$ $b$ -des sommets étiquetés, mais je n'ai pas pu formaliser cette intuition. (Bien sûr, une caractérisation structurelle appropriée doit parler des étiquettes des sommets en plus de la forme du DAG, car déjà pour et sur la condition est satisfaite par des DAG complètement arbitraires chaque fois que tous les sommets portent la même étiquette.) $k \geq 1$ $\{a, b\}$

reference-request graph-theory directed-acyclic-graph partial-order a3nm
la source

@Saeed, Non, cela ne fonctionne pas. Votre confusion vient du fait que si une lettre n'apparaît pas dans une antichaine, alors sa taille étiquetée est . Prenons par exemple un graphe bipartite complet G = (A, B, E), chaque arête orientée de A à B. Étiquetez chaque sommet de A avec et chaque sommet de B avec . Ensuite, chaque antichaine a au plus une couleur et est donc de taille , mais vous ne pouvez pas la couvrir avec chaînes disjointes. Même chose avec un DAG que vous étiquetez avec seul.

0

$0$

a

$a$

b

$b$

0

$0$

m (k - 1)

$m(k-1)$

a

$a$

holf

@holf, à droite, je pensais que nous comptions sur les étiquettes où elles apparaissent dans l'antichaîne, je n'ai pas remarqué que min passe en revue tous les éléments de sigma. Je pense que c'est une définition un peu étrange.

Saeed

@Saeed: Le but est d'interdire les antichaines avec une grande variété de symboles. L'intuition pour cela est que nous étudions la complexité d'un problème sur les DAG, qui devient trivial lorsque vous avez de si grandes antichaines (suffisamment d'occurrences de symboles incomparables). Pour montrer la tractabilité globale, nous avons juste besoin de gérer le cas des DAG où ce modèle ne se produit pas, nous voulons donc comprendre comment ces DAG peuvent être décomposés pour concevoir un algorithme traitable pour eux. (Dans le cas sans étiquette, par exemple, la décomposition en chaîne conduit à un algorithme dynamique.)

a3nm

Avec Charles Paperman, nous avons pu obtenir un tel résultat pour les DAG étiquetés avec l'alphabet . Essentiellement, nous pouvons montrer que , étant donné un DAG qui a un grand antichaînes d' des éléments marqués au , grand antichaînes de éléments marqué à , mais pas grand antichaînes contenant à la fois beaucoup marqué à et éléments marqués au , alors il y a une décomposition tant que partition , où: $\{a, b\}$ $G$ $a$ $b$ $a$ $b$ $G$ $L_1, \ldots, L_n$

la partition est ce que nous appelons une "superposition", c'est-à-dire:
- chaque est un ensemble convexe, c'est-à-dire si et puis $L_i$ $x, y \in L_i$ $x \leq z \leq y$ $z \in L_i$
- pour tout , il n'y a pas et tels que $i < j$ $x \in L_i$ $y \in L_j$ $y \leq x$
pour toute antichaine de , il y en a tel que est "presque contenu" dans , c'est-à-dire est inférieur à une constante $A$ $G$ $i$ $A$ $L_i$ $|A \setminus L_i|$
pour chaque , l'une des conditions suivantes est vraie:
- contient une grande antichaîne d' des éléments marquéslarge etcontient pas de antichaîne éléments marqué $L_i$ $a$ $b$
- contient une grande antichaîne de élémentsmaiscontient pas marquégrand antichaîne d' des éléments marqués $L_i$ $b$ $a$

De plus, une telle partition peut être calculée dans PTIME.

J'ai publié notre preuve actuelle en ligne . C'est très approximatif et essentiellement pas relu parce que nous n'avons aucune utilité pour le résultat pour l'instant, mais je pensais toujours qu'il était plus ordonné d'ajouter une réponse à cette question CStheory avec nos progrès actuels. N'hésitez pas à me contacter si vous êtes intéressé par le résultat mais ne pouvez pas donner un sens à la preuve.

a3nm
la source

Généralisation du théorème de Dilworth pour les DAG étiquetés

Réponses: