The complexity of cover graph recognition for some varieties of finite lattices. (English) Zbl 0840.06009
Summary: We address the following decision problem:
Instance: an undirected graph \(G\).
Problem: Is \(G\) a cover graph of lattice?
We prove that this problem is NP-complete. This extends results of Brightwell and of Nešetřil and Rödl. On the other hand, it follows from Alvarez theorem [L. R. Alvarez, Can. J. Math. 17, 923-932 (1965; Zbl 0173.51502)] that recognizing cover graphs of modular or distributive lattices is in P. An important tool in the proof of the first result is the following statement which may be of independent interest:
Given an integer \(l\), \(l \geq 3\), there exists an algorithm which for a graph \(G\) with \(n\) vertices yields, in time polynomial in \(n\), a graph \(H\) with the number of vertices polynomial in \(n\), and satisfying \(\text{girth} (H) \geq l\) and \(\chi (H) = \chi (G)\).
Instance: an undirected graph \(G\).
Problem: Is \(G\) a cover graph of lattice?
We prove that this problem is NP-complete. This extends results of Brightwell and of Nešetřil and Rödl. On the other hand, it follows from Alvarez theorem [L. R. Alvarez, Can. J. Math. 17, 923-932 (1965; Zbl 0173.51502)] that recognizing cover graphs of modular or distributive lattices is in P. An important tool in the proof of the first result is the following statement which may be of independent interest:
Given an integer \(l\), \(l \geq 3\), there exists an algorithm which for a graph \(G\) with \(n\) vertices yields, in time polynomial in \(n\), a graph \(H\) with the number of vertices polynomial in \(n\), and satisfying \(\text{girth} (H) \geq l\) and \(\chi (H) = \chi (G)\).
MSC:
| 06B05 | Structure theory of lattices |
| 68Q25 | Analysis of algorithms and problem complexity |
| 05C15 | Coloring of graphs and hypergraphs |
| 68R10 | Graph theory (including graph drawing) in computer science |
| 06B20 | Varieties of lattices |
Citations:
Zbl 0173.51502References:
| [1] | Alford, W. R., Greenville, A., and Pomerance, C. (1994) There are infinitely many Carmichael numbers,Annals Math. 140, 703-722. · Zbl 0816.11005 · doi:10.2307/2118576 |
| [2] | Alvarez, L. R. (1965) Undirected graphs realizable as graphs of modular lattices,Canad. J. Math. 17, 923-932. · Zbl 0173.51502 · doi:10.4153/CJM-1965-088-1 |
| [3] | Alon, N. and Spencer, J. (1992)The Probabilistic Method, Wiley, New York. · Zbl 0767.05001 |
| [4] | Birkhoff, G. (1963)Lattice Theory, Harvard University Press. · Zbl 0122.02101 |
| [5] | Brightwell, G. (1993) On the complexity of diagram testing,Order 10, 297-303. · Zbl 0808.06003 · doi:10.1007/BF01108825 |
| [6] | F?redi, Z. (May 1995)Universal Graphs, Emory University, Atlanta, GA. |
| [7] | Garey, M. R. and Johnson, D. S. (1979)Computers and Intractability ? A Guide to the Theory of NP-Completeness, W. H. Freeman and Co. · Zbl 0411.68039 |
| [8] | Lubotzky, A. (1994) Discrete groups, expanding graphs and invariant measures,Progress in Math. 125, Birkhauser. · Zbl 0826.22012 |
| [9] | Lubotzky, A., Phillips, R., and Sarnak, P. (1988) Ramanujan graphs,Combinatorica 8(3), 261-277. · Zbl 0661.05035 · doi:10.1007/BF02126799 |
| [10] | Lund, C. and Yannakakis, M. (1993)On the Hardness of Approximating Minimization Problems, 25th ACM STOC, 286-293. · Zbl 1310.68094 |
| [11] | Ne?et?il, J. and R?dl, V. (1987) Complexity of diagrams,Order 3, 321-330. · Zbl 0808.06004 · doi:10.1007/BF00340774 |
| [12] | Ne?et?il, J. and R?dl, V. (1993)More on Complexity of Diagrams, Manuscript. |
| [13] | Ore, O. (1962)Theory of Graphs, AMS Coll. Publ. 34, Providence, RI. · Zbl 0105.35401 |
| [14] | Pomerance, C., Private communication. |
| [15] | Rival, I. (1985) The diagram,Order 2, 101-104. · Zbl 0558.05059 · doi:10.1007/BF00337928 |
| [16] | Rival, I. (1985) The diagram, in I. Rival (ed.),Graphs and Order, NATO Advanced Institute in Graphs and Order, D. Reidel Publ. Co., Dordrecht, Holland, pp. 103-133. |
| [17] | Sauer, N. and Spencer, J. (1978)Edge Disjoint Placement of Graphs, JCTB25, 295-302. · Zbl 0417.05037 · doi:10.1016/0095-8956(78)90005-9 |
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.
