Abstract
The input of the Tropical Connected Set problem is a vertex-colored graph \(G=(V,E)\) and the task is to find a connected subset \(S\subseteq V\) of minimum size such that each color of \(G\) appears in \(S\). This problem is known to be NP-complete, even when restricted to trees of height at most three. We show that Tropical Connected Set on trees has no subexponential-time algorithm unless the Exponential Time Hypothesis fails. This motivates the study of exact exponential algorithms to solve Tropical Connected Set. We present an \(\mathcal {O}^*(1.5359^n)\) time algorithm for general graphs and an \(\mathcal {O}^*(1.2721^n)\) time algorithm for trees.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Abu-Khzam, F.N., Mouawad, A.E., Liedloff, M.: An exact algorithm for connected red-blue dominating set. J. Discret. Algorithm. 9(3), 252–262 (2011)
Ambalath, A.M., Balasundaram, R., Rao H., C., Koppula, V., Misra, N., Philip, G., Ramanujan, M.S.: On the kernelization complexity of colorful motifs. In: Raman, V., Saurabh, S. (eds.) IPEC 2010. LNCS, vol. 6478, pp. 14–25. Springer, Heidelberg (2010)
Angles D’Auriac, J.-A., Cohen, N., El Maftouhi, A., Harutyunyan, A., Legay, S., Manoussakis, Y.: Connected tropical subgraphs in vertex-colored graphs. http://people.maths.ox.ac.uk/harutyunyan/Tropical%20sets.pdf
Betzler, N., Van Bevern, R., Fellows, M.R., Komusiewicz, C., Niedermeier, R.: Parameterized algorithmics for finding connected motifs in biological networks. IEEE/ACM Trans. Comput. Biol. Bioinf. 8(5), 1296–1308 (2011)
Bruckner, S., Hüffner, F., Karp, R.M., Shamir, R., Sharan, R.: Topology-free querying of protein interaction networks. J. Comput. Biol. 17(3), 237–252 (2010)
Courcelle, B.: The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inf. Comput. 85, 12–75 (1990)
Demaine, E.D., Hajiaghayi, M.T.: The bidimensionality theory and its algorithmic applications. Comput. J. 51, 292–302 (2008)
Dondi, R., Fertin, G., Vialette, S.: Complexity issues in vertex-colored graph pattern matching. J. Discret. Algorithm. 9(1), 82–99 (2011)
Fellows, M.R., Fertin, G., Hermelin, D., Vialette, S.: Sharp tractability borderlines for finding connected motifs in vertex-colored graphs. In: Arge, L., Cachin, C., Jurdziński, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol. 4596, pp. 340–351. Springer, Heidelberg (2007)
Fellows, M.R., Fertin, G., Hermelin, D., Vialette, S.: Upper and lower bounds for finding connected motifs in vertex-colored graphs. J. Comput. Syst. Sci. 77(4), 799–811 (2011)
Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms. Springer, Heidelberg (2010)
Fomin, F.V., Kratsch, D., Woeginger, G.J.: Exact (Exponential) algorithms for the dominating set problem. In: Hromkovič, J., Nagl, M., Westfechtel, B. (eds.) WG 2004. LNCS, vol. 3353, pp. 245–256. Springer, Heidelberg (2004)
Fomin, F.V., Thilikos, D.M.: A simple and fast approach for solving problems on planar graphs. In: Diekert, V., Habib, M. (eds.) STACS 2004. LNCS, vol. 2996, pp. 56–67. Springer, Heidelberg (2004)
Guillemot, S., Sikora, F.: Finding and counting vertex-colored subtrees. Algorithmica 65(4), 828–844 (2013)
Impagliazzo, R., Paturi, R.: On the complexity of k-SAT. J. Comput/Syst. Sci. 62, 367–375 (2001)
Lacroix, V., Fernandes, C.G., Sagot, M.-F.: Motif search in graphs: application to metabolic networks. IEEE/ACM Trans. Comput. Biol. Bioinf. 3(4), 360–368 (2006)
McMorris, F., Warnow, T., Wimer, T.: Triangulating vertex-colored graphs. SIAM J. Discret. Math. 7, 296–306 (1994)
Nederlof, J.: Fast polynomial-space algorithms using Inclusion-Exclusion. Algorithmica 65, 868–884 (2013)
Scott, J., Ideker, T., Karp, R.M., Sharan, R.: Efficient algorithms for detecting signaling pathways in protein interaction networks. J. Comput. Biol. 13, 133–144 (2006)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Chapelle, M., Cochefert, M., Kratsch, D., Letourneur, R., Liedloff, M. (2014). Exact Exponential Algorithms to Find a Tropical Connected Set of Minimum Size. In: Cygan, M., Heggernes, P. (eds) Parameterized and Exact Computation. IPEC 2014. Lecture Notes in Computer Science(), vol 8894. Springer, Cham. https://doi.org/10.1007/978-3-319-13524-3_13
Download citation
DOI: https://doi.org/10.1007/978-3-319-13524-3_13
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-13523-6
Online ISBN: 978-3-319-13524-3
eBook Packages: Computer ScienceComputer Science (R0)