CS Paper Radar

Maximum Strong Independent Sets in Hypergraphs: Reductions, Bounds, and Greedy Certificates

Yingquan, Wu, Jason Cong

cs.LG ·submitted 2026-09-16 00:23 UTC · v1
theory

Abstract

We study the maximum strong independent set problem in a finite hypergraph: find the largest vertex set that intersects every hyperedge in at most one vertex. This objective arises whenever each observed block is a local incompatibility constraint but transitive closure across overlapping blocks is not justified. A motivating example is multi-band LSH-MinHash deduplication, where each collision bucket gives local evidence, while connected-component contraction can impose spurious global equivalences. The paper develops an incidence-structural toolkit for this problem. We prove exact reductions for dominance, incidence twins, and weight-1 blocks; derive closed-form and low-weight upper bounds; introduce puncturing and covering certificates that sharpen those bounds; and analyze a layered greedy clustering algorithm driven by block weights and residual incidence. The algorithmic analysis includes feasibility, maximality, conditional optimality, a layered witness-matching upper bound, and incidence-local complexity bounds. The results give correctness, termination, fixed-point, and optimality certificates for broad incidence families, together with examples showing when different certificates separate or coincide.

Closest papers

Nearest neighbours by meaning across the whole index.

Lower Bounds for Minimal-Transversal Enumeration of Bounded-Dimension Hypergraphs and the maximum Minimal Hitting Set Problem

cs.CC ·2026-10-20 ·Arnaud Mary
similarity 0.61
Abstract

We present lower bounds for the maximum minimal hitting set problem and for the problem of enumeration of minimal transversals in bounded-dimension hypergraphs. Our starting point is the recent reduction of Kobayashi, Kurita, and Wasa (2026), developed to establish ETH-based hardness of hypergraph dualization. Adapting their construction, we show that, under ETH, deciding whether a hypergraph $\mathcal{G}$ with $n$ vertices and $m$ hyperedges has a minimal transversal of size at least $k$ cannot be done in time $n^{f(k)}m^{o(k)}$, for an arbitrary computable $f$. We transfer this bound to the following decision problem: given a dimension-at-most-$r$ hypergraph and a family of $s$ of its minimal transversals, decide whether another exists. Under ETH, this problem admits no uniform algorithm with running time $n^{f(r)}(s+1)^{o(r)}$. Under SETH, for every fixed $t \geq 2$, it admits no algorithm with running time $\poly(|\mathcal{G}|)(s+1)^c$ for dimension at most $2t$ and any $c<t$. As corollaries, the same exponent obstructions hold for the total time of any output-polynomial enumeration algorithm, with $s$ replaced by the total number of minimal transversals. In particular, polynomial delay is excluded under SETH already for dimension at most four.

0.15

Implicit Hitting Set Enumeration for Power Dominating Sets

cs.DS ·2026-10-16 ·Thomas Bläsius, Max Göttlicher, Martin Schirneck
similarity 0.60
Abstract

The Transversal Hypergraph problem asks to enumerate (list) all inclusion-minimal hitting sets of a hypergraph. It usually assumes that the input is completely known and does not change over the course of the enumeration. In many applications, the underlying hypergraph is too large or expensive to compute. This motivated the implicit hitting set framework [Chandrasekaran, Karp, Moreno-Centeno, and Vempala, SODA 2011] for the corresponding optimization problem of finding a smallest hitting set. Access to the input is given by an oracle that either confirms that a query set $S$ is a hitting set, or reveals a new hyperedge disjoint from $S$. We adapt this framework to enumeration. We show for a general class of algorithms that they are able to find all hitting sets when given access to such an oracle, even if the hypergraph is a priori unknown. We also prove that the current fastest Transversal Hypergraph algorithm, Minimal-to-Maximal Conversion Search by Murakami and Uno [DAM 2014], belongs to this class. We then engineer an implicit hitting set algorithm for the enumeration of minimal power dominating sets in graphs. A power dominating set is a selection of vertices that "observe" all vertices by exhaustively applying two rules: if a vertex is dominated by the selection, it becomes observed; and if an observed vertex has a unique unobserved neighbor, this neighbor becomes observed as well. An experimental evaluation on a collection of power grid instances from the literature shows that our approach achieves very high throughput rates.

0.25

The Strong Total Cover Problem

cs.DM cs.CCmath.CO ·2026-10-16 ·Manuel Aprile, Luca Ferrarini
similarity 0.60
Abstract · 28 pages, 4 figures

The Strong Total Cover Problem (STCP) is a novel covering problem defined on a graph $G = (V, E)$, where the objective is to find a minimum-cardinality subset $T \subseteq V \cup E$ such that every element of $V \cup E$ is covered. In this setting, a vertex covers itself and all its incident edges, while an edge covers itself together with its two endpoints. The STCP resembles classical covering problems such as Vertex Cover and Edge Cover problems, and naturally arises as the dual of the total matching problem. In this paper, we investigate the STCP from algorithmic, complexity, and polyhedral perspectives. We first establish close connections between STCP, the Dominating Set Problem, and the Maximum Induced Matching Problem. These relationships provide structural insights, imply the NP-hardness of STCP, and identify graph classes for which the problem is polynomial-time solvable. We then investigate the weighted version of STCP, showing that it remains NP-hard even on complete graphs with binary weights. On the other hand, we present a 2-approximation algorithm, and a polynomial-time algorithm for complete bipartite graphs. On the polyhedral side, we introduce the Strong Total Cover Polytope and derive several families of valid inequalities, some of which are shown to define facets. Finally, we provide a complete linear description of the associated polytope for triangular cactus graphs, revealing an interesting contrast with the considerably more intricate facial structure of the dominating set polytope on cactus graphs.

0.25

Max Weight Independent Set in graphs with no long claws nor large induced bicliques

cs.DS ·2026-10-30 ·Maria Chudnovsky, Paweł Rzążewski
similarity 0.60
Abstract

The complexity of Max Weight Independent Set (MWIS) in graphs excluding a fixed subdivided claw is one of the central open problems in algorithmic graph theory. We show that MWIS can be solved in polynomial time in graphs excluding a fixed subdivided claw and a fixed biclique as an induced subgraph. This strengthens a result of Abrishami, Chudnovsky, Dibek, Pilipczuk, and Rzążewski [ACM TALG 2026] who showed an analogous result, but under a stronger assumption that some biclique is excluded as a subgraph.

0.19

Minimum Membership Dominating Set and Its Generalization: Leafage vs. Asteroidal Number

cs.DS ·2026-11-10 ·Yuma Tamura, Daichi Wakayama, Akira Suzuki, Xiao Zhou
published similarity 0.59
Abstract · Accepted for publication in IPEC2026

The Dominating Set problem is known to be fixed-parameter tractable when parameterized by leafage, a structural graph parameter defined on chordal graphs. We investigate whether this tractability extends to its variants with natural constraints. Specifically, we study the Minimum Membership Dominating Set problem and its generalization, the Min. $(σ, ρ)$-Dominating Set problem. Given a graph $G$ and a positive integer $\ell$, Minimum Membership Dominating Set asks whether there is a dominating set $D$ such that every vertex in $G$ is dominated by at most $\ell$ vertices in $D$. We first show a negative result: Minimum Membership Dominating Set parameterized by leafage plus $\ell$ is W[1]-hard, demonstrating that even this natural constraint serves as a severe barrier to designing FPT algorithms. To complement this, we present an XP algorithm for the Min. $(σ, ρ)$-Dominating Set problem parameterized by asteroidal number plus $μ$, where $σ$ and $ρ$ are finite sets of non-negative integers and $μ$ is the maximum value in $σ\cup ρ$. Note that asteroidal number generalizes leafage to arbitrary graphs. Combining this algorithm with our structural bound that every graph $G$ admits a dominating set such that no vertex is dominated by more than $7\mathsf{an}(G)-6$ vertices, where $\mathsf{an}(G)$ denotes the asteroidal number of $G$, we show that Minimum Membership Dominating Set admits an XP algorithm parameterized solely by asteroidal number.

0.32

Detection and Construction of Small Blocking Sets via Critical Independent Sets and Matching Decomposition

cs.DM ·2026-10-09 ·Quanlong Niu, Riheng Jia
theory similarity 0.59
Abstract

The small blocking set detection and construction problem asks whether a given connected simple graph contains a nonempty independent set whose cardinality equals the size of its neighborhood and is strictly less than half the number of vertices, and, if so, how to construct such a set. Previous work characterized restless explorability in vertex-permuted temporal graphs using small blocking sets, but left the computational complexity of detecting their existence as an open problem. We give a polynomial-time algorithm for detection and construction. Specifically, we first compute a maximum-cardinality critical independent set and use its difference and cardinality to handle the cases that admit an immediate solution. In the remaining boundary case, where the critical difference is zero and the selected independent set contains exactly half the vertices, we establish a projection theorem using a perfect matching and neighborhood counting: the graph contains a small blocking set if and only if the selected independent set contains a nonempty proper tight subset. We then use matching contraction to translate the tight-subset condition into the absence of arcs leaving a vertex subset in an auxiliary digraph. This yields a strong-connectivity test for the existence of a small blocking set and, when one exists, a construction based on a sink strongly connected component. The result resolves the open complexity question for small blocking set detection and provides an explicit construction algorithm.

0.15

Multiobjective Hypergraph Min-Cut in Quasi-Polynomial Time

cs.DS ·2026-09-03 ·Karthekeyan Chandrasekaran, Chandra Chekuri, Weihao Zhu
similarity 0.59
Abstract

We study the multiobjective hypergraph min-cut problem: Given a hypergraph $H=(V,E)$ and $k$ cost functions $c_1, c_2, \ldots, c_k:E\to\mathbb{Z}_{\ge 0}$, the goal is to find a non-empty proper subset $U\subsetneq V$ of vertices with minimum $\max_{i\in [k]} c_i(δ(U))$. When $k$ is part of input, the problem is NP-hard (even in graphs). We focus on fixed-constant $k$ setting (e.g., $k=1, 2, 3, \ldots$). Single-objective hypergraph min-cut as well as multiobjective graph min-cut for a constant number of objectives admit polynomial-time algorithms. In contrast to these special cases, the complexity of multiobjective hypergraph min-cut remains open even for $k=2$. Known techniques fail to extend due to structural differences between graphs and hypergraphs. For $k$-objective hypergraph min-cut when $k$ is a fixed constant, we design a randomized PTAS, and two different randomized quasi-polynomial time algorithms. As an application of our $2$-objective hypergraph min-cut results, we obtain a quasi-polynomial time approximation scheme (QPTAS) for hypergraph connectivity interdiction. AI tools were used to iterate and refine the algorithmic ideas underlying this work.

0.25

Geometric Optimization Parameterized by Piercing Complexity

cs.CG cs.DS ·2026-09-25 ·Aritra Banik, Rajiv Raman, Saurabh Ray
top venue similarity 0.59
Abstract · This is a corrected version of our ICALP 2026 paper. Unforunately, the conference version has an unfixable bug rendering the proofs incorrec…

Packing and covering problems for geometric regions have been studied under many notions of complexity, including VC-dimension, union complexity, shallow-cell complexity, and fatness. Although these restrictions often yield constant-factor approximation algorithms, they do not by themselves generally lead to PTASs. A recurring feature of known hardness constructions is that one region may be \emph{pierced} by many others: a region $B$ pierces $A$ when $A\setminus B$ is disconnected. We study geometric instances through the \emph{piercing degree}. Since piercing is symmetric for Jordan regions, this is the maximum degree of the corresponding piercing graph. Our main result is that, for every fixed piercing degree, the standard local-search algorithms give PTASs for the unweighted \emph{Discrete Independent Set} and \emph{Set Cover} problems. The proof constructs a sublinear balanced separator for an appropriate locality graph and applies it adaptively throughout the recursive local-search analysis. This guarantee depends only on the piercing degree; in particular, it places no bound on the number of components created by an individual piercing pair. We also prove a polynomial shallow-trace bound depending only on the piercing degree. As consequences, for every fixed piercing degree, weighted Set Cover admits a deterministic $C_r$-approximation and weighted Discrete Independent Set admits a deterministic $O(r+1)$-approximation. These results extend the known guarantees for non-piercing families and apply, for example, to axis-parallel rectangles when every rectangle is pierced by only a bounded number of other rectangles.

0.70