Cover Image

Conditionally Tight Algorithms for Maximum k-Coverage and Partial k-Dominating Set via Arity-Reducing Hypercuts

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Fischer, Nick, Künnemann, Marvin, Redzic, Mirza
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Fine-Grained Complexity of Multiple Domination and Dominating Patterns in Sparse Graphs
by: Künnemann, Marvin, et al.
Published: (2024)

Fine-Grained Classification Of Detecting Dominating Patterns
by: Dransfeld, Jonathan, et al.
Published: (2025)

Engineering Dominating Patterns: A Fine-grained Case Study
by: Dransfeld, Jonathan, et al.
Published: (2025)

Classifying Identities: Subcubic Distributivity Checking and Hardness from Arithmetic Progression Detection
by: Dudek, Bartłomiej, et al.
Published: (2026)

Faster Combinatorial k-Clique Algorithms
by: Abboud, Amir, et al.
Published: (2024)

Maximum Coverage $k$-Antichains and Chains: A Greedy Approach
by: Cáceres, Manuel, et al.
Published: (2025)

On Tight FPT Time Approximation Algorithms for k-Clustering Problems
by: Dai, Han, et al.
Published: (2025)

Dominating Set with Quotas: Balancing Coverage and Constraints
by: Chatterjee, Sobyasachi, et al.
Published: (2026)

On the Efficient Discovery of Maximum $k$-Defective Biclique
by: Cui, Donghang, et al.
Published: (2025)

A Simple PTAS for Weighted $k$-means and Sensor Coverage
by: Pareek, Akash, et al.
Published: (2025)

Approximation Algorithms for Connected Maximum Coverage, Minimum Connected Set Cover, and Node-Weighted Group Steiner Tree
by: D'Angelo, Gianlorenzo, et al.
Published: (2025)

Weighted $k$-Path and Other Problems in Almost $O^*(2^k)$ Deterministic Time via Dynamic Representative Sets
by: Nederlof, Jesper
Published: (2025)

Two New Upper Bounds for the Maximum k-plex Problem
by: Zheng, Jiongzhi, et al.
Published: (2023)

On $b$-Matching and Fully-Dynamic Maximum $k$-Edge Coloring
by: El-Hayek, Antoine, et al.
Published: (2023)

Optimal-Length Labeling Schemes and Fast Algorithms for k-gathering and k-broadcasting
by: Ganczorz, Adam, et al.
Published: (2025)

Logarithmic Approximations for Fair k-Set Selection
by: Li, Shi, et al.
Published: (2025)

A Faster Branching Algorithm for the Maximum $k$-Defective Clique Problem
by: Luo, Chunyu, et al.
Published: (2024)

Faster Approximation Algorithms for k-Center via Data Reduction
by: Filtser, Arnold, et al.
Published: (2025)

On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP
by: S., Karthik C., et al.
Published: (2024)

KD-Club: An Efficient Exact Algorithm with New Coloring-based Upper Bound for the Maximum k-Defective Clique Problem
by: Jin, Mingming, et al.
Published: (2023)

Non-Redundancy of Low-Arity Symmetric Boolean CSPs
by: Sharma, Amatya, et al.
Published: (2026)

Non-Adaptive Evaluation of $k$-of-$n$ Functions: Tight Gap and a Unit-Cost PTAS
by: Nielsen, Mads Anker, et al.
Published: (2025)

FPT Approximations for Connected Maximum Coverage
by: Inamdar, Tanmay, et al.
Published: (2026)

Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part I: Algorithmic Results
by: Focke, Jacob, et al.
Published: (2022)

Algorithms and Hardness Results for the $(k,\ell)$-Cover Problem
by: Madani, Amirali, et al.
Published: (2025)

Weighted $k$-Server Admits an Exponentially Competitive Algorithm
by: Bijoy, Adithya, et al.
Published: (2025)

Review of Three Algorithms That Build k-d Trees
by: Brown, Russell A.
Published: (2025)

Semi-Streaming Algorithms for Weighted $k$-Disjoint Matchings
by: Ferdous, S M, et al.
Published: (2023)

Reconstructing Sets of Strings from Their k-way Projections: Algorithms & Complexity
by: Tate, Elise, et al.
Published: (2025)

On $k$-connectivity oracles in $k$-connected graphs
by: Nutov, Zeev
Published: (2026)

Dynamic $((1+ε)\ln n)$-Approximation Algorithms for Minimum Set Cover and Dominating Set
by: Solomon, Shay, et al.
Published: (2023)

An ETH-Tight FPT Algorithm for Rejection-Proof Set Packing with Applications to Kidney Exchange
by: Jansen, Bart M. P., et al.
Published: (2025)

Tight Bounds for Sorting Under Partial Information
by: van der Hoog, Ivor, et al.
Published: (2024)

Beating Bellman's Algorithm for Subset Sum
by: Bringmann, Karl, et al.
Published: (2024)

Faster Algorithms for $(2k-1)$-Stretch Distance Oracles
by: Kadria, Avi, et al.
Published: (2025)

A $(2+\varepsilon)$-Approximation Algorithm for Metric $k$-Median
by: Cohen-Addad, Vincent, et al.
Published: (2025)

Faster and Simpler Greedy Algorithm for $k$-Median and $k$-Means
by: la Tour, Max Dupré, et al.
Published: (2024)

A Simple Algorithm for Trimmed Multipoint Evaluation
by: Fischer, Nick, et al.
Published: (2025)

Linear-Time Algorithms for k-Edge-Connected Components, k-Lean Tree Decompositions, and More
by: Korhonen, Tuukka
Published: (2024)

Breaking the Barrier $2^k$ for Subset Feedback Vertex Set in Chordal Graphs
by: Bai, Tian, et al.
Published: (2022)