A partial order or poset P=(X, <) on a (finite) base set X determines the set L(P) of linear extensions of P. The problem of computing, for a poset P, the cardinality of L(P) is #P-complete. A set {P 1 ,P 2 , ... ,P k } of posets on X covers the set of linear orders that is the union of the L(P i ) . Given linear orders L 1 ,L 2 , ... ,L m on X, the Poset Cover problem is to determine the smallest number of posets that cover { L 1 ,L 2 , ... ,L m} . Here, we show that the decision version of this problem is NP -complete. On the positive side, we explore the use of cover relations for finding posets that cover a set of linear orders and present a polynomial-time algorithm to find a partial poset cover.
B. S. Baker and E. G. Coffman, “Mutual Exclusion Scheduling,” Theoretical Computer Science, Vol. 162, No. 2, 1996, pp. 225-243. doi:10.1016/0304-3975(96)00031-X
P. Barcia and J. O. Cerdeira, “The k-Track Assignment Problem on Partial Orders,” Journal of Scheduling, Vol. 8, No. 2, 2005, pp. 135-143. doi:10.1007/s10951-005-6363-6
F. A. Chudak and D. B. Shmoys, “Approximation Algorithms for Precedence-Constrained Scheduling Problems on Parallel Machines That Run at Different Speeds,” Journal of Algorithms, Vol. 30, No. 2, 1999, pp. 323-343. doi:10.1006/jagm.1998.0987
J. R. Correa and A. S. Schulz, “Single-Machine Scheduling with Precedence Constraints,” Mathematics of Operations Research, Vol. 30, No. 4, 2005, pp. 1005-1021. doi:10.1287/moor.1050.0158
T. Kis, “Job-Shop Scheduling with Processing Alternatives,” European Journal of Operational Research, Vol. 151, No. 2, 2003, pp. 307-332. doi:10.1016/S0377-2217(02)00828-7
M. Peter and G. Wambach, “n-Extendible Posets, and How to Minimize Total Weighted Completion Time,” Discrete Applied Mathematics, Vol. 99, No. 1-3, 2000, pp. 157-167. doi:10.1016/S0166-218X(99)00131-6
N. Policella, A. Oddi, S. F. Smith and A. Cesta, “Generating Robust Partial Order Schedules,” Proceedings of Principles and Practice of Constraint Programming, Vol. 3258, 2004, pp. 496-511.
D. B. Shmoys, C. Stein and J. Wein, “Improved Approximation Algorithms for Shop Scheduling Problems,” SIAM Journal on Computing, Vol. 23, No. 3, 1994, pp. 617-632. doi:10.1137/S009753979222676X
C. Grasso and C. Lee, “Combining Partial Order Alignment and Progressive Multiple Sequence Alignment Increases Alignment Speed and Scalability to Very Large Alignment Problems,” Bioinformatics, Vol. 20, No. 10, 2004, pp. 1546-1556. doi:10.1093/bioinformatics/bth126
S. K. Kannan and T. J. Warnow, “Tree Reconstruction from Partial Orders,” SIAM Journal on Computing, Vol. 24, No. 3, 1995, pp. 511-519. doi:10.1137/S0097539793252195
S. Karlin and I. Ladunga, “Comparisons of Eukaryotic Genomic Sequences,” Proceedings of the National Academy of Sciences of the United States of America, Vol. 91, No. 26, 1994, pp. 12832-12836. doi:10.1073/pnas.91.26.12832
K. Miyakawa and H. Narushima, “Lattice-Theoretic Properties of MPR-Posets in Phylogeny,” Discrete Applied Mathematics, Vol. 134, No. 1-3, 2004, pp. 169-192. doi:10.1016/S0166-218X(03)00303-2
P. L. Hammer, A. Kogan and M. A. Lejeune, “Modeling Country Risk Ratings Using Partial Orders,” European Journal of Operational Research, Vol. 175, No. 2, 2006, pp. 836-859. doi:10.1016/j.ejor.2005.06.040
S. Holland and W. Kiessling, “User Preference Mining Techniques for Personalized Applications,” Wirtschaftsinformatik, Vol. 46, No. 6, 2004, pp. 439-445. doi:10.1007/BF03250961
S. Holland, M. Ester and W. Kiessling, “Preference Mining: A Novel Approach on Mining User Preferences for Personalized Applications,” Proceedings of Knowledge Discovery in Databases: PKDD 2003, Vol. 2838, 2003, pp. 204-216.
H. Mannila, H. Toivonen and A. I. Verkamo, “Discovery of Frequent Episodes in Event Sequences,” Data Mining and Knowledge Discovery, Vol. 1, No. 3, 1997, pp. 259-289. doi:10.1023/A:1009748302351
J. Pei, H. X. Wang, J. Liu, K. Wang, J. Y. Wang, and P. S. Yu, “Discovering Frequent Closed Partial Orders from Strings,” IEEE Transactions on Knowledge and Data Engineering, Vol. 18, No. 11, 2006, pp. 1467-1481. doi:10.1109/TKDE.2006.172
B. Bollobas and G. Brightwell, “The Structure of Random Graph Orders,” SIAM Journal on Discrete Mathematics, Vol. 10, No. 2, 1997, pp. 318-335. doi:10.1137/S0895480194281215
S. Felsner and K. Reuter, “The Linear Extension Diameter of a Poset,” SIAM Journal on Discrete Mathematics, Vol. 12, No. 3, 1999, pp. 360-373. doi:10.1137/S0895480197326139
S. Felsner and W. T. Trotter, “Posets and Planar Graphs,” Journal of Graph Theory, Vol. 49, No. 4, 2005, pp. 273-284. doi:10.1002/jgt.20081
P. C. Fishburn, P. J. Tanenbaum and A. N. Trenk, “Linear Discrepancy and Bandwidth,” Order, Vol. 18, No. 3, 2001, pp. 237-245. doi:10.1023/A:1012267732204
L. S. Heath and S. V. Pemmaraju, “Stack and Queue Layouts of Posets,” SIAM Journal on Discrete Mathematics, Vol. 10, No. 4, 1997, pp. 599-625. doi:10.1137/S0895480193252380
M. Naatz, “The Graph of Linear Extensions Revisited,” SIAM Journal on Discrete Mathematics, Vol. 13, No. 3, 2000, pp. 354-369. doi:10.1137/S0895480199352609
G. Agnarsson, S. Felsner and W. T. Trotter, “The Maximum Number of Edges in a Graph of Bounded Dimension, with Applications to Ring Theory,” Discrete Mathematics, Vol. 201, No. 1-3, 1999, pp. 5-19. doi:10.1016/S0012-365X(98)00309-4
M. Aguiar and W. F. Santos, “Galois Connections for Incidence Hopf Algebras of Partially Ordered Sets,” Advances in Mathematics, Vol. 151, No. 1, 2000, pp. 71-100. doi:10.1006/aima.1999.1864
N. Bergeron and F. Sottile, “Hopf Algebras and Edge-Labeled Posets,” Journal of Algebra, Vol. 216, No. 2, 1999, pp. 641-651. doi:10.1006/jabr.1998.7794
J. Konieczny, “Reduced Idempotents in the Semigroup of Boolean Matrices,” Journal of Symbolic Computation, Vol. 20, No. 4, 1995, pp. 471-482. doi:10.1006/jsco.1995.1059
F. Ruskey, “Generating Linear Extensions of Posets by Transpositions,” Journal of Combinatorial Theory Series B, Vol. 54, No. 1, 1992, pp. 77-101. doi:10.1016/0095-8956(92)90067-8
D. B. West, “Generating Linear Extensions by Adjacent Transpositions,” Journal of Combinatorial Theory Series B, Vol. 58, No. 1, 1993, pp. 58-64. doi:10.1006/jctb.1993.1031
G. Pruesse and F. Ruskey, “Generating Linear Extensions Fast,” SIAM Journal on Computing, Vol. 23, No. 2, 1994, pp. 373-386. doi:10.1137/S0097539791202647
E. R. Canfield and S. G. Williamson, “A Loop-Free Algorithm for Generating the Linear Extensions of a Poset,” Order, Vol. 12, No. 1, 1995, pp. 57-75.
J. F. Korsh and P. S. LaFollette, “Loopless Generation of Linear Extensions of a Poset,” Order, Vol. 19, No. 2, 2002, pp. 115-126. doi:10.1023/A:1016548222238
A. Ono and S. Nakano, “Constant Time Generation of Linear Extensions,” Proceedings of Fundamentals of Computational Theory, Vol. 3623, 2005, pp. 445-453.
R. Bubley and M. Dyer, “Faster Random Generation of Linear Extensions,” Discrete Mathematics, Vol. 201, No. 1-3, 1999, pp. 81-88. doi:10.1016/S0012-365X(98)00333-1
P. L. Fernandez, L. S. Heath, N. Ramakrishnan, M. Tan and J. P. C. Vergara, “Mining Posets from Linear Orders,” Discrete Mathematics, Algorithms and Applications, 2013, in press.
P. L. Fernandez, L. S. Heath, N. Ramakrishnan and J. P. C. Vergara, “Reconstructing Partial Orders from Linear Extensions,” Proceedings of the Fourth SIGKDD Workshop on Temporal Data Mining: Network Reconstruction from Dynamic Data, Philadelphia, 20 August 2006, p. 4.
A. K. Lee and M. A. Wilson, “A Combinatorial Method for Analyzing Sequential Firing Patterns Involving an Arbitrary Number of Neurons Based on Relative Time Order,” Journal of Neurophysiology, Vol. 92, No. 4, 2004, pp. 2555-2573. doi:10.1152/jn.01030.2003
B. A. Davey and H. A. Priestley, “Introduction to Lattices and Order,” 2nd Edition, Cambridge University Press, Cambridge, 2002. doi:10.1017/CBO9780511809088
G. Brightwell and P. Winkler, “Counting Linear Extensions,” Order, Vol. 8, No. 3, 1991, pp. 225-242. doi:10.1007/BF00383444
M. R. Garey, D. S. Johnson and L. Stockmeyer, “Some Simplified NP-Complete Graph problems,” Theoretical Computer Science, Vol. 1, No. 3, 1976, pp. 237-267. doi:10.1016/0304-3975(76)90059-1
T. M. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, “Introduction to Algorithms,” 2nd Edition, The MIT Press, Cambridge, 2001.