On multiway cut parameterized above lower bounds. (English) Zbl 1352.68100
Marx, Dániel (ed.) et al., Parameterized and exact computation. 6th international symposium, IPEC 2011, Saarbrücken, Germany, September 6–8, 2011. Revised selected papers. Berlin: Springer (ISBN 978-3-642-28049-8/pbk). Lecture Notes in Computer Science 7112, 1-12 (2012).
Summary: In this paper we consider two above lower bound parameterizations of the Node Multiway Cut problem – above the maximum separating cut and above a natural LP-relaxation – and prove them to be fixed-parameter tractable. Our results imply \(O ^{*}(4^{k })\) algorithms for Vertex Cover above Maximum Matching and Almost 2-SAT as well as an \(O ^{*}(2^{k })\) algorithm for Node Multiway Cut with a standard parameterization by the solution size, improving previous bounds for these problems.
For the entire collection see [Zbl 1238.68016].
For the entire collection see [Zbl 1238.68016].
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 05C40 | Connectivity |
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 90C27 | Combinatorial optimization |
References:
| [1] | Bousquet, N., Daligault, J., Thomassé, S.: Multicut is FPT. In: Proc. of STOC 2011 (to appear, 2011) · Zbl 1288.05264 · doi:10.1145/1993636.1993698 |
| [2] | Chen, J., Liu, Y., Lu, S.: An improved parameterized algorithm for the minimum node multiway cut problem. Algorithmica 55(1), 1–13 (2009) · Zbl 1194.68168 · doi:10.1007/s00453-007-9130-6 |
| [3] | Chen, J., Liu, Y., Lu, S., O’Sullivan, B., Razgon, I.: A fixed-parameter algorithm for the directed feedback vertex set problem. In: Proc. of STOC 2008, pp. 177–186 (2008) · Zbl 1231.68149 · doi:10.1145/1374376.1374404 |
| [4] | Dahlhaus, E., Johnson, D.S., Papadimitriou, C.H., Seymour, P.D., Yannakakis, M.: The complexity of multiterminal cuts. SIAM J. Comput. 23(4), 864–894 (1994) · Zbl 0809.68075 · doi:10.1137/S0097539792225297 |
| [5] | Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1999), citeseer.ist.psu.edu/downey98parameterized.html · doi:10.1007/978-1-4612-0515-9 |
| [6] | Fellows, M.R., Hermelin, D., Rosamond, F.A., Vialette, S.: On the parameterized complexity of multiple-interval graph problems. Theor. Comput. Sci. 410, 53–61 (2009) · Zbl 1161.68038 · doi:10.1016/j.tcs.2008.09.065 |
| [7] | Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science, 1st edn. An EATCS Series. Springer, Heidelberg (2006), http://www.worldcat.org/isbn/3540299521 |
| [8] | Garg, N., Vazirani, V.V., Yannakakis, M.: Multiway cuts in node weighted graphs. J. Algorithms 50(1), 49–61 (2004) · Zbl 1068.68178 · doi:10.1016/S0196-6774(03)00111-1 |
| [9] | Guillemot, S.: FPT Algorithms for Path-Transversals and Cycle-Transversals Problems in Graphs. In: Grohe, M., Niedermeier, R. (eds.) IWPEC 2008. LNCS, vol. 5018, pp. 129–140. Springer, Heidelberg (2008) · Zbl 1142.68599 · doi:10.1007/978-3-540-79723-4_13 |
| [10] | Gutin, G., van Iersel, L., Mnich, M., Yeo, A.: All Ternary Permutation Constraint Satisfaction Problems Parameterized above Average have Kernels with Quadratic Numbers of Variables. In: de Berg, M., Meyer, U. (eds.) ESA 2010, Part I, LNCS, vol. 6346, pp. 326–337. Springer, Heidelberg (2010) · Zbl 1287.68074 · doi:10.1007/978-3-642-15775-2_28 |
| [11] | Gutin, G., Kim, E.J., Lampis, M., Mitsou, V.: Vertex cover problem parameterized above and below tight bounds. Theory Comput. Syst. 48(2), 402–410 (2011) · Zbl 1209.68276 · doi:10.1007/s00224-010-9262-y |
| [12] | Mahajan, M., Raman, V.: Parameterizing above guaranteed values: Maxsat and maxcut. J. Algorithms 31(2), 335–354 (1999) · Zbl 0921.68052 · doi:10.1006/jagm.1998.0996 |
| [13] | Marx, D.: Parameterized graph separation problems. Theor. Comput. Sci. 351(3), 394–406 (2006) · Zbl 1086.68104 · doi:10.1016/j.tcs.2005.10.007 |
| [14] | Marx, D., Razgon, I.: Fixed-parameter tractability of multicut parameterized by the size of the cutset. In: Proc. of STOC 2011 (to appear, 2011) · Zbl 1288.05283 · doi:10.1145/1993636.1993699 |
| [15] | Niedermeier, R.: Invitation to Fixed Parameter Algorithms. Oxford Lecture Series in Mathematics and Its Applications. Oxford University Press, USA (2006), http://www.worldcat.org/isbn/0198566077 · doi:10.1093/acprof:oso/9780198566076.001.0001 |
| [16] | Raman, V., Ramanujan, M.S., Saurabh, S.: Paths, Flowers and Vertex Cover. In: Demetrescu, C., Halldórsson, M.M. (eds.) ESA 2011. LNCS, vol. 6942, pp. 382–393. Springer, Heidelberg (2011) · Zbl 1346.05287 · doi:10.1007/978-3-642-23719-5_33 |
| [17] | Razgon, I.: Computing multiway cut within the given excess over the largest minimum isolating cut. CoRR abs/1011.6267 (2010) |
| [18] | Razgon, I.: Large isolating cuts shrink the multiway cut. CoRR abs/1104.5361 (2011) |
| [19] | Razgon, I., O’Sullivan, B.: Almost 2-SAT is fixed-parameter tractable. J. Comput. Syst. Sci. 75(8), 435–450 (2009) · Zbl 1184.68477 · doi:10.1016/j.jcss.2009.04.002 |
| [20] | Xiao, M.: Simple and improved parameterized algorithms for multiterminal cuts. Theory Comput. Syst. 46(4), 723–736 (2010) · Zbl 1213.68472 · doi:10.1007/s00224-009-9215-5 |
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.
