×

Computing the largest bond and the maximum connected cut of a graph. (English) Zbl 1512.68209

Summary: The cut-set \(\partial(S)\) of a graph \(G=(V,E)\) is the set of edges that have one endpoint in \(S\subset V\) and the other endpoint in \(V\setminus S\), and whenever \(G[S]\) is connected, the cut \([S,V\setminus S]\) of \(G\) is called a connected cut. A bond of a graph \(G\) is an inclusion-wise minimal disconnecting set of \(G\), i.e., bonds are cut-sets that determine cuts \([S,V\setminus S]\) of \(G\) such that \(G[S]\) and \(G[V\setminus S]\) are both connected. Contrasting with a large number of studies related to maximum cuts, there exist very few results regarding the largest bond of general graphs. In this paper, we aim to reduce this gap on the complexity of computing the largest bond, and the maximum connected cut of a graph. Although cuts and bonds are similar, we remark that computing the largest bond and the maximum connected cut of a graph tends to be harder than computing its maximum cut. We show that it does not exist a constant-factor approximation algorithm to compute the largest bond, unless \(\mathrm{P}=\mathrm{NP}\). Also, we show that Largest Bond and Maximum Connected Cut are NP-hard even for planar bipartite graphs, whereas Maximum Cut is trivial on bipartite graphs and polynomial-time solvable on planar graphs. In addition, we show that Largest Bond and Maximum Connected Cut are NP-hard on split graphs, and restricted to graphs of clique-width \(w\) they can not be solved in time \(f(w) n^{{o}(w)}\) unless the Exponential Time Hypothesis fails, but they can be solved in time \(f(w)n^{{O}(w)} \). Finally, we show that both problems are fixed-parameter tractable when parameterized by the size of the solution, the treewidth, and the twin-cover number.

MSC:

68R10 Graph theory (including graph drawing) in computer science
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q27 Parameterized complexity, tractability and kernelization

Software:

GYutsis
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Aldred, REL; Van Dyck, D.; Brinkmann, G.; Fack, V.; McKay, BD, Graph structural properties of non-Yutsis graphs allowing fast recognition, Discrete Appl. Math., 157, 2, 377-386 (2009) · Zbl 1168.05363
[2] Bazgan, C.; Brankovic, L.; Casel, K.; Fernau, H.; Jansen, K.; Klein, KM; Lampis, M.; Liedloff, M.; Monnot, J.; Paschos, VT, The many facets of upper domination, Theoret. Comput. Sci., 717, 2-25 (2018) · Zbl 1388.68099
[3] Biedenharn, LC; Louck, JD, The Racah-Wigner Algebra in Quantum Theory (1981), USA: Addison-Wesley, USA · Zbl 0474.00024
[4] Bodlaender, HL; Cygan, M.; Kratsch, S.; Nederlof, J., Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth, Inf. Comput., 243, 86-111 (2015) · Zbl 1327.68126
[5] Bodlaender, HL; Jansen, K., On the complexity of the maximum cut problem, Nordic J. Comput., 7, 1, 14-31 (2000) · Zbl 0963.68224
[6] Bodlaender, HL; Van Leeuwen, J.; Tan, R.; Thilikos, DM, On interval routing schemes and treewidth, Inf. Comput., 139, 1, 92-109 (1997) · Zbl 0892.68069
[7] Boria, N.; Croce, FD; Paschos, VT, On the max min vertex cover problem, Discrete Appl. Math., 196, 62-71 (2015) · Zbl 1321.05177
[8] Bui-Xuan, BM; Suchý, O.; Telle, JA; Vatshelle, M., Feedback vertex set on graphs of low clique-width, Eur. J. Comb., 34, 3, 666-679 (2013) · Zbl 1257.05165
[9] Carvajal, R.; Constantino, M.; Goycoolea, M.; Vielma, JP; Weintraub, A., Imposing connectivity constraints in forest planning models, Oper. Res., 61, 4, 824-836 (2013) · Zbl 1291.90341
[10] Chaourar, B.: A linear time algorithm for a variant of the MAX CUT problem in series parallel graphs. Adv. Oper. Res. 1267108:1-1267108:4 (2017) · Zbl 1387.90259
[11] Chaourar, B.: Connected max cut is polynomial for graphs without \({K}_5\setminus e\) as a minor. CoRR (2019). arXiv:1903.12641
[12] Cho, JJ; Chen, Y.; Ding, Y., On the (co)girth of a connected matroid, Discrete Appl. Math., 155, 18, 2456-2470 (2007) · Zbl 1127.05020 · doi:10.1016/j.dam.2007.06.015
[13] Cormen, T.; Leiserson, C.; Rivest, R.; Stein, C., Introduction to Algorithms (2001), Cambridge: MIT Press, Cambridge · Zbl 1047.68161
[14] Courcelle, B.; Makowsky, JA; Rotics, U., Linear time solvable optimization problems on graphs of bounded clique-width, Theory Comput. Syst., 33, 2, 125-150 (2000) · Zbl 1009.68102
[15] Courcelle, B.; Olariu, S., Upper bounds to the clique width of graphs, Discrete Appl. Math., 101, 1-3, 77-114 (2000) · Zbl 0958.05105
[16] Cygan, M., Fomin, F.V., Kowalik, Ł., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015) · Zbl 1334.90001
[17] Cygan, M., Nederlof, J., Pilipczuk, M., Pilipczuk, M., Rooij, J.M.M.v., Wojtaszczyk, J.O.: Solving connectivity problems parameterized by treewidth in single exponential time. In: IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS 2011), pp. 150-159 (2011) · Zbl 1292.68122
[18] de Berg, M., Khosravi, A.: Finding perfect auto-partitions is NP-hard. In: 25th European Workshop on Computational Geometry (EuroCG2009), pp. 255-258 (2009)
[19] Demange, M., A note on the approximation of a minimum-weight maximal independent set, Comput. Optim. Appl., 14, 1, 157-169 (1999) · Zbl 0958.90093
[20] Ding, G.; Dziobiak, S.; Wu, H., Large-or-minors in 3-connected graphs, J. Graph Theory, 82, 2, 207-217 (2016) · Zbl 1339.05376
[21] Duarte, G.L., Lokshtanov, D., Pedrosa, L.L.C., Schouery, R.C.S., Souza, U.S.: Computing the Largest Bond of a Graph. In: 14th International Symposium on Parameterized and Exact Computation (IPEC 2019), Volume148 of LIPIcs, pp. 12:1-12:15 (2019) · Zbl 07650220
[22] Dyck, DV; Fack, V., On the reduction of Yutsis graphs, Discrete Math., 307, 11, 1506-1515 (2007) · Zbl 1115.68117
[23] Díaz, J.; Kamiński, M., Max-cut and max-bisection are NP-hard on unit disk graphs, Theoret. Comput. Sci., 377, 1, 271-276 (2007) · Zbl 1118.68073
[24] Edmonds, J.; Karp, RM, Theoretical improvements in algorithmic efficiency for network flow problems, J. ACM, 19, 2, 248-264 (1972) · Zbl 0318.90024
[25] Erdös, P., On some extremal problems in graph theory, Israel J. Math., 3, 2, 113-116 (1965) · Zbl 0134.43403
[26] Eto, H., Hanaka, T., Kobayashi, Y., Kobayashi, Y.: Parameterized Algorithms for Maximum Cut with Connectivity Constraints. In: 14th International Symposium on Parameterized and Exact Computation (IPEC 2019), Volume148 of LIPIcs, pp. 13:1-13:15 (2019) · Zbl 07650221
[27] Flynn, M.: The largest bond in 3-connected graphs. Ph.D. thesis, The University of Mississippi (2017)
[28] Fomin, FV; Golovach, PA; Lokshtanov, D.; Saurabh, S., Almost optimal lower bounds for problems parameterized by clique-width, SIAM J. Comput., 43, 5, 1541-1563 (2014) · Zbl 1306.05181
[29] Gandhi, R.; Hajiaghayi, MT; Kortsarz, G.; Purohit, M.; Sarpatwar, K., On maximum leaf trees and connections to connected maximum cut problems, Inf. Processing Lett., 129, 31-34 (2018) · Zbl 1420.68158
[30] Ganian, R., Improving vertex cover as a graph parameter, Discrete Math. Theoret. Comput. Sci., 17, 2, 77-100 (2015) · Zbl 1327.05321
[31] Garey, MR; Johnson, DS, Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), New York: W. H. Freeman, New York · Zbl 0411.68039
[32] Garey, MR; Johnson, DS; Tarjan, RE, The planar hamiltonian circuit problem is NP-complete, SIAM J. Comput., 5, 4, 704-714 (1976) · Zbl 0346.05110
[33] Godsil, CD; Royle, GF, Algebraic Graph Theory. Graduate Texts in Mathematics (2001), Berlin: Springer, Berlin · Zbl 0968.05002
[34] Goemans, MX; Williamson, DP, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. ACM, 42, 6, 1115-1145 (1995) · Zbl 0885.68088
[35] Gomory, RE; Hu, TC, Multi-terminal network flows, J. Soc. Ind. Appl. Math., 9, 4, 551-570 (1961) · Zbl 0112.12405
[36] Grimm, V.; Kleinert, T.; Liers, F.; Schmidt, M.; Zöttl, G., Optimal price zones of electricity markets: a mixed-integer multilevel model and global solution approaches, Optim. Methods Softw., 34, 2, 406-436 (2019) · Zbl 1407.90077
[37] Guruswami, V., Maximum cut on line and total graphs, Discrete Appl. Math., 92, 2, 217-221 (1999) · Zbl 0935.68082
[38] Hadlock, F., Finding a maximum cut of a planar graph in polynomial time, SIAM J. Comput., 4, 3, 221-225 (1975) · Zbl 0321.05120
[39] Haglin, DJ; Venkatesan, SM, Approximation and intractability results for the maximum cut problem and its variants, IEEE Trans. Comput., 40, 1, 110-113 (1991) · Zbl 1395.68139
[40] Hajiaghayi, M.T., Kortsarz, G., MacDavid, R., Purohit, M., Sarpatwar, K.: Approximation algorithms for connected maximum cut and related problems. In: 23rd Annual European Symposium on Algorithms (ESA 2015), Volume 9294 of LNCS, pp. 693-704 (2015) · Zbl 1420.68237
[41] Hanaka, T., Bodlaender, H.L., van der Zanden, T.C., Ono, H.: On the maximum weight minimal separator. In: 14th Annual Conference on Theory and Applications of Models of Computation (TAMC 2017), Volume 10185 of LNCS, pp. 304-318 (2017) · Zbl 1435.68238
[42] Karp, RM, Reducibility among Combinatorial Problems, 85-103 (1972), Boston, MA: Springer US, Boston, MA · Zbl 1467.68065
[43] Khoshkhah, K., Ghadikolaei, M.K., Monnot, J., Sikora, F.: Weighted upper edge cover: Complexity and approximability. In: 13th International Workshop on Algorithms and Computation (WALCOM 2019), Volume 11355 of LNCS, pp. 235-247 (2019) · Zbl 1420.68093
[44] Khot, S.; Kindler, G.; Mossel, E.; O’Donnell, R., Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?, SIAM J. Comput., 37, 1, 319-357 (2007) · Zbl 1135.68019
[45] Mahajan, M.; Raman, V., Parameterizing above guaranteed values: MaxSat and MaxCut, J. Algorithms, 31, 2, 335-354 (1999) · Zbl 0921.68052
[46] Mitzenmacher, M.; Upfal, E., Probability and Computing: Randomized Algorithms and Probabilistic Analysis (2005), Cambridge: Cambridge University Press, Cambridge · Zbl 1092.60001
[47] Mulmuley, K.; Vazirani, UV; Vazirani, V., Matching is as easy as matrix inversion, Combinatorica, 7, 1, 105-113 (1987) · Zbl 0632.68041
[48] Odlyzko, AM, Asymptotic enumeration methods, Handbook Combi., 2, 1063, 1229 (1995) · Zbl 0845.05005
[49] Orlova, GI; Dorfman, YG, Finding the maximal cut in a graph, Eng. Cyvernetics, 10, 3, 502-506 (1972) · Zbl 0247.05151
[50] Oxley, JG, Matroid Theory (2006), USA: Oxford University Press, USA · Zbl 1115.05001
[51] Raman, V.; Saurabh, S., Improved fixed parameter tractable algorithms for two “edge” problems: MAXCUT and MAXDAG, Inf. Process. Lett., 104, 2, 65-72 (2007) · Zbl 1183.05084
[52] Rao, M., Clique-width of graphs defined by one-vertex extensions, Discrete Math., 308, 24, 6157-6165 (2008) · Zbl 1180.05081
[53] Robertson, N.; Seymour, PD, Graph minors. V. excluding a planar graph, J. Comb. Theory, Ser. B, 41, 1, 92-114 (1986) · Zbl 0598.05055
[54] Saurabh, S., Zehavi, M.: Parameterized Complexity of Multi-Node Hubs. In: 13th International Symposium on Parameterized and Exact Computation (IPEC 2018), Volume115 of LIPIcs, pp. 8:1-8:14 (2019) · Zbl 1520.68051
[55] Shen, X.; Lee, J.; Nagarajan, V., Approximating graph-constrained max-cut, Math. Program., 172, 1, 35-58 (2018) · Zbl 1406.90106
[56] Vicente, S., Kolmogorov, V., Rother, C.: Graph cut based image segmentation with connectivity priors. In: 2008 IEEE Conference on Computer Vision and Pattern Recognition (CVPR 2008), pp. 1-8 (2008)
[57] Yannakakis, M.; Gavril, F., Edge dominating sets in graphs, SIAM J. Appl. Math., 38, 3, 364-372 (1980) · Zbl 0455.05047
[58] Yutsis, A.P., Vanagas, V.V., Levinson, I.B.: Mathematical apparatus of the theory of angular momentum. Israel Program for Scientific Translations (1962) · Zbl 0111.42704
[59] Zehavi, M., Maximum minimal vertex cover parameterized by vertex cover, SIAM J. Discrete Math., 31, 4, 2440-2456 (2017) · Zbl 1380.68236
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.