On the parameterized complexity of monotone and antimonotone weighted circuit satisfiability. (English) Zbl 1380.68228
Summary: We consider the weighted monotone and antimonotone satisfiability problems on normalized circuits of depth at most \(t \geq 2\), abbreviated \(\mathrm{WSAT}^+[t]\) and \(\mathrm{WSAT}^-[t]\), respectively, where the parameter under consideration is the weight of the sought satisfying assignment. These problems model the weighted satisfiability of monotone and antimonotone propositional formulas, and serve as the canonical problems in the definition of the parameterized complexity hierarchy. Moreover, several well-studied problems, including important graph problems, can be modeled as \(\mathrm{WSAT}^+[t]\) and \(\mathrm{WSAT}^-[t]\) problems in a straightforward manner.
We study the parameterized complexity of \(\mathrm{WSAT}^-[t]\) and \(\mathrm{WSAT}^+[t]\) with respect to the genus of the underlying circuit. We give tight results, and draw a map of the parameterized complexity of these problems with respect to the genus of the circuit. As a byproduct of our results, we obtain tight characterizations of the parameterized complexity of several problems with respect to the genus of the underlying graph.
We study the parameterized complexity of \(\mathrm{WSAT}^-[t]\) and \(\mathrm{WSAT}^+[t]\) with respect to the genus of the underlying circuit. We give tight results, and draw a map of the parameterized complexity of these problems with respect to the genus of the circuit. As a byproduct of our results, we obtain tight characterizations of the parameterized complexity of several problems with respect to the genus of the underlying graph.
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 68R10 | Graph theory (including graph drawing) in computer science |
References:
| [1] | Abrahamson, K.; Downey, R.; Fellows, M., Fixed-parameter tractability and completeness IV: on completeness for W[P] and PSPACE analogues, Ann. Pure Appl. Log., 73, 3, 235-276 (1995) · Zbl 0828.68077 |
| [2] | Barrington, D.; Lu, C.; Miltersen, P.; Skyum, S., On monotone planar circuits, (Proceedings of the Fourteenth Annual IEEE Conference on Computational Complexity (1999)), 24-31 |
| [3] | Bodlaender, H.; Drange, P.; Dregi, M.; Fomin, F.; Lokshtanov, D.; Polopczuk, M., A \(O(c^k n) 5\)-approximation algorithm for treewidth, (Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (2013)) |
| [4] | Bodlaender, H.; Fomin, F.; Lokshtanov, D.; Penninkx, E.; Saurabh, S.; Thilikos, D., (Meta) kernelization, (Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (2009)), 629-638 · Zbl 1292.68089 |
| [5] | Bodlaender, H.; Gilbert, J.; Hafsteinsson, H.; Kloks, T., Approximating treewidth, pathwidth, frontsize, and shortest elimination tree, J. Algorithms, 18, 2, 238-255 (1995) · Zbl 0818.68118 |
| [6] | Cai, L.; Fellows, M.; Juedes, D.; Rosamond, F., The complexity of polynomial-time approximation, Theory Comput. Syst., 41, 3, 459-477 (2007) · Zbl 1202.68481 |
| [7] | Chen, J.; Huang, X.; Kanj, I.; Xia, G., Polynomial time approximation schemes and parameterized complexity, Discrete Appl. Math., 155, 2, 180-193 (2007) · Zbl 1109.68135 |
| [8] | Chen, J.; Kanj, I.; Perkovic, L.; Sedgwick, E.; Xia, G., Genus characterizes the complexity of certain graph problems: some tight results, J. Comput. Syst. Sci., 73, 6, 892-907 (2007) · Zbl 1121.68086 |
| [9] | Demaine, E.; Fomin, F.; Hajiaghayi, M.; Thilikos, D., Subexponential parameterized algorithms on bounded-genus graphs and \(H\)-minor-free graphs, J. ACM, 52, 866-893 (2005) · Zbl 1326.05152 |
| [10] | Demaine, E.; Hajiaghayi, M., Bidimensionality: new connections between FPT algorithms and PTASs, (Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (2005)), 590-601 · Zbl 1297.05056 |
| [11] | Djidjev, H.; Venkatesan, S., Planarization of graphs embedded on surfaces, (Proceedings of the 21st International Workshop on Graph-Theoretic Concepts in Computer Science. Proceedings of the 21st International Workshop on Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, vol. 1017 (1995), Springer), 62-72 · Zbl 1533.05067 |
| [12] | Downey, R.; Fellows, M., Parameterized Complexity (1999), Springer: Springer New York · Zbl 0914.68076 |
| [13] | Flüm, J.; Grohe, M., Parameterized Complexity Theory (2010), Springer-Verlag: Springer-Verlag Berlin, Germany |
| [14] | Fomin, F.; Golovach, P.; Thilikos, D., Contraction obstructions for treewidth, J. Comb. Theory (B), 101, 5, 302-314 (2011) · Zbl 1223.05022 |
| [15] | Fomin, F.; Lokshtanov, D.; Raman, V.; Saurabh, S., Bidimensionality and EPTAS, (Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (2011)), 748-759 · Zbl 1377.68324 |
| [16] | Fomin, F.; Lokshtanov, D.; Saurabh, S.; Thilikos, D., Bidimensionality and kernels, (Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (2010)), 503-510 · Zbl 1288.68116 |
| [17] | Gross, J.; Tucker, T., Topological Graph Theory (1987), Wiley-Interscience: Wiley-Interscience New York, NY, USA · Zbl 0621.05013 |
| [18] | Kanj, I.; Pelsmajer, M.; Schaefer, M.; Xia, G., On the induced matching problem, J. Comput. Syst. Sci., 77, 6, 1058-1070 (2011) · Zbl 1235.05114 |
| [19] | Khanna, S.; Motwani, R., Towards a syntactic characterization of PTAS, (Proceedings of the 28th Annual ACM Symposium on Theory of Computing (1996)), 468-477 |
| [20] | Kloks, T., Treewidth, Computations and Approximations, Lecture Notes in Computer Science, vol. 842 (1994), Springer · Zbl 0825.68144 |
| [21] | Limaye, N.; Mahajan, M.; Sarma, J., Upper bounds for monotone planar circuit value and variants, Comput. Complex., 18, 377-412 (2009) · Zbl 1213.68266 |
| [22] | Lipton, R.; Tarjan, R., Applications of a planar separator theorem, SIAM J. Comput., 9, 3, 615-627 (1980) · Zbl 0456.68077 |
| [23] | Marx, D., Completely inapproximable monotone and antimonotone parameterized problems, J. Comput. Syst. Sci., 79, 1, 144-151 (2013) · Zbl 1261.68066 |
| [24] | Savage, J., Planar Circuit Complexity and the Performance of VLSI Algorithms (May 1981), INRIA, Technical Report RR-0077 |
| [25] | Szeider, S., On fixed-parameter tractable parameterizations of SAT, (The International Conferences on Theory and Applications of Satisfiability Testing. The International Conferences on Theory and Applications of Satisfiability Testing, Lecture Notes in Computer Science, vol. 2919 (2004)), 188-202 · Zbl 1204.68109 |
| [26] | Turán, G., On the complexity of planar Boolean circuits, Comput. Complex., 5, 24-42 (1995) · Zbl 0816.68069 |
| [27] | van Rooij, J.; Bodlaender, H.; Rossmanith, P., Dynamic programming on tree decompositions using generalised fast subset convolution, (Proceedings of the 17th Annual European Symposium on Algorithms. Proceedings of the 17th Annual European Symposium on Algorithms, Lecture Notes in Computer Science, vol. 5757 (2009), Springer), 566-577 · Zbl 1256.68157 |
| [28] | Wegener, I., The Complexity of Boolean Functions (1987), Wiley-Teubner · Zbl 0623.94018 |
| [29] | West, D., Introduction to Graph Theory (1996), Prentice Hall Inc.: Prentice Hall Inc. Upper Saddle River, NJ · Zbl 0845.05001 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
