2016 journal article
On size-constrained minimum s-t cut problems and size-constrained dense subgraph problems
THEORETICAL COMPUTER SCIENCE, 609, 434–442.
author keywords: At-least-k-subgraph problem; At-most-k-subgraph problem; Approximation algorithm; The minimum s-t cut with at-least-k vertices problem; The minimum s-t cut with at-most-k vertices problem; The minimum s-t cut with exactly k vertices problem
TL;DR:
The minimum s-t cut with at-least-k vertices problem, the minimum s -t cutWith at-most-k-subgraph problem, and the Minimum s-T cut with exactly k vertices problems are introduced and it is proved that they are NP-complete.
(via Semantic Scholar)
manuscript.elsevier.com (publisher PDF)
UN Sustainable Development Goal Categories
11. Sustainable Cities and Communities
(Web of Science)
Source: Web Of Science
Added: August 6, 2018
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−1k−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δ), for some δ<1/3.