11
$\begingroup$

An antichain in a DAG $(V, E)$ is a subset $A \subseteq V$ of vertices that are pairwise unreachable, namely, there are no $v \neq v' \in A$ such that $v$ is reachable from $v'$ in $E$. From Dilworth's theorem in partial order theory, it is known that if DAG has no antichain of size $k \in \mathbb{N}$, then it can be decomposed in a union of at most $k-1$ disjoint chains, i.e., directed paths.

Now, I am interested in labeled DAGs, i.e., DAGs where each vertex $v$ carries a label $\lambda(v)$ in some fixed finite set $\Sigma$ of labels. Given an antichain $A \subseteq V$, I can define its labeled size as the minimal number of occurrences of the labels of $\Sigma$ in $A$, namely, $\min_{a \in \Sigma} |\{v \in A \mid \lambda(v) = a\}|$. Is there an analogue of Dilworth's theorem in this context? In other words, if I assume that a DAG has no antichain of labeled size $k \in \mathbb{N}$, what can I assume about its structure? Can I decompose it in some special way? I am already puzzled by the case of $\Sigma = \{a, b\}$, but also interested in the case of a general finite label set.

To visualize this for $\Sigma = \{a, b\}$, saying that $G$ has no antichain of labeled size $k$ means that there is no antichain containing at least $k$ vertices labeled $a$ and $k$ vertices labeled $b$; there can be arbitrarily large antichains but they have to contain only $a$ elements or only $b$ elements, up to $k-1$ exceptions at most. It seems that disallowing large antichains should enforce that the DAG essentially "alternates" between parts of large width for $a$-labeled vertices, and large width for $b$-labeled vertices, but I have not been able to formalize this intuition. (Of course, a suitable structural characterization must talk about the labels of vertices in addition to the shape of the DAG, because already for $k \geq 1$ and on $\{a, b\}$ the condition is satisfied by completely arbitrary DAGs whenever all vertices carry the same label.)

$\endgroup$
  • 1
    $\begingroup$ @Saeed, No this does not work. Your confusion comes from the fact that if a letter does not appear in an antichain, then its labeled size is $0$. Take for example a complete bipartite graph G = (A,B,E), every edge oriented from A to B. Label every vertex of A with $a$ and every vertex of B with $b$. Then each antichain has at most one color in it and thus is of labeled size $0$, but you can't cover it with $m(k-1)$ disjoint chains. Same with a DAG that you label with $a$ only. $\endgroup$ – holf Nov 29 '16 at 15:19
  • $\begingroup$ @holf, right, I thought we count over labels where they appear in the antichain, I didn't notice min goes over all elements of sigma. I think It's a bit strange definition. $\endgroup$ – Saeed Nov 30 '16 at 7:17
  • $\begingroup$ @Saeed: The point is to disallow antichains with a large variety of symbols. The intuition for this is that we are studying the complexity of a problem on DAGs, which becomes trivial when you have such large antichains (sufficiently many occurrences of incomparable symbols). To show overall tractability we just need to handle the case of DAGs where this pattern doesn't occur, so we want to figure out how such DAGs can be decomposed to design a tractable algorithm for them. (In the unlabeled case, for instance, the chain decomposition leads to a dynamic algorithm.) $\endgroup$ – a3nm Nov 30 '16 at 10:53
7
$\begingroup$

With Charles Paperman we have been able to obtain such a result for DAGs labeled with the alphabet $\{a, b\}$. Essentially, we can show that given a DAG $G$ that has large antichains of $a$-labeled elements, large antichains of $b$-labeled elements, but no large antichains containing both many $a$-labeled and $b$-labeled elements, then there is a decomposition of $G$ as a partition $L_1, \ldots, L_n$, where:

  • the partition $L_1, ..., L_n$ is what we call a "layering", i.e.:
    • each $L_i$ is a convex set, i.e., if $x, y \in L_i$ and $x \leq z \leq y$ then $z \in L_i$
    • for all $i < j$, there is no $x \in L_i$ and $y \in L_j$ such that $y \leq x$
  • for any antichain $A$ of $G$, there is some $i$ such that $A$ is "almost contained" in $L_i$, i.e., $|A \setminus L_i|$ is less than a constant
  • for each $L_i$, one of the following is true:
    • $L_i$ contains a large antichain of $a$-labeled elements and contains no large antichain of $b$-labeled elements
    • $L_i$ contains a large antichain of $b$-labeled elements but contains no large antichain of $a$-labeled elements

Further, such a partition can be computed in PTIME.

I have posted our current proof online. It's very rough and essentially not proofread because we have no use for the result for now, but I still thought it was tidier to add an answer to this CStheory question with our current progress. Don't hesitate to get in touch with me if you're interested in the result but can't make sense of the proof.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.