On the connectivity preserving minimum cut problem

DOI10.1016/J.JCSS.2014.01.003zbMATH Open1285.68121arXiv1309.6689OpenAlexW2084950686MaRDI QIDQ2637652FDOQ2637652

Authors: Jinhui Xu, Qi Duan 

Publication date: 13 February 2014

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Abstract: In this paper, we study a generalization of the classical minimum cut prob- lem, called Connectivity Preserving Minimum Cut (CPMC) problem, which seeks a minimum cut to separate a pair (or pairs) of source and destination nodes and meanwhile ensure the connectivity between the source and its partner node(s). The CPMC problem is a rather powerful formulation for a set of problems and finds applications in many other areas, such as network security, image processing, data mining, pattern recognition, and machine learning. For this important problem, we consider two variants, connectiv- ity preserving minimum node cut (CPMNC) and connectivity preserving minimum edge cut (CPMEC). For CPMNC, we show that it cannot be ap- proximated within {alpha}logn for some constant {alpha} unless P=NP, and cannot be approximated within any poly(logn) unless NP has quasi-polynomial time algorithms. The hardness results hold even for graphs with unit weight and bipartite graphs. Particularly, we show that polynomial time solutions exist for CPMEC in planar graphs and for CPMNC in some special planar graphs. The hardness of CPMEC in general graphs remains open, but the polynomial time algorithm in planar graphs still has important practical applications.

Full work available at URL: https://arxiv.org/abs/1309.6689

Recommendations

• scientific article; zbMATH DE number 2075842
• Minimal disconnected cuts in planar graphs
• Minimal disconnected cuts in planar graphs

zbMATH Keywords

inapproximabilityminimum cutconnectivity preserving

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Planar graphs; geometric and topological aspects of graph theory (05C10) Connectivity (05C40)

Cites Work

• A note on two problems in connexion with graphs
• Title not available (Why is that?)
• The Complexity of Multiterminal Cuts
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the hardness of approximating minimization problems
• Title not available (Why is that?)
• Combinatorial optimization. Networks and matroids
• On shortest disjoint paths in planar graphs
• The Effect of a Connectivity Requirement on the Complexity of Maximum Subgraph Problems
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (2)

• Connectivity and minimum cut approximation in the broadcast congested clique
• Maximum reachability preserved graph cut

This page was built for publication: On the connectivity preserving minimum cut problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2637652)