×

zbMATH — the first resource for mathematics

A general reduction theorem with applications to pathwidth and the complexity of Max 2-CSP. (English) Zbl 1328.68089
Summary: We prove a general reduction theorem which allows us to extend bounds for certain graph parameters on cubic graphs to bounds for general graphs taking into account the individual vertex degrees. As applications, we give an algorithm for Max 2-CSP whose complexity matches the algorithm of A. D. Scott and G. B. Sorkin [Discrete Optim. 4, No. 3–4, 260–287 (2007; Zbl 1153.90505)] in the case of \(d\) regular graphs, \(d \leq 5\), but is otherwise faster. It also improves on the previously fastest known algorithm in terms of the average degree, given by A. Golovnev and K. Kutzkov [Theor. Comput. Sci. 526, 18–27 (2014; Zbl 1290.68144)]. Also from the general theorem, we derive a bound for the pathwidth of a general graph which equals that of F. V. Fomin et al. [Algorithmica 54, No. 2, 181–207 (2009; Zbl 1185.68475)] and S. Gaspers [Exponential time algorithms: structures, measures, and bounds. Saarbrücken: VDM Verlag Dr. Mueller e.K. (2010)] for graphs of degree at most 6, but is smaller otherwise, and use this to give an improved exponential-space algorithm for Max 2-CSP. Finally we use the general result to give a faster algorithm for Max 2-CSP on claw-free graphs.

MSC:
68Q25 Analysis of algorithms and problem complexity
05C38 Paths and cycles
05C85 Graph algorithms (graph-theoretic aspects)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Software:
MAX-2-SAT
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Arnborg, S; Proskurowski, A; Corneil, DG, Forbidden minors characterization of partial 3-trees, Discret. Math., 80, 1-19, (1990) · Zbl 0701.05016
[2] Bansal, N., Raman, V.: Upper bounds for MAXSAT: further improved, in Algorithms and computation Chennai. Lecture Notes in Computer Science, vol. 1741, pp. 247-258. Springer, Berlin (1999) · Zbl 0971.68069
[3] Bodlaender, HL, A partial \(k\)-arboretum of graphs with bounded treewidth, Theor. Comput. Sci., 209, 1-45, (1998) · Zbl 0912.68148
[4] Cheng, C., McDermid, E., Suzuki, I.: Planarization and acyclic colorings of subcubic claw-free graphs. In: Kolman, P., Kratochvíl, J. (eds.) Graph-Theoretic Concepts in Computer Science, WG 2011 (Czech Republic, June 2011). Lecture Notes in Computer Science, vol. 6986, pp. 107-118. Springer, Berlin (2011) · Zbl 1341.05068
[5] de Fraysseix, H., Ossona de Mendez, P.: A characterization of DFS cotree critical graphs. In: Mutzel, P., Jünger, M., Leipert, S. (eds.) Graph Drawing 2001 (Vienna, 23-26 Sept. 2001), Lecture Notes in Computer Science, vol. 2265, pp. 84-95. Springer, Berlin (2002) · Zbl 1054.68608
[6] Della Croce, F; Kaminski, MJ; Paschos, VTH, An exact algorithm for MAX-CUT in sparse graphs, Oper. Res. Lett., 35, 403-408, (2007) · Zbl 1163.90767
[7] Edwards, KJ; Farr, GF, Fragmentability of graphs, J. Combin. Theory, 82, 30-37, (2001) · Zbl 1028.05054
[8] Edwards, KJ; Farr, GE, Improved upper bounds for planarization and series-parallelization of average degree bounded graphs, Electron. J. Comb., 19, #p25, (2010) · Zbl 1243.05066
[9] Edwards, K.J., Farr, G.E.: Graph fragmentability. In: Beineke, L.W., Wilson, R.J. (eds.) Topics in Structural Graph Theory, Encyclopedia of Mathematics and its Applications No. 147, pp. 203-218, Cambridge University Press, Cambridge (2013). ISBN 978-0-521-80231-4
[10] Fomin, FV; Gaspers, S; Saurabh, S; Stepanov, AA, On two techniques of combining branching and treewidth, Algorithmica, 54, 181-207, (2009) · Zbl 1185.68475
[11] Fomin, FV; Grandoni, F; Kratsch, D, A measure & conquer approach for the analysis of exact algorithms, J. ACM, 56, 1-32, (2009) · Zbl 1325.68311
[12] Fomin, FV; Høie, K, Pathwidth of cubic graphs and exact algorithms, Inf. Process. Lett., 97, 191-196, (2006) · Zbl 1191.68826
[13] Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms. Springer, Texts in Theoretical Computer Science (2010). ISBN 978-3-642-16533-7 · Zbl 1370.68002
[14] Gaspers, S.: Exponential Time Algorithms: Structures, Measures, and Bounds. VDM Verlag Dr. Mueller e.K., 2010. ISBN 978-3-639-21825-1
[15] Gaspers, S; Sorkin, GB, A universally fastest algorithm for MAX 2-sat, MAX 2-CSP, and everything in between, J. Comput. Syst. Sci., 78, 305-335, (2012) · Zbl 1238.68066
[16] Golovnev, A.: New upper bounds for MAX-2-SAT and MAX-2-CSP w.r.t. the average variable degree. In: Parameterized and exact computation, Lecture Notes in Computer Science, vol. 7112, pp. 106-117. Springer, Heidelberg (1973) · Zbl 1352.68107
[17] Golovnev, A; Kutzkov, K, New exact algorithms for the 2-constraint satisfaction problem, Theor. Comput. Sci., 526, 18-27, (2014) · Zbl 1290.68144
[18] Gramm, J; Hirsch, EA; Niedermeier, R; Rossmanith, P, Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT, Discret. Appl. Math., 130, 139-155, (2003) · Zbl 1051.68078
[19] Haxell, P; Pikhurko, O; Thomason, A, Maximum acyclic and fragmented sets in regular graphs, J. Graph Theory, 57, 149-156, (2008) · Zbl 1131.05050
[20] Hirsch, E.A.: A new algorithm for MAX-2-SAT, in: STACS 2000 (Lille), Lecture Notes in Computer Science, vol. 1770, pp. 65-73. Springer, Berlin (2000) · Zbl 0959.68047
[21] Kneis, J; Mölle, D; Richter, S; Rossmanith, P, A bound on the pathwidth of sparse graphs with applications to exact algorithms, SIAM J. Discret. Math., 23, 407-427, (2009) · Zbl 1219.05187
[22] Kojevnikov, A., Kulikov, A.S.: A new approach to proving upper bounds for MAX-2-SAT. In: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms 2006, pp. 11-17. ACM, New York (2006) · Zbl 1192.68368
[23] Kulikov, A.S., Kutzkov, K.: New bounds for MAX-SAT by clause learning, in: Proceedings of the 2nd International Symposium on Computer Science in Russia (CSR 2007), Lecture Notes in Computer Science, vol. 4649, pp. 194-204. Springer (2007) · Zbl 1188.68272
[24] Niedermeier, R; Rossmanith, P, New upper bounds for maximum satisfiability, J. Algorithms, 36, 63-88, (2000) · Zbl 0959.68049
[25] Raible, D., Fernau, H.: A new upper bound for Max-2-SAT: a graph-theoretic approach. In: Mathematical foundations of computer science 2008, Lecture Notes in Computer Science, vol. 5162, pp. 551-562. Springer, Berlin, (2008) · Zbl 1173.68539
[26] Robson, J.M.: Finding a maximum independent set in time \(O(2^{n/4})\). Technical Report 1251-01, LaBRI, Université Bordeaux I (2001)
[27] Scott, AD; Sorkin, GB, Linear-programming design and analysis of fast algorithms for MAX 2-CSP, Discret. Optim., 4, 260-287, (2007) · Zbl 1153.90505
[28] Scott, AD; Sorkin, GB, Polynomial constraint satisfaction problems, graph bisection, and the Ising partition functio, ACM Trans. Algorithms, 5, 45, (2009) · Zbl 1298.68256
[29] Williams, R.: A new algorithm for optimal constraint satisfaction and its implications. In: J. Díaz et al. (eds.), Proc. 31st International Colloquium on Automata, Languages and Programming (ICALP) (Turku, Finland, 2004), Lecture Notes in Computer Science, vol. 3142, pp. 1227-1237. Springer (2004) · Zbl 1098.68120
[30] Woeginger, G.J.: Exact algorithms for NP-hard problems: a survey. In: Combinatorial optimization-Eureka, you shrink!, Lecture Notes in Computer Science vol. 2570, pp. 185-207. Springer (2003) · Zbl 1024.68529
[31] Woeginger, GJ, Open problems around exact algorithms, Discret. Appl. Math., 156, 397-405, (2008) · Zbl 1165.90613
[32] Xiao, M., Nagamochi, H.: Exact algorithms for maximum independent set. In: L. Cai, S.-W. Cheng, and T.-W. Lam (eds.), ISAAC2013, Lecture Notes in Computer Science, vol. 8283, pp. 328-338. Springer (2013) · Zbl 1406.68047
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.