Let $(P, <)$ be a finite partial order. Call a collection $\{C_1, \ldots C_k\}$ of (not necessarily disjoint) subsets of $P$ a covering of $(P, <)$ by maximal chains if:
- $P = \bigcup C_i$
- $\forall i, (C_i, <)$ is a maximal chain in $(P, <)$ (i.e. $C_i$ is not a proper subset of a chain in $P$)
My question is: is there an efficient algorithm (ideally polynomial in $|P|$) that, given a finite partial order $(P, <)$, finds a covering of $(P, <)$ by the smallest possible number of maximal chains?
Let $(P,<)$ be a finite partial order we define a DAG $G=(V,E)$ as follow: $V=P\cup\{\top,\bot\}$ where $\forall x\in p,x<\top$ and $\bot<x$. $E=\{(x,y)\mid x<y, \forall z\in E\setminus \{x,y\},\neg (x<z<y) \}$.
It is easy to show that $x<y$ if and only if there exists a path from $x$ to $y$ in $G$.
Thus, any maximal chain $C$ of $(P,<)$ is a subset of a path from $\bot$ to $\top$ in $G$. Moreover any path from $\bot$ to $\top$ is a maximal chain by definition of $E$.
Let $B_1...B_{k'}$ be a minimum path cover of $G$, and $C_1...C_k$ be a covering of $(P,<)$ by the smallest possible number of maximal chains.
Since the $B_i$ are maximal chains and form a covering of $P$ we have $k'\geq k$. Moreover since for all $C_i$ there exists $j_i$ such that $C_i\subseteq B_{j_i}$ and $N=\cup_{i\leq k} C_i=\cup_{i\leq k} B_{j_i}$ we have that $B_{j_1}...B_{j_k}$ is a path cover of $G$ and by minimality of $k'$ we have $k\geq k'$. Hence, $k=k'$.
Thus $B_1...B_{k'}$ is a solution of your problem.
Complexity
Computing $E$ can be done in $O(|P|^3)$ (test all triple $(x,z,y)$ to see if $(x,y)\in E$).
Computing a minimal paths cover of a DAG can be done in polynomial time (for DAG only, otherwise it is NP) see fore example wikipedia.
Thus we have a solution in Polynomial time.