Exact Algorithms for Exact Satisfiability and Number of Perfect Matchings

Springer Science and Business Media LLC - Tập 52 - Trang 226-249 - 2007
Andreas Björklund1, Thore Husfeldt1
1Department of Computer Science, Lund University, Lund, Sweden

Tóm tắt

We present exact algorithms with exponential running times for variants of n-element set cover problems, based on divide-and-conquer and on inclusion–exclusion characterizations. We show that the Exact Satisfiability problem of size l with m clauses can be solved in time 2 m l O(1) and polynomial space. The same bounds hold for counting the number of solutions. As a special case, we can count the number of perfect matchings in an n-vertex graph in time 2 n n O(1) and polynomial space. We also show how to count the number of perfect matchings in time O(1.732 n ) and exponential space. We give a number of examples where the running time can be further improved if the hypergraph corresponding to the set cover instance has low pathwidth. This yields exponential-time algorithms for counting k-dimensional matchings, Exact Uniform Set Cover, Clique Partition, and Minimum Dominating Set in graphs of degree at most three. We extend the analysis to a number of related problems such as TSP and Chromatic Number.

Tài liệu tham khảo

Angelsmark, O., Thapper, J.: Partitioning based algorithms for some colouring problems. In: Recent Advances in Constraints. Lecture Notes in Artificial Intelligence, vol. 3978, pp. 44–58. Springer, Berlin (2005)

Bax, E.T.: Inclusion and exclusion algorithm for the Hamiltonian Path problem. Inf. Process. Lett. 47(4), 203–207 (1993)

Björklund, A., Husfeldt, T. Koivisto, M.: Set partitioning via inclusion–exclusion. SIAM J. Comput., to appear. Prelim. versions in Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, Berkeley, CA, 21–24 October 2006, pp. 575–582, 583–590. IEEE Computer Society, Los Alamitos, CA (2006)

Bodlaender, H., Kratsch, D.: An exact algorithm for graph coloring with polynomial memory. Technical report UU-CS-2006-015, Utrecht University (2006)

Byskov, J.M.: Enumerating maximal independent sets with applications to graph colouring. Oper. Res. Lett. 32, 547–556 (2004)

Byskov, J.M.: Exact algorithms for graph colouring and exact satisfiability. Ph.D. thesis, University of Aarhus (2004)

Byskov, J.M., Madsen, B.A., Skjernaa, B.: New algorithms for Exact Satisfiability. Theor. Comput. Sci. 332(1–3), 515–541 (2005)

Chien, S.: A determinant-based algorithm for counting perfect matchings in a general graph. In: Proc. 15th SODA, pp. 728–735 (2004)

Christofides, N.: An algorithm for the chromatic number of a graph. Comput. J. 14, 38–39 (1971)

Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic progressions. J. Symb. Comput. 9(3), 251–280 (1990)

Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, New York (1999). ISBN 0-387-94883-X

Dahllöf, V., Jonsson, P., Beigel, R.: Algorithms for four variants of exact satisfiability. Theor. Comput. Sci. 320(2–3), 373–394 (2004)

Davis, M., Logemann, G., Loveland, D.: A machine program for theorem proving. Commun. ACM 5(7), 394–397 (1962)

Eppstein, D.: Small maximal independent sets and faster exact graph coloring. J. Graph Algorithms Appl. 7(2), 131–140 (2003)

Fomin, F.V., Grandoni, F., Kratsch, D.: Some new techniques in design and analysis of exact (exponential) algorithms. In: Bull. EATCS, vol. 87 (2005)

Fomin, F.V., Grandoni, F., Kratsch, D.: Measure and conquer: domination—a case study. In: Proceedings of the 32nd ICALP, pp. 191–203 (2005)

Fomin, F.V., Höie, K.: Pathwidth of cubic graphs and exact algorithms. Inf. Process. Lett. 97(5), 191–196 (2006)

Feder, T., Motwani, R.: Worst-case time bounds for coloring and satisfiability problems. J. Algorithms 45(2), 192–201 (2002)

Feige, U., Kilian, J.: Exponential time algorithms for computing the bandwidth of a graph. Manuscript. Cited in [38]

Gurevich, Y., Shelah, S.: Expected computation time for Hamiltonian path problem. SIAM J. Comput. 16(3), 486–502 (1987)

Hujter, M., Tuza, Z.: On the number of maximal independent sets in triangle-free graphs. SIAM J. Discrete Math. 6(2), 284–288 (1993)

Jerrum, M., Sinclair, A., Vigoda, E.: A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries. In: Proc. 33rd STOC, pp. 712–721 (2001)

Karp, R.M.: Dynamic programming meets the principle of inclusion-exclusion. Oper. Res. Lett. 1, 49–51 (1982)

Kohn, S., Gottlieb, A., Kohn, M.: A generating function approach to the Traveling Salesman Problem. In: ACM ’77: Proceedings of the 1977 annual conference, pp. 294–300. ACM Press, New York (1977)

Kneis, J., Mölle, D., Richter, S., Rossmanith, P.: Algorithms based on the treewidth of sparse graphs. In: Proceedings of the 31st International Workshop on Graph-Theoretic Concepts in Computer Science, pp. 385–396 (2005)

Lawler, E.L.: A note on the complexity of the chromatic number problem. Inf. Process. Lett. 5(3), 66–67 (1976)

Lovász, L., Plummer, M.D.: Matching Theory. North-Holland, Amsterdam (1986)

Madsen, B.A.: An algorithm for exact satisfiability analysed with the number of clauses as parameter. Inf. Process. Lett. 97(1), 28–30 (2006)

Moon, J.W., Moser, L.: On cliques in graphs. Isr. J. Math. (1965)

Monien, B., Speckenmeyer, E., Vornberger, O.: Upper bounds for covering problems. Methods Oper. Res. 43, 419–431 (1981)

Porschen, S.: On some weighted satisfiability and graph problems. In: Proc. 31st SOFSEM. Lecture Notes in Computer Science, vol. 3381, pp. 278–287 (2005)

Ryser, H.J.: Combinatorial Mathematics. Carus Math. Monographs, no. 14. Math. Assoc. of America, Washington, DC (1963)

Tsukiyama, S., Ide, M., Ariyoshi, H., Shirakawa, I.: A new algorithm for generating all the maximal independent sets. SIAM J. Comput. 6(3), 505–517 (1977)

Vadhan, S.P.: The complexity of counting in sparse, regular, and planar graps. SIAM J. Comput. 32(2), 398–427 (2001)

Valiant, L.G.: The complexity of computing the permanent. Theor. Comput. Sci. 8, 189–201 (1979)

Williams, R.: A new algorithm for optimal 2-constraint satisfaction and its implications. Theor. Comput. Sci. 348(1–2), 357–365 (2005)

Woeginger, G.J.: Exact algorithms for NP-hard problems: a survey. In: Combinatorial Optimization: Eureka, You Shrink!, pp. 185–207. Springer, Berlin (2003)

Woeginger, G.J.: Space and time complexity of exact algorithms: Some open problems. In: Proc. 1st IWPEC. Lecture Notes in Computer Science, vol. 3162, pp. 281–290 (2004)

Thông tin
Thông tin xuất bản

Springer Science and Business Media LLC

Tập 52

226-249

Thông tin tác giả