×

Hardness results and spectral techniques for combinatorial problems on circulant graphs. (English) Zbl 0931.05050

Summary: We show that computing (and even approximating) MAXIMUM CLIQUE and MINIMUM GRAPH COLORING for circulant graphs is essentially as hard as in the general case. In constrast, we show that, under additional constraints, e.g., prime order and/or sparseness, GRAPH ISOMORPHISM and MINIMUM GRAPH COLORING become easier in the circulant case, and we take advantage of spectral techniques for their efficient computation.

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C15 Coloring of graphs and hypergraphs
05C85 Graph algorithms (graph-theoretic aspects)
15A18 Eigenvalues, singular values, and eigenvectors
68R10 Graph theory (including graph drawing) in computer science
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alon, N.; Kahale, N., A spectral technique for coloring random 3-colorable graphs, (Proceedings of The 26th Annual Symposium on the Theory of Computing. Proceedings of The 26th Annual Symposium on the Theory of Computing, New York (1994), ACM Press: ACM Press New York), 346-355 · Zbl 1345.05022
[2] Arora, S.; Lund, C.; Motwani, R.; Sudan, M.; Szegedy, M., Proof verification and hardness of approximation problems, (Proc. The 33rd IEEE Symposium on the Foundations of Computer Science (1992), IEEE Computer Society), 14-23 · Zbl 0977.68539
[3] Aspvall, B.; Gilbert, J. R., Graph coloring using eigenvalue decomposition, SIAM J. Algebraic Discrete Methods, 5, 4, 526-538 (1984) · Zbl 0554.05048
[4] Biggs, N. L., Algebraic Graph Theory (1974), Cambridge Univ. Press: Cambridge Univ. Press Cambridge · Zbl 0501.05039
[5] Bose, R. C.; Chowla, S. D., Theorems in additive theory of numbers, Comment. Math. Helv., 37, 141-147 (1963) · Zbl 0109.03301
[6] Cantor, D. G.; Kaltofen, E., On fast multiplication of polynomials over arbitrary algebras, Acta Inform., 28, 7, 693-701 (1991) · Zbl 0766.68055
[7] Chan, T. F., An optimal circulant preconditioner for Toeplitz systems, SIAM J. Sci. Statist. Comput., 9, 766-771 (1988) · Zbl 0646.65042
[8] Cvetković, D. M.; Doob, M.; Sachs, H., Spectra of Graphs (1978), Academic Press: Academic Press New York
[9] Håstad, J., Clique is hard to approximate within \(n^{1−ϵ}\), (Proceedings of The 37th IEEE Symposium on the Foundations of Computer Science (1996), IEEE Computer Society), 627-636
[10] Lund, C.; Yannakakis, M., On the hardness of approximating minimization problems, J. ACM, 41, 5, 960-981 (1991) · Zbl 0814.68064
[11] Minc, H., Permanental compounds and permanents of (0,1) circulants, Linear Algebra Appl., 86, 11-46 (1987) · Zbl 0608.15009
[12] Shoup, V., New algorithms for finding irriducible polynomials over finite fields, Math. Comp., 54, 189, 435-447 (1990) · Zbl 0712.11077
[13] Shparlinski, I. E., Computational and Algorithmic Problems in Finite Fields (1992), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht · Zbl 0846.11064
[14] Turner, J., Point-symmetric graphs with prime number of points, J. Combin. Theory, 3, 136-145 (1967) · Zbl 0161.20803
[15] Wilf, H. S., Spectral bounds for the clique and independence numbers of graphs, J. Combin. Theory Ser. B, 40, 113-117 (1986) · Zbl 0598.05047
[16] Winograd, S., On computing the discrete Fourier transform, Math. Comp., 32, 175-199 (1978) · Zbl 0374.68034
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.