Abstract
Finding subgraphs of small diameter in undirected graphs has been seemingly unexplored from a parameterized complexity perspective. We perform the first parameterized complexity study on the corresponding NP-hard s-Club problem. We consider two parameters: the solution size and its dual.
Article PDF
Similar content being viewed by others
References
Alba R.D.: A graph-theoretic definition of a sociometric clique. J. Math. Sociol. 3, 3–113 (1973)
Asahiro, Y., Miyano, E., Samizo K.: Approximating maximum diameter-bounded subgraphs. In: Proceedings of the 9th Latin American Theoretical Informatics Symposium (LATIN’10). Lecture Notes in Computer Science, vol. 6034, pp. 615–626. Springer, Berlin (2010)
Balasundaram B., Butenko S., Trukhanov S.: Novel approaches for analyzing biological networks. J. Comb. Optim. 10(1), 23–39 (2005)
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)
Bodlaender H.L., Downey R.G., Fellows M.R., Hermelin D.: On problems without polynomial kernels. J. Comput. Syst. Sci. 75(8), 423–434 (2009)
Bourjolly J., Laporte G., Pesant G.: Heuristics for finding k-clubs in an undirected graph. Comput. Oper. Res. 27(6), 559–569 (2000)
Bourjolly J., Laporte G., Pesant G.: An exact algorithm for the maximum k-club problem in an undirected graph. Eur. J. Oper. Res. 138(1), 21–28 (2002)
Butenko, S., Prokopyev, O.: On k-club and k-clique numbers in graphs. Technical report, Texas A and M University (2007)
Downey R.G., Fellows M.R.: Fixed-parameter tractability and completeness II: on completeness for W[1]. Theor. Comput. Sci. 141(1&2), 109–131 (1995)
Downey R.G., Fellows M.R.: Parameterized Complexity. Springer, Berlin (1999)
Fernau, H., Fomin, F.V., Lokshtanov, D., Raible, D., Saurabh, S., Villanger Y.: Kernel(s) for problems with no kernel: on out-trees with many leaves. In: Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS’09). LIPIcs, vol. 3, pp. 421–432. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Germany (2009)
Flum J., Grohe M.: Parameterized Complexity Theory. Springer, Berlin (2006)
Fortnow L., Santhanam R.: Infeasibility of instance compression and succinct pcps for np. J. Comput. Syst. Sci. 77(1), 91–106 (2011)
Guo J., Niedermeier R.: Invitation to data reduction and problem kernelization. ACM SIGACT News 38(1), 31–45 (2007)
Lokshtanov, D.: New Methods in Parameterized Algorithms and Complexity. PhD thesis, Universitetet i Bergen, Bergen, Norway (2009)
Marincek J., Mohar B.: On approximating the maximum diameter ratio of graphs. Discret. Math. 244(1–3), 323–330 (2002)
Memon, N., Kristoffersen, K.C., Hicks, D.L., Larsen H.L.: Detecting critical regions in covert networks: a case study of 9/11 terrorists network. In: Proceedings of the 2nd International Conference on Availability, Reliability and Security (ARES’07), pp. 861–870. IEEE Computer Society, Washington, DC (2007)
Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. In: Oxford Lecture Series in Mathematics and Its Applications, vol. 31. Oxford University Press, USA (2006)
Pasupuleti, S.: Detection of protein complexes in protein interaction networks using n-clubs. In: Proceedings of the 6th European Conference on Evolutionary Computation, Machine Learning and Data Mining in Bioinformatics (EvoBIO’08), volume 4973 of LNCS, pages 153–164. Springer, Berlin (2008)
Schäfer, A.: Exact algorithms for s-club finding and related problems, 2009. Diploma Thesis, Friedrich-Schiller-Universität Jena
Seidman S.B., Foster B.L.: A graph-theoretic generalization of the clique concept. J. Math. Sociol. 6, 139–154 (1978)
Author information
Authors and Affiliations
Corresponding author
Additional information
The main work for this article was done while all authors were with the Friedrich-Schiller-Universität Jena.
The results of this article are part of the first author’s diploma thesis [20].
Rights and permissions
About this article
Cite this article
Schäfer, A., Komusiewicz, C., Moser, H. et al. Parameterized computational complexity of finding small-diameter subgraphs. Optim Lett 6, 883–891 (2012). https://doi.org/10.1007/s11590-011-0311-5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11590-011-0311-5