On the connectivity preserving minimum cut problem

DOI10.1016/J.JCSS.2014.01.003MaRDI QIDQ2637652zbMATH OpenOpenAlexFDO

Authors Jinhui Xu, Qi Duan

Publication date 13 February 2014

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

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

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)

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.

Recommendations

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

Cites work

• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• scientific article; zbMATH DE number 1219584 (Why is no real title available?)
• scientific article; zbMATH DE number 1256748 (Why is no real title available?)
• scientific article; zbMATH DE number 1330032 (Why is no real title available?)
• scientific article; zbMATH DE number 1559563 (Why is no real title available?)
• scientific article; zbMATH DE number 6146454 (Why is no real title available?)
• scientific article; zbMATH DE number 6783459 (Why is no real title available?)
• A note on two problems in connexion with graphs
• Combinatorial optimization. Networks and matroids
• On shortest disjoint paths in planar graphs
• On the hardness of approximating minimization problems
• The Complexity of Multiterminal Cuts
• The Effect of a Connectivity Requirement on the Complexity of Maximum Subgraph Problems

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)