A Polynomial Algorithm for the k-cut Problem for Fixed k

Olivier Goldschmidt
Olivier Goldschmidt
Mechanical Engineering Department, The University of Texas at Austin, Austin, Texas 78712
Search for more papers by this author
,
Dorit S. Hochbaum
Dorit S. Hochbaum
IEOR Department and School of Business Administration, University of California, Berkeley, California 94720
Search for more papers by this author

Olivier Goldschmidt

Mechanical Engineering Department, The University of Texas at Austin, Austin, Texas 78712

Search for more papers by this author

Dorit S. Hochbaum

IEOR Department and School of Business Administration, University of California, Berkeley, California 94720

Search for more papers by this author

Published Online:1 Feb 1994https://doi.org/10.1287/moor.19.1.24

Abstract

The k-cut problem is to find a partition of an edge weighted graph into k nonempty components, such that the total edge weight between components is minimum. This problem is NP-complete for an arbitrary k and its version involving fixing a vertex in each component is NP-hard even for k = 3. We present a polynomial algorithm for k fixed, that runs in O(n^k^{²/2−3k/2+4}T(n, m)) steps, where T(n, m) is the running time required to find the minimum (s, t)-cut on a graph with n vertices and m edges.

Cited by
- On complexity of substructure connectivity and restricted connectivity of graphs
  Journal of Parallel and Distributed Computing, Vol. 211
- Tractable but Hard to Approximate: The Bi‐Objective Minimum s‐t‐Cut Problem With Binary Capacities
  9 January 2026 | Networks, Vol. 87, No. 3
- A Novel Cooperative Roadside Unit Broadcast Approach for Future Intelligent Transportation Networks
  IEEE Transactions on Intelligent Transportation Systems, Vol. 27, No. 3
- Optimal Approximations for the Requirement Cut Problem on Sparse Graph Classes
  13 February 2026
- Formulations and branch-and-cut algorithms for cycle covers with up to p cycles
  European Journal of Operational Research, Vol. 327, No. 1
- Agent-Q: Fine-Tuning Large Language Models for Quantum Circuit Generation and Optimization
- Automated Road Numbering for Geospatial Maps Using Search Algorithms
- The k -way vertex cut problem on bipartite graphs: Complexity results and algorithms
  Discrete Optimization, Vol. 56
- Abstract Hardware Grounding Towards the Automated Design of Automation Systems
  21 January 2025
- Distributional limits of graph cuts on discretized grids
  Electronic Journal of Statistics, Vol. 19, No. 2
- Approximating Submodular ${k}$-Partition via Principal Partition Sequence
  16 December 2024 | SIAM Journal on Discrete Mathematics, Vol. 38, No. 4
- A Parameterized Approximation Scheme for Min $k$-Cut
  25 April 2022 | SIAM Journal on Computing, Vol. 53, No. 6
- Counting and Enumerating Optimum Cut Sets for Hypergraph k-Partitioning Problems for Fixed k
  Calvin Beideman,
  Karthekeyan Chandrasekaran,
  Weihang Wang
  13 December 2023 | Mathematics of Operations Research, Vol. 49, No. 4
- Deterministic enumeration of all minimum cut-sets and k-cut-sets in hypergraphs for fixed k
  12 September 2023 | Mathematical Programming, Vol. 207, No. 1-2
- A polynomial time algorithm for finding a minimum 4-partition of a submodular function
  6 December 2023 | Mathematical Programming, Vol. 207, No. 1-2
- Mixed-integer linear programming formulations and column generation algorithms for the Minimum Normalized Cuts problem on networks
  European Journal of Operational Research, Vol. 316, No. 2
- FocusedCleaner: Sanitizing Poisoned Graphs for Robust GNN-Based Node Classification
  IEEE Transactions on Knowledge and Data Engineering, Vol. 36, No. 6
- Understanding Accelerated Graph Clustering via Local Grouping
- Link fault tolerance of BC networks and folded hypercubes on h-extra r-component edge-connectivity
  Applied Mathematics and Computation, Vol. 462
- Partitioning subclasses of chordal graphs with few deletions
  Theoretical Computer Science, Vol. 983
- Robust Spanning Tree Problems
  10 May 2024
- On the role of entanglement in qudit-based circuit compression
  16 October 2023 | Quantum, Vol. 7
- Hypergraph partitioning using tensor eigenvalue decomposition
  21 July 2023 | PLOS ONE, Vol. 18, No. 7
- Minimizing Interference-to-Signal Ratios in Multi-Cell Telecommunication Networks
  17 July 2023 | Algorithms, Vol. 16, No. 7
- Min–Max Partitioning of Hypergraphs and Symmetric Submodular Functions
  27 April 2023 | Combinatorica, Vol. 43, No. 3
- Shift of pairwise similarities for data clustering
  22 June 2022 | Machine Learning, Vol. 112, No. 6
- New algorithms for a simple measure of network partitioning
  Theoretical Computer Science, Vol. 957
- Fault tolerance analysis for hamming graphs with large-scale faulty links based on k-component edge-connectivity
  Journal of Parallel and Distributed Computing, Vol. 173
- Fixed parameter approximation scheme for min-max k-cut
  16 June 2022 | Mathematical Programming, Vol. 197, No. 2
- A polyhedral study of lifted multicuts
  Discrete Optimization, Vol. 47
- Partitioning Subclasses of Chordal Graphs with Few Deletions
  25 April 2023
- Multicriteria cuts and size-constrained k-cuts in hypergraphs
  29 November 2021 | Mathematical Programming, Vol. 197, No. 1
- Political districting to minimize cut edges
  26 April 2022 | Mathematical Programming Computation, Vol. 14, No. 4
- Hypergraph k-Cut for Fixed k in Deterministic Polynomial Time
  Karthekeyan Chandrasekaran,
  Chandra Chekuri
  22 March 2022 | Mathematics of Operations Research, Vol. 47, No. 4
- Isolation branching: a branch and bound algorithm for the k-terminal cut problem
  7 February 2020 | Journal of Combinatorial Optimization, Vol. 44, No. 3
- Computation and algorithm for the minimum k-edge-connectivity of graphs
  15 February 2020 | Journal of Combinatorial Optimization, Vol. 44, No. 3
- An overview of graph covering and partitioning
  Discrete Mathematics, Vol. 345, No. 8
- Native measurement-based quantum approximate optimization algorithm applied to the Max K -Cut problem
  30 August 2022 | Physical Review A, Vol. 106, No. 2
- Breaking the n k barrier for minimum k -cut on simple graphs
  10 June 2022
- New Algorithms for a Simple Measure of Network Partitioning
  1 January 2023
- Packing Hypertrees and the k-cut Problem in Hypergraphs
  5 February 2023
- Multi-Objective Graph Partitioning for the Mfd-Based Perimeter Control of an Urban Network
  SSRN Electronic Journal, Vol. 137
- Model-Free Optimal Control of Linear Multiagent Systems via Decomposition and Hierarchical Approximation
  IEEE Transactions on Control of Network Systems, Vol. 8, No. 3
- A Graph-Based Approach for Data Fusion and Segmentation of Multimodal Images
  IEEE Transactions on Geoscience and Remote Sensing, Vol. 59, No. 5
- Hypergraph k-cut in randomized polynomial time
  13 November 2019 | Mathematical Programming, Vol. 186, No. 1-2
- Dynamic Resilient Network Games With Applications to Multiagent Consensus
  IEEE Transactions on Control of Network Systems, Vol. 8, No. 1
- Fixed Parameter Approximation Scheme for Min-Max k-Cut
  5 May 2021
- New Approximations and Hardness Results for Submodular Partitioning Problems
  30 June 2021
- Approximating Max k-Uncut via LP-rounding plus greed, with applications to Densest k-Subgraph
  Theoretical Computer Science, Vol. 849
- Mixed-case community detection problem in social networks: Algorithms and analysis
  Theoretical Computer Science, Vol. 854
- Low-Energy Eigenspectrum Decomposition (LEED) of Quantum-Dot Cellular Automata Networks
  IEEE Transactions on Nanotechnology, Vol. 20
- Dynamic Resilient Network Games Considering Connectivity
- Using a Min-Cut Generalisation to Go Beyond Boolean Surjective VCSPs
  24 June 2020 | Algorithmica, Vol. 82, No. 12
- Edge Manipulation Attacks for Distributed Control of TCLs in Microgrid: Impacts and Mitigation
- A Parameterized Approximation Scheme for Min $k$-Cut
- Hypergraph -cut for fixed in deterministic polynomial time
- The K ‐partitioning problem: Formulations and branch‐and‐cut
  21 April 2020 | Networks, Vol. 76, No. 3
- On integer and bilevel formulations for the k-vertex cut problem
  31 July 2019 | Mathematical Programming Computation, Vol. 12, No. 2
- Merge, Split, and Cluster: Dynamic Deployment of Stream Processing Applications
- Learned Critical Probabilistic Roadmaps for Robotic Motion Planning
- Reducing Dense Virtual Networks for Fast Embedding
  IEICE Transactions on Communications, Vol. E103.B, No. 4
- Approximating Max k-Uncut via LP-rounding Plus Greed, with Applications to Densest k-Subgraph
  9 August 2020
- Mixed-Case Community Detection Problem in Social Networks
  4 December 2020
- Minimum Violation Vertex Maps and Their Applications to Cut Problems
  22 October 2020 | SIAM Journal on Discrete Mathematics, Vol. 34, No. 4
- LP Relaxation and Tree Packing for Minimum $k$-Cut
  16 June 2020 | SIAM Journal on Discrete Mathematics, Vol. 34, No. 2
- Study and application of improved level set method with prior graph cut in PCB image segmentation
  Circuit World, Vol. 46, No. 1
- Faster Minimum k-cut of a Simple Graph
- Beating the 2-approximation factor for global bicut
  30 March 2018 | Mathematical Programming, Vol. 177, No. 1-2
- The number of minimum k -cuts: improving the Karger-Stein bound
  23 June 2019
- Algorithms and complexity of range clustering
  19 September 2018 | Networks, Vol. 73, No. 2
- The vertex k -cut problem
  Discrete Optimization, Vol. 31
- From Loop Fusion to Kernel Fusion: A Domain-Specific Approach to Locality Optimization
- Solving Coalition Structure Generation Problems over Weighted Graph
  21 October 2019
- Approximation and hardness results for the Max k-Uncut problem
  Theoretical Computer Science, Vol. 749
- Faster Exact and Approximate Algorithms for k-Cut
- Forming k coalitions and facilitating relationships in social networks
  Artificial Intelligence, Vol. 259
- Joint Cuts and Matching of Partitions in One Graph
- The Critical Node Detection Problem in networks: A survey
  Computer Science Review, Vol. 28
- Isolation Branching: A Branch and Bound Algorithm for the k-Terminal Cut Problem
  16 November 2018
- Inapproximability of Maximum Biclique Problems, Minimum k-Cut and Densest At-Least-k-Subgraph from the Small Set Expansion Hypothesis
  17 January 2018 | Algorithms, Vol. 11, No. 1
- Clustering by Shift
- Hermes: Latency Optimal Task Assignment for Resource-constrained Mobile Computing
  IEEE Transactions on Mobile Computing, Vol. 16, No. 11
- A feasible graph partition framework for parallel computing of big graph
  Knowledge-Based Systems, Vol. 134
- A graph-based approach for feature extraction and segmentation of multimodal images
- Operation of shunting yards: train-to-yard assignment problem
  1 June 2016 | Journal of Business Economics, Vol. 87, No. 4
- Revisiting the Design of Data Stream Processing Systems on Multi-Core Processors
- A Comparative Study of Local Search Algorithms for Correlation Clustering
  15 August 2017
- Organizing objects by predicting user preferences through collaborative filtering
  11 July 2016 | The International Journal of Robotics Research, Vol. 35, No. 13
- Graph partitioning-based zonal reserve allocation for congestion management in power systems with wind resources
- An extended edge-representative formulation for the K-partitioning problem
  Electronic Notes in Discrete Mathematics, Vol. 52
- Reducing dense virtual networks for fast embedding
- Terminal-set-enhanced community detection in social networks
- Approximation and Hardness Results for the Max k-Uncut Problem
  31 October 2016
- Recent Advances in Graph Partitioning
  11 November 2016
- An O(1)-Approximation for Minimum Spanning Tree Interdiction
- Using unmanned aerial vehicles as relays in wireless balloon networks
- Estimating minimum sum-rate for cooperative data exchange
- Robot, organize my shelves! Tidying up objects by predicting user preferences
- Hermes: Latency optimal task assignment for resource-constrained mobile computing
- Polyhedral study of the connected subgraph problem
  Discrete Mathematics, Vol. 338, No. 1
- General Bibliography
  8 August 2014
- The Maximum Cut Problem
  8 August 2014
- Clique Cover and Graph Separation
  1 May 2014 | ACM Transactions on Computation Theory, Vol. 6, No. 2
- An O⁎(1.84k) parameterized algorithm for the multiterminal cut problem
  Information Processing Letters, Vol. 114, No. 4
- Complexity and approximability of the k ‐way vertex cut
  15 October 2013 | Networks, Vol. 63, No. 2
- The Supervised Normalized Cut Method for Detecting, Classifying, and Identifying Special Nuclear Materials
  Yan T. Yang,
  Barak Fishbain,
  Dorit S. Hochbaum,
  Eric B. Norman,
  Erik Swanberg
  11 April 2013 | INFORMS Journal on Computing, Vol. 26, No. 1
- A Complex Semidefinite Programming Rounding Approximation Algorithm for the Balanced Max-3-Uncut Problem
- Computing minimum multiway cuts in hypergraphs
  Discrete Optimization, Vol. 10, No. 4
- The Maximum Cut Problem
  13 February 2013
- The Problem of Cell Formation: Ideas and Their Applications
  21 June 2013
- The p-Median Problem
  21 June 2013
- Application of the PMP to Cell Formation in Group Technology
  21 June 2013
- The Minimum Multicut Problem and an Exact Model for Cell Formation
  21 June 2013
- An O *(1.84 k ) Parameterized Algorithm for the Multiterminal Cut Problem
- Modularity maximization in networks by variable neighborhood search
- Polynomial‐time algorithms for solving a class of critical node problems on trees and series‐parallel graphs
  28 October 2011 | Networks, Vol. 60, No. 2
- An exact model for cell formation in group technology
  13 May 2012 | Computational Management Science, Vol. 9, No. 3
- Divide-and-Conquer Algorithms for Partitioning Hypergraphs and Submodular Systems
  21 December 2010 | Algorithmica, Vol. 62, No. 3-4
- Clique Cover and Graph Separation: New Incompressibility Results
- An efficient integer programming formulation for the assignment of base stations to controllers in cellular networks
  Computer Networks, Vol. 56, No. 1
- Minimum d-blockers and d-transversals in graphs
  5 June 2010 | Journal of Combinatorial Optimization, Vol. 22, No. 4
- Analysis of Heuristic Graph Partitioning Methods for the Assignment of Packet Control Units in GERAN
  26 March 2010 | Wireless Personal Communications, Vol. 60, No. 4
- Approximation Algorithms for Submodular Multiway Partition
- The Minimum k-way Cut of Bounded Size is Fixed-Parameter Tractable
- Graph-Cut Based Coscheduling Strategy Towards Efficient Execution of Scientific Workflows in Collaborative Cloud Environments
- Tight Approximation Ratio of a General Greedy Splitting Algorithm for the Minimum k-Way Cut Problem
  8 May 2009 | Algorithmica, Vol. 59, No. 4
- Finding minimum 3-way cuts in hypergraphs
  Information Processing Letters, Vol. 110, No. 14-15
- Simple and Improved Parameterized Algorithms for Multiterminal Cuts
  8 May 2009 | Theory of Computing Systems, Vol. 46, No. 4
- Polynomial Time Algorithms for Ratio Regions and a Variant of Normalized Cut
  IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 32, No. 5
- Efficient Algorithms for the Problems of Enumerating Cuts by Non-decreasing Weights
  14 February 2009 | Algorithmica, Vol. 56, No. 3
- Generating partitions of a graph into a fixed number of minimum weight cuts
  Discrete Optimization, Vol. 7, No. 1-2
- Computing Minimum Multiway Cuts in Hypergraphs from Hypertree Packings
- Multi-provider service negotiation and contracting in network virtualization
- Divide-and-Conquer Algorithms for Partitioning Hypergraphs and Submodular Systems
- Minimum k-way cuts via deterministic greedy tree packing
  17 May 2008
- Efficient Algorithms for the k Smallest Cuts Enumeration
- Finding Minimum 3-Way Cuts in Hypergraphs
- Algorithms for Multiterminal Cuts
- An Improved Divide-and-Conquer Algorithm for Finding All Minimum k-Way Cuts
- Algorithms for the minimum partitioning problems in graphs
  23 April 2007 | Electronics and Communications in Japan (Part III: Fundamental Electronic Science), Vol. 90, No. 10
- Automatic Constraint Partitioning to Speed Up CLP Execution
- Minimum cost subpartitions in graphs
  Information Processing Letters, Vol. 102, No. 2-3
- BDFS: A Real-Time Search Algorithm for Central Office (CO) Optimization
- Approximating Minimum k-partitions in Submodular Systems
- A Deterministic Algorithm for Finding All Minimum k ‐Way Cuts
  SIAM Journal on Computing, Vol. 36, No. 5
- Two-Server Network Disconnection Problem
- The Steiner k-Cut Problem
  SIAM Journal on Discrete Mathematics, Vol. 20, No. 1
- Network capacity recovery and efficient capacity deployment in switching centers
  17 February 2005 | Bell Labs Technical Journal, Vol. 9, No. 4
- Tight lower bounds for certain parameterized NP-hard problems
  Information and Computation, Vol. 201, No. 2
- An Automated Method for Exploring Targeted Substructural Diversity within Sets of Chemical Structures
  16 August 2005 | Journal of Chemical Information and Modeling, Vol. 45, No. 5
- Minimal multicut and maximal integer multiflow: A survey
  European Journal of Operational Research, Vol. 162, No. 1
- On generalized greedy splitting algorithms for multiway partition problems
  Discrete Applied Mathematics, Vol. 143, No. 1-3
- Cutting Up Is Hard To Do
  Electronic Notes in Theoretical Computer Science, Vol. 78
- Approximating Steiner k-Cuts
  18 June 2003
- New Directions and New Challenges in Algorithm Design and Complexity, Parameterized
- The Semidefinite Relaxation of the k-Partition Polytope Is Strong
  21 May 2002
- A new—old algorithm for minimum‐cut and maximum‐flow in closure graphs
  6 June 2001 | Networks, Vol. 37, No. 4
- A Unified Framework for Approximating Multiway Partition Problems
  4 December 2001
- Compact Representations of Cuts
  SIAM Journal on Discrete Mathematics, Vol. 14, No. 1
- A Faster Algorithm for Computing Minimum 5-Way and 6-Way Cuts in Graphs
  Journal of Combinatorial Optimization, Vol. 4, No. 2
- Separation of Partition Inequalities
  Mourad Baïou,
  Francisco Barahona,
  Ali Ridha Mahjoub,
  1 May 2000 | Mathematics of Operations Research, Vol. 25, No. 2
- On the k-cut problem
  Operations Research Letters, Vol. 26, No. 3
- Increasing the Weight of Minimum Spanning Trees
  Journal of Algorithms, Vol. 33, No. 2
- Crossing properties of multiterminal cuts
  Networks, Vol. 34, No. 3
- A Faster Algorithm for Computing Minimum 5-Way and 6-Way Cuts in Graphs
  25 June 1999
- A Fast Algorithm for Computing Minimum 3-Way and 4-Way Cuts
  30 April 1999
- Optimization algorithms for large self-structuring networks
- The planar multiterminal cut problem
  Discrete Applied Mathematics, Vol. 85, No. 3
- Optimal cuts in graphs and statistical mechanics
  Mathematical and Computer Modelling, Vol. 26, No. 8-10
- A Hypergraph Framework for Optimal Model-Based Decomposition of Design Problems
  Computational Optimization and Applications, Vol. 8, No. 2
- On the Task Assignment Problem: Two New Efficient Heuristic Algorithms
  Journal of Parallel and Distributed Computing, Vol. 42, No. 1
- A new and improved algorithm for the 3-cut problem
  Operations Research Letters, Vol. 21, No. 5
- Path Costs in Evolutionary Tree Reconstruction
  Journal of Computational Biology, Vol. 4, No. 2
- Extended formulations for the A-cut problem
  Mathematical Programming, Vol. 73, No. 1
- Optimal Model-Based Decomposition of Powertrain System Design
  1 December 1995 | Journal of Mechanical Design, Vol. 117, No. 4
- The Complexity of Multiterminal Cuts
  SIAM Journal on Computing, Vol. 23, No. 4

cover image Mathematics of Operations Research

Volume 19, Issue 1

February 1994

Pages 1-256

Article Information

Metrics

Information

Published Online:February 01, 1994

Cite as

Olivier Goldschmidt, Dorit S. Hochbaum, (1994) A Polynomial Algorithm for the k-cut Problem for Fixed k. Mathematics of Operations Research 19(1):24-37.

https://doi.org/10.1287/moor.19.1.24

Keywords

PDF download

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

A Polynomial Algorithm for the k-cut Problem for Fixed k

Abstract

Volume 19, Issue 1

Article Information

Metrics

Information

Cite as

Keywords

Sign Up for INFORMS Publications Updates and News