Madathil, Jayakrishnan; Sharma, Roohani; Zehavi, Meirav A sub-exponential FPT algorithm and a polynomial kernel for minimum directed bisection on semicomplete digraphs. (English) Zbl 1516.68068 Algorithmica 83, No. 6, 1861-1884 (2021). Summary: Given an \(n\)-vertex digraph \(D\) and a non-negative integer \(k\), the Minimum Directed Bisection problem asks if the vertices of \(D\) can be partitioned into two parts, say \(L\) and \(R\), such that \(\vert L\vert\) and \(\vert R\vert\) differ by at most 1 and the number of arcs from \(R\) to \(L\) is at most \(k\). This problem is known to be NP-hard even when \(k=0\). We investigate the parameterized complexity of this problem on semicomplete digraphs. We show that Minimum Directed Bisection admits a sub-exponential time fixed-parameter tractable algorithm on semicomplete digraphs. We also show that Minimum Directed Bisection admits a polynomial kernel on semicomplete digraphs. To design the kernel, we use \((n,k,k^2)\)-splitters, which, to the best of our knowledge, have never been used before in the design of kernels. We also prove that Minimum Directed Bisection is NP-hard on semicomplete digraphs, but polynomial time solvable on tournaments. MSC: 68R10 Graph theory (including graph drawing) in computer science 05C20 Directed graphs (digraphs), tournaments 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) 05C85 Graph algorithms (graph-theoretic aspects) 68Q27 Parameterized complexity, tractability and kernelization Keywords:bisection; semicomplete digraph; tournament; FPT algorithm; chromatic coding; polynomial kernel; splitters PDFBibTeX XMLCite \textit{J. Madathil} et al., Algorithmica 83, No. 6, 1861--1884 (2021; Zbl 1516.68068) Full Text: DOI Link References: [1] Alon, N., Lokshtanov, D., Saurabh, S.: Fast FAST. In: Automata, Languages and Programming, 36th International Colloquium, ICALP 2009, Rhodes, Greece, July 5-12, 2009, Proceedings, Part I, pp. 49-58 (2009) · Zbl 1248.68547 [2] Alon, N.; Yuster, R.; Zwick, U., Color-coding, J. ACM, 42, 4, 844-856 (1995) · Zbl 0885.68116 [3] Bang-Jensen, J.; Gutin, GZ, Digraphs—Theory, Algorithms and Applications (2002), Berlin: Springer, Berlin · Zbl 1001.05002 [4] Barbero, F.; Paul, C.; Pilipczuk, M., Exploring the complexity of layout parameters in tournaments and semicomplete digraphs, ACM Trans. Algorithms, 14, 3, 38:1-38:31 (2018) · Zbl 1454.68055 [5] Barbero, F.; Paul, C.; Pilipczuk, M., Strong immersion is a well-quasi-ordering for semicomplete digraphs, J. Graph Theory, 90, 4, 484-496 (2019) · Zbl 1414.05273 [6] Bessy, S.; Fomin, FV; Gaspers, S.; Paul, C.; Perez, A.; Saurabh, S.; Thomassé, S., Kernels for feedback arc set in tournaments, J. Comput. Syst. Sci., 77, 6, 1071-1078 (2011) · Zbl 1235.05134 [7] Bui, TN; Peck, A., Partitioning planar graphs, SIAM J. Comput., 21, 2, 203-215 (1992) · Zbl 0759.05089 [8] Camion, P., Chemins et circuits hamiltoniens des graphes complets, Comptes Rendus Hebdomadaires des Séances de l’Académie des Sciences, 249, 21, 2151-2152 (1959) · Zbl 0092.15801 [9] Chudnovsky, M.; Seymour, PD, A well-quasi-order for tournaments, J. Comb. Theory Ser. B, 101, 1, 47-53 (2011) · Zbl 1221.05178 [10] Cygan, M.; Fomin, FV; Kowalik, L.; Lokshtanov, D.; Marx, D.; Pilipczuk, M.; Pilipczuk, M.; Saurabh, S., Parameterized Algorithms (2015), Berlin: Springer, Berlin · Zbl 1334.90001 [11] Cygan, M.; Lokshtanov, D.; Pilipczuk, M.; Pilipczuk, M.; Saurabh, S., Minimum bisection is fixed-parameter tractable, SIAM J. Comput., 48, 2, 417-450 (2019) · Zbl 1421.68069 [12] Díaz, J., Mertzios, G.B.: Minimum bisection is NP-hard on unit disk graphs. In: Mathematical Foundations of Computer Science 2014—39th International Symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings, Part II, pp. 251-262 (2014) · Zbl 1426.68100 [13] Diestel, R.: Graph Theory, 4th edn, volume 173 of Graduate texts in mathematics. Springer (2012) · Zbl 1375.05002 [14] Dom, M.; Guo, J.; Hüffner, F.; Niedermeier, R.; Truß, A., Fixed-parameter tractability results for feedback set problems in tournaments, J. Discrete Algorithms, 8, 1, 76-86 (2010) · Zbl 1191.68349 [15] Feige, U.: Faster fast (feedback arc set in tournaments). CoRR arXiv:abs/0911.5094 (2009) [16] Feige, U.; Yahalom, O., On the complexity of finding balanced oneway cuts, Inf. Process. Lett., 87, 1, 1-5 (2003) · Zbl 1175.68188 [17] Feldmann, AE; Widmayer, P., An o(n \({}^{\text{4}} )\) time algorithm to compute the bisection width of solid grid graphs, Algorithmica, 71, 1, 181-200 (2015) · Zbl 1307.05211 [18] Fomin, FV; Pilipczuk, M., On width measures and topological problems on semi-complete digraphs, J. Comb. Theory Ser. B, 138, 78-165 (2019) · Zbl 1415.05063 [19] Fradkin, A.: Forbidden structures and algorithms in graphs and digraphs. PhD thesis, Princeton University (2011) [20] Garey, MR; Johnson, DS; Stockmeyer, LJ, Some simplified NP-complete graph problems, Theor. Comput. Sci., 1, 3, 237-267 (1976) · Zbl 0338.05120 [21] Jansen, K.; Karpinski, M.; Lingas, A.; Seidel, E., Polynomial time approximation schemes for MAX-BISECTION on planar and geometric graphs, SIAM J. Comput., 35, 1, 110-119 (2005) · Zbl 1087.90063 [22] Karpinski, M., Schudy, W.: Faster algorithms for feedback arc set tournament, kemeny rank aggregation and betweenness tournament. In: Algorithms and Computation—21st International Symposium, ISAAC 2010, Jeju Island, Korea, December 15-17, 2010, Proceedings, Part I, pp. 3-14 (2010) · Zbl 1310.68272 [23] Kim, I.: On containment relations in directed graphs. PhD thesis, Princeton University (2013) [24] Kim, I.; Seymour, PD, Tournament minors, J. Comb. Theory Ser. B, 112, 138-153 (2015) · Zbl 1310.05109 [25] Lampis, M.; Kaouri, G.; Mitsou, V., On the algorithmic effectiveness of digraph decompositions and complexity measures, Discrete Optim., 8, 1, 129-138 (2011) · Zbl 1248.90073 [26] Macgregor, R.M.: On partitioning a graph: a theoretical and empirical study. PhD thesis, University of California, Berkeley (1979) [27] Madathil, J., Sharma, R., Zehavi, M.: A sub-exponential FPT algorithm and a polynomial kernel for minimum directed bisection on semicomplete digraphs. In: Rossmanith, P., Heggernes, P., Katoen, J.-P. (es) 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019, August 26-30, 2019, Aachen, Germany, volume 138 of LIPIcs, pp. 28:1-28:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019) [28] Marx, D., Parameterized graph separation problems, Theor. Comput. Sci., 351, 3, 394-406 (2006) · Zbl 1086.68104 [29] Naor, M., Schulman, L.J., Srinivasan, A.: Splitters and near-optimal derandomization. In: 36th Annual Symposium on Foundations of Computer Science, Milwaukee, Wisconsin, USA, 23-25 October 1995, pp. 182-191 (1995) · Zbl 0938.68932 [30] Panolan, F., Saurabh, S., Zehavi, M.: Contraction decomposition in unit disk graphs and algorithmic applications in parameterized complexity. In: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pp. 1035-1054 (2019) · Zbl 1431.68100 [31] Papadimitriou, CH; Sideri, M., The bisection width of grid graphs, Math. Syst. Theory, 29, 2, 97-110 (1996) · Zbl 0839.68076 [32] Räcke, H.: Optimal hierarchical decompositions for congestion minimization in networks. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008, pp. 255-264 (2008) · Zbl 1231.68051 [33] Rédei, L., Ein kombinatorischer satz, Satz. Acta Litt. Szeged, 7, 39-43 (1934) · Zbl 0009.14606 [34] van Bevern, R., Feldmann, A.E., Sorge, M., Suchý, O.: On the parameterized complexity of computing graph bisections. In Brandstädt, A., Jansen, K., Reischuk, R. (eds) Graph-Theoretic Concepts in Computer Science—39th International Workshop, WG 2013, Lübeck, Germany, June 19-21, 2013, Revised Papers, volume 8165 of Lecture Notes in Computer Science, pp. 76-87. Springer (2013) · Zbl 1318.68098 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.