×
Brightwell, Graham

On the complexity of diagram testing. (English) Zbl 0808.06003

Order 10, No. 4, 297-303 (1993).
Summary: J. Nešetřil and V. Rödl [ibid. 3, 321-330 (1987; see the review below)] claim to have proved that the problem of finding whether a given graph \(G\) can be oriented as the diagram of a partial order is NP-complete. A flaw was discovered in their proof by J. Thostrup [Partially ordered sets and graphs (Danish), MSc. Diss., Odense Univ. (1992)]. J. Nešetřil and V. Rödl [“More on complexity of diagrams”, submitted to Order] have since corrected the proof, but the new version is rather complex. We give a simpler and more elementary proof, using a completely different approach.

Cited in 16 Documents

MSC:

06A06 Partial orders, general
68Q25 Analysis of algorithms and problem complexity
05C75 Structural characterization of families of graphs

Keywords:

orientation; NP-completeness; finite poset; diagram
PDFBibTeX XMLCite
\textit{G. Brightwell}, Order 10, No. 4, 297--303 (1993; Zbl 0808.06003)
Full Text: DOI

References:

[1] M. R. Garey and D. S. Johnson (1979)Computers and Intractability: A Guide to the Theory of NP-completeness, Freeman. · Zbl 0411.68039
[2] C. Lund and M. Yannakakis (1993) On the hardness of approximating minimization problems, in25th ACM Symposium on the Theory of Computing, pp. 286-293. · Zbl 1310.68094
[3] K. M. Mosesian (1972) Certain theorems on strongly basable graphs [Russian],Akad. Nauk Armian. SSR Dokl. 55, 83-86.
[4] J. Ne?et?il and V. R?dl (1987) Complexity of diagrams,Order 3, 321-330. · Zbl 0808.06004 · doi:10.1007/BF00340774
[5] J. Ne?et?il and V. R?dl, More on complexity of diagrams, submitted toOrder.
[6] O. Ore (1962)Theory of Graphs, AMS Coll. Publ.34, Providence, RI. · Zbl 0105.35401
[7] O. Pretzel (1985) On graphs that can be oriented as diagrams of ordered sets,Order 2, 25-40. · Zbl 0571.05041 · doi:10.1007/BF00337921
[8] O. Pretzel (1986) On reorienting graphs by pushing down maximal vertices,Order 3, 135-153. · Zbl 0611.05028 · doi:10.1007/BF00390104
[9] O. Pretzel (1986) Orientations and reorientations of graphs,Cont. Math. 57, 103-125. · Zbl 0595.06005
[10] O. Pretzel and D. Youngs (1991) Balanced graphs and noncovering graphs,Disc. Math. 88, 279-287. · Zbl 0764.05095 · doi:10.1016/0012-365X(91)90015-T
[11] J. Thostrup (1992) Partial ordered sets and graphs (in Danish), MSc. dissertation, Odense University, Denmark, 56 pp.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.