Abstract
We show a method resulting in the improvement of several polynomial-space, exponential-time algorithms. The method capitalizes on the existence of small balanced separators for sparse graphs, which can be exploited for branching to disconnect an instance into independent components. For this algorithm design paradigm, the challenge to date has been to obtain improvements in worst-case analyses of algorithms, compared with algorithms that are analyzed with advanced methods, such as Measure and Conquer. Our contribution is the design of a general method to integrate the advantage from the separator-branching into Measure and Conquer, for an improved running time analysis.
We illustrate the method with improved algorithms for Max \((r,2)\)-CSP and #Dominating Set. For Max \((r,2)\)-CSP instances with domain size r and m constraints, the running time improves from \({r}^{m/6}\) to \({r}^{m/7.5}\) for cubic instances and from \({r}^{0.19\cdot m}\) to \({r}^{0.18\cdot m}\) for general instances, omitting subexponential factors. For #Dominating Set instances with n vertices, the running time improves from \({1.4143}^{n}\) to \({1.2458}^{n}\) for cubic instances and from \({1.5673}^{n}\) to \({1.5183}^{n}\) for general instances. It is likely that other algorithms relying on local transformations can be improved using our method, which exploits a non-local property of graphs.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Achlioptas, D., Sorkin, G.B.: Optimal myopic algorithms for random 3-SAT. In: Proc. FOCS 2000, pp. 590–600 (2000)
Alekhnovich, M., Hirsch, E.A., Itsykson, D.: Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas. J. Autom. Reasoning 35(1–3), 51–72 (2005)
Biere, A., Sinz, C.: Decomposing SAT problems into connected components. JSAT 2(1–4), 201–208 (2006)
Dechter, R., Mateescu, R.: And/or search spaces for graphical models. Artif. Intell. 171(2–3), 73–106 (2007)
Diestel, R.: Graph Theory. Springer (2010)
Edwards, K., McDermid, E.: A general reduction theorem with applications to pathwidth and the complexity of MAX 2-CSP. Algorithmica. (to appear)
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., Grandoni, F., Kratsch, D.: A measure & conquer approach for the analysis of exact algorithms. J. ACM 56(5) (2009)
Fomin, F.V.: Høie, K.: Pathwidth of cubic graphs and exact algorithms. Inform. Process. Lett. 97(5), 191–196 (2006)
Fomin, F.V., Lokshtanov, D., Misra, N., Saurabh, S.: Planar F-deletion: approximation, kernelization and optimal FPT algorithms. In: Proc. FOCS 2012, pp. 470–479 (2012)
Freuder, E.C., Quinn, M.J.: Taking advantage of stable sets of variables in constraint satisfaction problems. In: Proc. IJCAI 1985, pp. 1076–1078 (1985)
Gaspers, S.: Exponential Time Algorithms - Structures, Measures, and Bounds. VDM (2010)
Gaspers, S., Sorkin, G.B.: A universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything in between. J. Comput. System Sci. 78(1), 305–335 (2012)
Gaspers, S., Sorkin, G.B.: Separate, Measure and Conquer: Faster algorithms for Max 2-CSP and counting dominating sets (2014). arXiv:1404.0753 [cs.DS]
Gaspers, S., Szeider, S.: Strong backdoors to bounded treewidth SAT. In: Proc. FOCS 2013, pp. 489–498 (2013)
Golovnev, A., Kutzkov, K.: New exact algorithms for the 2-constraint satisfaction problem. Theor. Comput. Sci. 526, 18–27 (2014)
Gottlob, G., Leone, N., Scarcello, F.: A comparison of structural CSP decomposition methods. Artif. Intell. 124(2), 243–282 (2000)
Kim, E.J., Langer, A., Paul, C., Reidl, F., Rossmanith, P., Sau, I., Sikdar, S.: Linear kernels and single-exponential algorithms via protrusion decompositions. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013, Part I. LNCS, vol. 7965, pp. 613–624. Springer, Heidelberg (2013)
Kneis, Joachim, Mölle, Daniel, Richter, Stefan, Rossmanith, Peter: Algorithms based on the treewidth of sparse graphs. In: Kratsch, Dieter (ed.) WG 2005. LNCS, vol. 3787, pp. 385–396. Springer, Heidelberg (2005)
Li, W., van Beek, P.: Guiding real-world SAT solving with dynamic hypergraph separator decomposition. In: Proc. ICTAI 2004, pp. 542–548 (2004)
Lipton, R.J., Tarjan, R.E.: Application of a planar separator theorem. In: Proc. FOCS 1977, pp. 162–170 (1977)
Monien, B., Preis, R.: Upper bounds on the bisection width of 3- and 4-regular graphs. J. Discrete Algorithms 4(3), 475–498 (2006)
Nederlof, J., van Rooij, J.M.M., van Dijk, T.C.: Inclusion/exclusion meets measure and conquer. Algorithmica 69(3), 685–740 (2014)
Scott, A.D., Sorkin, G.B.: Solving sparse random instances of Max Cut and Max 2-CSP in linear expected time. Comb. Probab. Comput. 15(1–2), 281–315 (2006)
Scott, A.D., Sorkin, G.B.: Linear-programming design and analysis of fast algorithms for Max 2-CSP. Discrete Optim. 4(3–4), 260–287 (2007)
Scott, A.D., Sorkin, G.B.: Polynomial constraint satisfaction problems, graph bisection, and the Ising partition function. ACM Trans. Algorithms 5(4), Art. 45, 27 (2009)
van Rooij, J.M.M.: Polynomial space algorithms for counting dominating sets and the domatic number. In: Calamoneri, T., Diaz, J. (eds.) CIAC 2010. LNCS, vol. 6078, pp. 73–84. Springer, Heidelberg (2010)
van Rooij, J.M.M., Nederlof, J., van Dijk, T.C.: Inclusion/exclusion meets measure and conquer. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol. 5757, pp. 554–565. Springer, Heidelberg (2009)
Xiao, M., Nagamochi, H.: Confining sets and avoiding bottleneck cases: A simple maximum independent set algorithm in degree-3 graphs. Theor. Comput. Sci. 469, 92–104 (2013)
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
Gaspers, S., Sorkin, G.B. (2015). Separate, Measure and Conquer: Faster Polynomial-Space Algorithms for Max 2-CSP and Counting Dominating Sets. In: Halldórsson, M., Iwama, K., Kobayashi, N., Speckmann, B. (eds) Automata, Languages, and Programming. ICALP 2015. Lecture Notes in Computer Science(), vol 9134. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-47672-7_46
Download citation
DOI: https://doi.org/10.1007/978-3-662-47672-7_46
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-47671-0
Online ISBN: 978-3-662-47672-7
eBook Packages: Computer ScienceComputer Science (R0)