Text

Hypergraph k-Cut for Fixed k in Deterministic Polynomial Time

We consider the Hypergraph-k-Cut problem. The input consists of a hypergraph G=(V,E) with nonnegative hyperedge-costs c:E→R+ and a positive integer k. The objective is to find a minimum cost subset F⊆E such that the number of connected components in G – F is at least k. An alternative formulation of the objective is to find a partition of V into k nonempty sets V1,V2,…,Vk so as to minimize the cost of the hyperedges that cross the partition. Graph-k-Cut, the special case of Hypergraph-k-Cut obtained by restricting to graph inputs, has received considerable attention. Several different approaches lead to a polynomial-time algorithm for Graph-k-Cut when k is fixed, starting with the work of Goldschmidt and Hochbaum (Math of OR, 1994). In contrast, it is only recently that a randomized polynomial time algorithm for Hypergraph-k-Cut was developed (Chandrasekaran, Xu, Yu, Math Programming, 2019) via a subtle generalization of Karger’s random contraction approach for graphs. In this work, we develop the first deterministic algorithm for Hypergraph-k-Cut that runs in polynomial time for any fixed k. We describe two algorithms both of which are based on a divide and conquer approach. The first algorithm is simpler and runs in nO(k2)m time while the second one runs in nO(k)m time, where n is the number of vertices and m is the number of hyperedges in the input hypergraph. Our proof relies on new structural results that allow for efficient recovery of the parts of an optimum k-partition by solving minimum (S,T)-terminal cuts. Our techniques give new insights even for Graph-k-Cut.

Ketersediaan

Informasi Detail

Judul Seri

MATHEMATICS OF OPERATIONS RESEARCH; Vol.47 No.4 November 2022

No. Panggil

-

Penerbit

: .,

Deskripsi Fisik

p. 3380-3399

Bahasa

English

ISBN/ISSN

-

Klasifikasi

NONE

Tipe Isi

-

Tipe Media

-

Tipe Pembawa

-

Edisi

-

Subjek

ALGORITHMS
HYPERGRAPHS
K-CUT

Info Detail Spesifik

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

Pernyataan Tanggungjawab

Karthekeyan Chandrasekaran, Chandra Chekuri

Versi lain/terkait

Lampiran Berkas

Komentar