Parameterization and approximation are two popular ways of coping with NP-hard
problems. More recently, the two have also been combined to derive many interesting …

In Maximum $ k $-Vertex Cover (Max $ k $-VC), the input is an edge-weighted graph $ G $
and an integer $ k $, and the goal is to find a subset $ S $ of $ k $ vertices that maximizes …

In the Min k-Cut problem, the input consists of an edge weighted graph G and an integer k,
and the task is to partition the vertex set into k nonempty sets, such that the total weight of the …

Over the past decade, many results have focused on the design of parameterized
approximation algorithms for W [1]-hard problems. However, there are fundamental …

For a fixed integer k ≥ 2 k≥ 2, the hypergraph k-cut problem asks for a smallest subset of
hyperedges whose removal leads to at least k connected components in the remaining …

Karger used spanning tree packings DR Karger, J. ACM, 47 (2000), pp. 46--76 to derive a
near linear-time randomized algorithm for the global minimum cut problem as well as a …

Ensuring fairness in computational problems has emerged as a key topic during recent
years, buoyed by considerations for equitable resource distributions and social justice. It is …

In the k-cut problem, we are given an edge-weighted graph and want to find the least-weight
set of edges whose deletion breaks the graph into k connected components. Algorithms due …

The Parameterized Inapproximability Hypothesis (PIH) asserts that no fixed parameter
tractable (FPT) algorithm can distinguish a satisfiable CSP instance, parameterized by the …

On hypergraphs with m hyperedges and n vertices, where p denotes the total size of the
hyperedges, we provide the following results: We give an algorithm that runs in Õ (mn 2 k–2) …