×

Exploiting a hypergraph model for finding Golomb rulers. (English) Zbl 1360.68520

Summary: Golomb rulers are special rulers where for any two marks it holds that the distance between them is unique. They find applications in radio frequency selection, radio astronomy, data encryption, communication networks, and bioinformatics. An important subproblem in constructing “compact” Golomb rulers is Golomb Subruler (GSR), which asks whether it is possible to make a given ruler Golomb by removing at most \(k\) marks. We initiate a study of GSR from a parameterized complexity perspective. In particular, we consider a natural hypergraph characterization of rulers and investigate the construction and structure of the corresponding hypergraphs. We exploit their properties to derive polynomial-time data reduction rules that reduce a given instance of GSR to an equivalent one with \(\mathrm{O}(k^3)\) marks. Finally, we complement a recent computational complexity study of GSR by providing a simplified reduction that shows NP-hardness even when all integers are bounded by a polynomial in the input length.

MSC:

68Q25 Analysis of algorithms and problem complexity
05C65 Hypergraphs
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abu-Khzam, F.N.: A kernelization algorithm for \[d\] d-hitting set. J. Comput. Syst. Sci. 76(7), 524-531 (2010) · Zbl 1197.68083 · doi:10.1016/j.jcss.2009.09.002
[2] Alon, N., Babai, L., Itai, A.: A fast and simple randomized parallel algorithm for the maximal independent set problem. J. Algorithms 7(4), 567-583 (1986) · Zbl 0631.68063 · doi:10.1016/0196-6774(86)90019-2
[3] Babcock, W.: Intermodulation interference in radio systems. Bell Syst. Tech. J. 32, 63-73 (1953) · doi:10.1002/j.1538-7305.1953.tb01422.x
[4] Bertram-Kretzberg, C., Lefmann, H.: The algorithmic aspects of uncrowded hypergraphs. SIAM J. Comput. 29(1), 201-230 (1999) · Zbl 0937.68056 · doi:10.1137/S0097539797323716
[5] Bloom, G., Golomb, S.: Applications of numbered undirected graphs. Proc. IEEE 65(4), 562-570 (1977) · doi:10.1109/PROC.1977.10517
[6] Blum, E., Biraud, F., Ribes, J.: On optimal synthetic linear arrays with applications to radioastronomy. IEEE Trans. Antennas Propag. 22, 108-109 (1974) · doi:10.1109/TAP.1974.1140732
[7] Bodlaender, H.L.: Kernelization: new upper and lower bound techniques. In: Proceedings of the 4th International Workshop on Parameterized and Exact Computation (IWPEC ’09). Lecture Notes in Computer Science, vol. 5917, pp. 17-37. Springer, Berlin (2009) · Zbl 1448.68465
[8] Cotta, C., Dotú, I., Fernández, A.J., Hentenryck, P.V.: Local search-based hybrid algorithms for finding Golomb rulers. Constraints 12, 263-291 (2007) · Zbl 1211.90194 · doi:10.1007/s10601-007-9020-1
[9] Dell, H., van Melkebeek, D.: Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. In: Proceedings of the 42th Annual ACM Symposium on Theory of Computing (STOC ’10), pp. 251-260. ACM. Journal version to appear in Journal of the ACM (2010) · Zbl 1293.68132
[10] Dimitromanolakis, A.: Analysis of the Golomb Ruler and the Sidon Set Problems, and Determination of Large, Near-Optimal Golomb Rulers. Master’s thesis, Department of Electronic and Computer Engineering, Technical University of Crete (2002) · Zbl 0909.68088
[11] Distributed.net. Home page. http://www.distributed.net/. Accessed May 2014 · Zbl 1228.05154
[12] Dollas, A., Rankin, W.T., McCracken, D.: A new algorithm for Golomb ruler derivation and proof of the 19 mark ruler. IEEE Trans. Inf. Theory 44(1), 379-382 (1998) · Zbl 0909.68088 · doi:10.1109/18.651068
[13] Dom, M., Guo, J., Hüffner, F., Niedermeier, R., Truss, A.: Fixed-parameter tractability results for feedback set problems in tournaments. J. Discrete Algorithms 8(1), 76-86 (2010) · Zbl 1191.68349 · doi:10.1016/j.jda.2009.08.001
[14] Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Springer, Berlin (2013) · Zbl 1358.68006 · doi:10.1007/978-1-4471-5559-1
[15] Drakakis, K.: A review of the available construction methods for Golomb rulers. Adv. Math. Commun. 3(3), 235-250 (2009) · Zbl 1226.05057 · doi:10.3934/amc.2009.3.235
[16] Fellows, M.R., Jansen, B.M.P., Rosamond, F.A.: Towards fully multivariate algorithmics: Parameter ecology and the deconstruction of computational complexity. Eur. J. Comb. 34(3), 541-566 (2013) · Zbl 1448.68465 · doi:10.1016/j.ejc.2012.04.008
[17] Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Heidelberg (2006)
[18] Guo, J., Niedermeier, R.: Invitation to data reduction and problem kernelization. ACM SIGACT News 38(1), 31-45 (2007) · doi:10.1145/1233481.1233493
[19] Komusiewicz, C., Niedermeier, R., Uhlmann, J.: Deconstructing intractability—a multivariate complexity analysis of interval constrained coloring. J. Discrete Algorithms 9(1), 137-151 (2011) · Zbl 1228.05154 · doi:10.1016/j.jda.2010.07.003
[20] Lokshtanov, D., Misra, N., Saurabh, S.: Kernelization—preprocessing with a guarantee. In: The Multivariate Algorithmic Revolution and Beyond—Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday. Lecture Notes in Computer Science, vol. 7370, pp. 129-161. Springer, Berlin (2012) · Zbl 1358.68141
[21] Malakonakis, P., Sotiriades, E., Dollas, A.: GE3: a single FPGA client-server architecture for Golomb ruler derivation. In: Proceedings of the International Conference on Field-Programmable Technology (FPT ’10), pp. 470-473. IEEE (2010)
[22] Meyer, C., Papakonstantinou, P.A.: On the complexity of constructing Golomb rulers. Discrete Appl. Math. 157, 738-748 (2008) · Zbl 1186.68221 · doi:10.1016/j.dam.2008.07.006
[23] Nicolas, F., Rivals, E.: Longest common subsequence problem for unoriented and cyclic strings. Theor. Comput. Sci. 370(1-3), 1-18 (2007) · Zbl 1118.68074 · doi:10.1016/j.tcs.2006.10.002
[24] Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, Oxford (2006) · Zbl 1095.68038 · doi:10.1093/acprof:oso/9780198566076.001.0001
[25] Niedermeier, R.: Reflections on multivariate algorithmics and problem parameterization. In: Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science (STACS ’10), volume 5 of Dagstuhl Seminar Proceedings, pp. 17-32. IBFI Dagstuhl, Germany (2010) · Zbl 1230.68096
[26] Pereira, F., Tavares, J., Costa, E.: Golomb rulers: the advantage of evolution. In: Proceedings of the 11th Portuguese Conference on Artificial Intelligence (EPIA ’03). Lecture Notes in Computer Science, vol. 2902, pp. 29-42. Springer, Berlin (2003)
[27] Rankin, W.T.: Optimal Golomb rulers: An Exhaustive Parallel Search Implementation. Master’s thesis, Department of Electrical Engineering, Duke University, Durham. Addendum by Aviral Singh (1993) · Zbl 1186.68221
[28] Soliday, S.W., Homaifar, A., Lebby, G.L.: Genetic algorithm approach to the search for Golomb rulers. In: Proceedings of the 6th International Conference on Genetic Algorithms (ICGA ’95), pp. 528-535. Morgan Kaufmann, Burlington (1995)
[29] Sorge, M.: Algorithmic Aspects of Golomb Ruler Construction. Studienarbeit, Institut für Informatik, Friedrich-Schiller-Universität Jena, Germany, 2010. Available electronically. arXiv:1005.5395v2 · Zbl 1228.05154
[30] Sorge, M., Moser, H., Niedermeier, R., Weller, M.: Exploiting a hypergraph model for finding Golomb rulers. In: Proceedings of the 2nd International Symposium on Combinatorial Optimization (ISCO ’12). Lecture Notes in Computer Science, vol. 7422, pp. 368-379. Springer, Berlin (2012) · Zbl 1360.68519
[31] Tavares, J., Pereira, F., Costa, E.: Golomb rulers: a fitness landscape analysis. In: Proceedings of the IEEE Congress on Evolutionary Computation (CEC ’08), pp. 3695-3701. IEEE (2008)
[32] van Bevern, R.: Towards optimal and expressive kernelization for \[d\] d-hitting set. Algorithmica (2013) · Zbl 1364.68237
[33] von zur Gathen, J., Sieveking, M.: A bound on solutions of linear integer equations and inequalities. Proc. Am. Math. Soc. 72, 155-158 (1978) · Zbl 0397.90071 · doi:10.1090/S0002-9939-1978-0500555-0
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.