| Texto completo | |
| Autor(es): |
Duarte, Gabriel L.
[1]
;
Eto, Hiroshi
[2]
;
Hanaka, Tesshu
[3]
;
Kobayashi, Yasuaki
[4]
;
Kobayashi, Yusuke
[4]
;
Lokshtanov, Daniel
[5]
;
Pedrosa, Lehilton L. C.
[6]
;
Schouery, Rafael C. S.
[6]
;
Souza, Ueverton S.
[1]
Número total de Autores: 9
|
| Afiliação do(s) autor(es): | [1] Fluminense Fed Univ, Niteroi, RJ - Brazil
[2] Kyushu Univ, Fukuoka - Japan
[3] Chuo Univ, Tokyo - Japan
[4] Kyoto Univ, Kyoto - Japan
[5] Univ Calif Santa Barbara, Santa Barbara, CA 93106 - USA
[6] Univ Estadual Campinas, Campinas, SP - Brazil
Número total de Afiliações: 6
|
| Tipo de documento: | Artigo Científico |
| Fonte: | ALGORITHMICA; v. 83, n. 5, p. 1421-1458, MAY 2021. |
| Citações Web of Science: | 0 |
| Resumo | |
The cut-set partial derivative(S) of a graph G = (V, E) is the set of edges that have one endpoint in S subset of V and the other endpoint in V \textbackslash{} S, and whenever G{[}S] is connected, the cut {[} S, V \textbackslash{} 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 \textbackslash{} S] of G such that G{[} S] and G{[}V \textbackslash{} 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 themaximum 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 P = 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-widthw 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)(nO(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. (AU) | |
| Processo FAPESP: | 15/11937-9 - Investigação de problemas difíceis do ponto de vista algorítmico e estrutural |
| Beneficiário: | Flávio Keidi Miyazawa |
| Modalidade de apoio: | Auxílio à Pesquisa - Temático |