The vertex k-cut problem

Denis Cornaz, Fabio Furini, Mathieu Lacroix, Enrico Malaguti, Ali Ridha Mahjoub, Sébastien MartinDiscret. Optim 2019 · DOI

TL;DR

This paper tackles the computationally challenging vertex k-cut problem, aiming to find the smallest set of vertices whose removal disconnects a graph into at least k components. The authors prove this problem is NP-hard for fixed k ≥ 3 and introduce novel integer linear programming formulations, including an exponential-size one solved efficiently using a Branch-and-Price algorithm. Their work provides a significant advancement in solving this fundamental graph partitioning problem.

What Problem Does This Paper Address?

Graph partitioning is a fundamental problem in computer science with applications ranging from network design to parallel computing. The vertex k-cut problem specifically asks for the minimum number of vertices to remove from a graph to create at least k disconnected components. While related problems like the edge k-cut have been studied extensively, the vertex k-cut problem has received less attention, particularly concerning efficient exact algorithms. Previous work established its NP-hardness for general k, but the complexity for fixed k remained an open question. This paper addresses this by proving NP-hardness for fixed k ≥ 3 and developing effective computational methods to solve it.

Methods

The authors propose two main approaches:

  1. Compact Integer Linear Programming (ILP) Formulation (ILPc): This formulation is derived from a reformulation of the vertex k-cut problem as a maximum stable set problem on a specially constructed k-partite graph. This leads to a compact ILP model, which is then solved using a standard ILP solver (CPLEX).
  2. Exponential-Size ILP Formulation (ILPE) with Branch-and-Price: This approach leverages an extended formulation with an exponential number of variables, representing all possible subsets of vertices that could form disconnected components. To handle this complexity, they employ a Branch-and-Price algorithm. This algorithm combines:
  3. Column Generation: To efficiently solve the linear programming (LP) relaxation of the exponential formulation by dynamically adding variables (columns) as needed. The pricing subproblem, crucial for column generation, is shown to be solvable in polynomial time using min-cut/max-flow techniques.
  4. Branching Scheme: A two-level branching strategy is introduced to handle fractional solutions from the LP relaxation and guide the search towards an integer solution.

Datasets

The authors evaluate their methods on several benchmark datasets:

  • DIMACS Challenge Instances: Two sets of instances from the DIMACS challenge (2nd and 10th) were used, totaling 49 and 38 instances respectively for k=5 and k=10. These are classical graph instances used in various combinatorial optimization problems.
  • Intersection Graph Instances: Three sets of instances derived from intersection graphs of coefficient matrices of linear systems, collected from applications in physics, electrical engineering, meteorology, economics, and mathematics. These instances range from 49 to 136 vertices.

Key Insights and Ideas

  • NP-Hardness for Fixed k ≥ 3: A significant theoretical contribution is proving that the vertex k-cut problem is NP-hard even when k is fixed and greater than or equal to 3. This was demonstrated through a reduction from the maximum stable set problem in tripartite graphs.
  • Equivalence to Maximum Stable Set: The paper establishes a strong connection between the vertex k-cut problem and the maximum stable set problem on a constructed k-partite graph. This equivalence is key to developing the ILP formulations.
  • Strength of the Extended Formulation: The exponential-size formulation (ILPE) provides a significantly stronger linear programming relaxation compared to the compact formulation (ILPc). This stronger relaxation leads to fewer nodes explored in the Branch-and-Price algorithm, especially for larger values of k.
  • Complementarity of Methods: While the Branch-and-Price algorithm excels for larger k and more complex instances, the compact formulation solved by CPLEX remains competitive and often faster for smaller values of k. This suggests that these methods are complementary rather than mutually exclusive.
  • Polynomial Solvability of Pricing Subproblem: A crucial aspect of the Branch-and-Price approach is the efficient, polynomial-time solvability of its pricing subproblem using min-cut/max-flow algorithms. This is a common theme in successful Branch-and-Price implementations.

Key Results

  • NP-Hardness Proof: The paper formally proves the NP-hardness of the vertex k-cut problem for any fixed k ≥ 3.
  • Computational Performance:
    • For smaller values of k (e.g., k=5), the compact formulation solved by CPLEX with preprocessing often outperforms the Branch-and-Price algorithm in terms of CPU time, though it explores significantly more nodes.
  • As k increases, the Branch-and-Price algorithm becomes increasingly advantageous, solving more instances and requiring fewer nodes. For k=20, Branch-and-Price solves instances that CPLEX+reduction cannot within the time limit.
  • The Branch-and-Price algorithm consistently explores fewer nodes than CPLEX+reduction, especially for larger k, demonstrating the effectiveness of the stronger LP relaxation.
  • The paper highlights instances where one method succeeds while the other fails, underscoring their complementary nature. For example, for k=15 on Intersection Graph instances, 7 instances were solved by Branch-and-Price while CPLEX+reduction failed, and vice versa.

Limitations and Future Work

  • Instance Size: While the methods are effective, the computational experiments were limited to instances with up to 150 vertices. Scaling to much larger graphs remains a challenge.
  • Time Limits: For some instances, neither method could find an optimal solution within the 3600-second time limit, indicating that the problem remains hard for very challenging instances.
  • Branching Complexity: In rare cases, the pricing subproblem in the Branch-and-Price algorithm might become NP-hard if incompatibility constraints are introduced, though this was observed to be infrequent.
  • Future Work: The authors suggest exploring further improvements to the Branch-and-Price algorithm, potentially by developing more sophisticated branching rules or investigating other techniques for solving the pricing subproblem. Further analysis of the problem's complexity on specific graph classes could also be beneficial.

Summary updated

BibTeX
@article{cornaz2019vertex,
  author = {Denis Cornaz and Fabio Furini and Mathieu Lacroix and Enrico Malaguti and Ali Ridha Mahjoub and Sébastien Martin},
  title = {{The vertex k-cut problem}},
  journal = {Discret. Optim.},
  year = {2019},
  doi = {10.1016/j.disopt.2018.07.003},
}
Figure