Abstract
We introduce a multivariate approach for solving weighted parameterized problems. Building on the flexible use of certain parameters, our approach defines a new general framework for applying the classic bounded search trees technique. In our model, given an instance of size n of a minimization/maximization problem, and a parameter W ≥ 1, we seek a solution of weight at most/at least W. We demonstrate the wide applicability of our approach by solving the weighted variants of Vertex Cover, 3-Hitting Set, Edge Dominating Set and Max Internal Out-Branching. While the best known algorithms for these problems admit running times of the form a W n O(1), for some constant a > 1, our approach yields running times of the form b s n O(1), for some constant b ≤ a, where s ≤ W is the minimum size of a solution of weight at most (at least) W. If no such solution exists, s = min {W,m}, where m is the maximum size of a solution. Clearly, s can be substantially smaller than W. Moreover, we give an example for a problem whose polynomial-time solvability crucially relies on our flexible (in lieu of a strict) use of parameters.
We further show, among other results, that Weighted Vertex Cover and Weighted Edge Dominating Set are solvable in times 1.443t n O(1) and 3t n O(1), respectively, where t ≤ s is the minimum size of a solution.
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
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alon, N., Yuster, R., Zwick, U.: Color coding. J. ACM 42(4), 844–856 (1995)
Binkele-Raible, D., Fernau, H.: Enumerate and measure: Improving parameter budget management. In: Raman, V., Saurabh, S. (eds.) IPEC 2010. LNCS, vol. 6478, pp. 38–49. Springer, Heidelberg (2010)
Chen, J., Fomin, F.V., Liu, Y., Lu, S., Villanger, Y.: Improved algorithms for feedback vertex set problems. J. Comput. Syst. Sci. 74(7), 1188–1198 (2008)
Chen, J., Kanj, I.A., Jia, W.: Vertex cover: further observations and further improvements. J. Algorithms 41(2), 280–301 (2001)
Chen, J., Kanj, I.A., Xia, G.: Improved upper bounds for vertex cover. Theor. Comput. Sci. 411(40-42), 3736–3756 (2010)
Chlebìk, M., Chlebìovà, J.: Crown reductions for the minimum weighted vertex cover problem. Discrete Appl. Math. 156(3), 292–312 (2008)
Cygan, M.: Deterministic parameterized connected vertex cover. In: Fomin, F.V., Kaski, P. (eds.) SWAT 2012. LNCS, vol. 7357, pp. 95–106. Springer, Heidelberg (2012)
Cygan, M., Lokshtanov, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Minimum bisection is fixed parameter tractable. In: STOC, pp. 323–332 (2014)
Daligault, J.: Combinatorial techniques for parameterized algorithms and kernels, with ppplications to multicut. PhD thesis, Universite Montpellier, France (2011)
Demaine, E.D., Hajiaghayi, M., Marx, D.: Open problems from Dagstuhl Seminar 09511 (2010). http://drops.dagstuhl.de/opus/volltexte/2010/2499/pdf/09511.SWM.Paper.2499.pdf
Downey, R.G., Fellows, M.R.: Fundamentals of parameterized complexity. Springer (2013)
Fernau, H.: Parameterized algorithms for d-hitting set: the weighted case. Theor. Comput. Sci. 411(16-18), 1698–1713 (2010)
Fomin, F.V., Gaspers, S., Saurabh, S.: Branching and treewidth based exact algorithms. In: Asano, T. (ed.) ISAAC 2006. LNCS, vol. 4288, pp. 16–25. Springer, Heidelberg (2006)
Fomin, F.V., Gaspers, S., Saurabh, S., Stepanov, A.A.: On two techniques of combining branching and treewidth. Algorithmica 54(2), 181–207 (2009)
Fomin, F.V., Lokshtanov, D., Saurabh, S.: Efficient computation of representative sets with applications in parameterized and exact agorithms. In: SODA, pp. 142–151 (2014)
Hüffner, F., Wernicke, S., Zichner, T.: Algorithm engineering for color-coding with applications to signaling pathway detection. Algorithmica 52(2), 114–132 (2008)
Issac, D., Jaiswal, R.: An O*(1.0821n)-time algorithm for computing maximum independent set in graphs with bounded degree 3. CoRR abs/1308.1351 (2013)
Jansen, B.M.P., Bodlaender, H.L.: Vertex cover kernelization revisited – upper and lower bounds for a refined parameter. Theory Comput. Syst. 53(2), 263–299 (2013)
Knauer, M., Spoerhase, J.: Better approximation algorithms for the maximum internal spanning tree problem. In: Dehne, F., Gavrilova, M., Sack, J.-R., Tóth, C.D. (eds.) WADS 2009. LNCS, vol. 5664, pp. 459–470. Springer, Heidelberg (2009)
Niedermeier, R., Rossmanith, P.: On efficient fixed-parameter algorithms for weighted vertex cover. J. Algorithms 47(2), 63–77 (2003)
Salamon, G.: Approximation algorithms for the maximum internal spanning tree problem. Theor. Comput. Sci. 410(50), 5273–5284 (2009)
Shachnai, H., Zehavi, M.: A multivariate framework for weighted FPT algorithms. CoRR abs/1407.2033 (2014)
Shachnai, H., Zehavi, M.: Representative families: a unified tradeoff-based approach. In: Schulz, A.S., Wagner, D. (eds.) ESA 2014. LNCS, vol. 8737, pp. 786–797. Springer, Heidelberg (2014)
Sharan, R., Dost, B., Shlomi, T., Gupta, N., Ruppin, E., Bafna, V.: QNet: a tool for querying protein interaction networks. J. Comput. Biol. 15(7), 913–925 (2008)
Wahlström, M.: Algorithms, measures and upper bounds for satisfiability and related problems. Ph.D. thesis Linköpings universitet, Sweden (2007)
Xiao, M., Kloks, T., Poon, S.H.: New parameterized algorithms for the edge dominating set problem. Theor. Comput. Sci. 511, 147–158 (2013)
Xiao, M., Nagamochi, H.: Parameterized edge dominating set in graphs with degree bounded by 3. Theor. Comput. Sci. 508, 2–15 (2013)
Zehavi, M.: Algorithms for k-internal out-branching. In: Gutin, G., Szeider, S. (eds.) IPEC 2013. LNCS, vol. 8246, pp. 361–373. Springer, Heidelberg (2013)
Zehavi, M.: Mixing color coding-related techniniques. In: ESA (2015, to appear)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Shachnai, H., Zehavi, M. (2015). A Multivariate Approach for Weighted FPT Algorithms. In: Bansal, N., Finocchi, I. (eds) Algorithms - ESA 2015. Lecture Notes in Computer Science(), vol 9294. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-48350-3_80
Download citation
DOI: https://doi.org/10.1007/978-3-662-48350-3_80
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-48349-7
Online ISBN: 978-3-662-48350-3
eBook Packages: Computer ScienceComputer Science (R0)