Connected max cut is polynomial for graphs without the excluded minor $$K_5\backslash e$$ K 5 \ e
- PDF / 268,265 Bytes
- 7 Pages / 439.37 x 666.142 pts Page_size
- 74 Downloads / 139 Views
Connected max cut is polynomial for graphs without the excluded minor K5 \e Brahim Chaourar1
© Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Given a graph G = (V , E), a connected cut δ(U ) is the set of edges of E linking all vertices of U to all vertices of V \U such that the induced subgraphs G[U ] and G[V \U ] are connected. Given a positive weight function w defined on E, the connected maximum cut problem (CMAX CUT) is to find a connected cut Ω such that w(Ω) is maximum among all connected cuts. CMAX CUT is NP-hard even for planar graphs, and thus for graph without the excluded minor K 5 . In this paper, we prove that CMAX CUT is polynomial for the class of graphs without the excluded minor K 5 \e, denoted by G(K 5 \e). We deduce two quadratic time algorithms: one for the minimum cut problem in G(K 5 \e) without computing the maximum flow, and another one for Hamilton cycle problem in the class of graphs without the two excluded minors the prism P6 and K 3,3 . This latter problem is NP-complete for maximal planar graphs. Keywords Max cut · Connected max cut · Polynomial algorithm · Min cut · Graphs without the excluded minor K 5 \e · Hamilton cycle problem Mathematics Subject Classification 90C27
1 Introduction We refer to Bondy and Murty (2008) about graph theory terminolgy and facts. Given an undirected graph G = (V , E) and positive weights wi j = w ji on the edges (i, j) ∈ E, the maximum (respectively, minimum) cut problem (MAX CUT, (respectively, MIN CUT)) is that of finding the set of vertices S that maximizes (respectively, minimzes) the weight of the edges in the cut (S, V \S) or δ(S) or δ(V \S); that is, the weight of the edges linking all vertices of S to those of V \S. The (decision variant of the) MAX
B 1
Brahim Chaourar [email protected] Imam Mohammad Ibn Saud Islamic University (IMSIU), P.O. Box 90950, Riyadh 11623, Saudi Arabia
123
Journal of Combinatorial Optimization
CUT is one of the Karp’s original NP-complete problems (Karp 1972), and has long been known to be NP-complete even if the problem is unweighted; that is, if wi j = 1 for all (i, j) ∈ E (Garey et al. 1976). This motivates the research to solve MAX CUT in special classes of graphs. MAX CUT problem is solvable in polynomial time for the following special classes of graphs: planar graphs (Barahona 1990; Hadlock 1975; Orlova and Dorfman 1972), line graphs (Guruswami 1999), graphs with bounded treewidth, or cographs (Bodlaender and Jansen 2000). But the problem remains NPcomplete for chordal graphs, undirected path graphs, split graphs, tripartite graphs, graphs that are the complement of a bipartite graph (Bodlaender and Jansen 2000) and planar graphs if the weights are of arbitrary sign (Terebenkov 1991). Besides its theoretical importance, MAX CUT problem has applications in circuit layout design and statistical physics (Barahona et al. 1988). For a comprehensive survey of MAX CUT, the reader is referred to Poljak and Tuza (1995) and Ben-Ameur et al. (2014). The best known algorithm for MAX
Data Loading...
