On size-constrained minimum s-t cut problems and size-constrained dense subgraph problems

Abstract

In some application cases, the solutions of combinatorial optimization problems on graphs should satisfy an additional vertex size constraint. In this paper, we consider size-constrained minimum s-t cut problems and size-constrained dense subgraph problems. We introduce the minimum s-t cut with at-least-k vertices problem, the minimum s-t cut with at-most-k vertices problem, and the minimum s-t cut with exactly k vertices problem. We prove that they are NP-complete. Thus, they are not polynomially solvable unless P = NP. On the other hand, we also study the densest at-least-k-subgraph problem (DalkS) and the densest at-most-k-subgraph problem (DamkS) introduced by Andersen and Chellapilla [1]. We present a polynomial time algorithm for DalkS when k is bounded by some constant c. We also present two approximation algorithms for DamkS. The first approximation algorithm for DamkS has an approximation ratio of n-1/k-1, where n is the number of vertices in the input graph. The second approximation algorithm for DamkS has an approximation ratio of O (n(delta)), for some delta < 1/3. (C) 2015 Elsevier B.V. All rights reserved.