CS Paper Radar

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

Quanlong Niu, Riheng Jia

cs.DM ·submitted 2026-10-09 06:51 UTC · v1
theory

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.

Closest papers

Nearest neighbours by meaning across the whole index.

The Strong Total Cover Problem

cs.DM cs.CCmath.CO ·2026-10-16 ·Manuel Aprile, Luca Ferrarini
similarity 0.68
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

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.65
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

Structural Complexity of Matching-Match: Dense and Sparse Graphs

cs.DS ·2026-09-22 ·Ilie Dumitru, Adrian Miclăuş, Alexandru Popa
theory similarity 0.65
Abstract

The Matching-Match puzzle asks whether the vertices of a fixed graph can be colored so that the multiset of color pairs induced by its edges is exactly a prescribed multiset. We study how the complexity of this realization problem depends on the host graph. On the dense side, we give a polynomial-time algorithm for complete $k$-partite graphs for every fixed number $k$ of parts, with arbitrary precoloring and an arbitrary number of colors. We prove a sharp complement-degree threshold: the problem is polynomial-time solvable when $Δ(\overline G)\le1$, but NP-complete on completely uncolored graphs already when $Δ(\overline G)=2$. This yields a dichotomy for uniform complete multipartite graphs, and connected diameter two already suffices for NP-completeness. We also prove W[1]-hardness on cographs parameterized by the number of colors. On the sparse side, completely uncolored paths and cycles admit a linear-time characterization by Euler trails and circuits, while counting feasible colorings is $\#P$-complete on both classes. Counting is nevertheless polynomial-time solvable on stars and complete graphs, even with arbitrary precoloring. A decomposition-transfer theorem yields NP-completeness already at tree-depth two. A separate path-decomposition reduction gives a maximum-degree threshold between one and two for completely uncolored disconnected host graphs with unrestrictedly many colors. Components with at most two edges are tractable, while a disjoint union of $P_4$'s is NP-complete. Finally, precoloring restores tractability in several cases: star forests are polynomial when every center is precolored, and two broad precoloring regimes on length-two spiders are polynomial even when the number of colors is unbounded.

0.21

A simple algorithm for computing Hamilton paths on independent set polytopes

cs.DM math.CO ·2026-09-07 ·Jean Cardinal, Pia Herkenrath, Torsten Mütze, Francesco Verciani
similarity 0.65
Abstract

The independent set polytope, or stable set polytope, of a graph $G$ is the 0/1-polytope defined by the convex hull of the characteristic vectors of all independent sets of $G$. We present a simple algorithm for computing a Hamilton path on the independent set polytope of a given $n$-vertex graph $G$ with amortized delay $\mathcal{O}(n)$. The independent sets are listed such that two consecutive sets differ either in removing a vertex, or adding a vertex and removing its neighbors from the independent set, i.e., the symmetric difference between two consecutive independent sets induces a star in $G$. As applications of this result, we obtain an algorithm to compute a Hamilton path on the matching polytope of an $m$-edge graph $G$ with worst-case delay $\mathcal{O}(m)$, which lists all matchings of $G$ in such a way that the symmetric difference between two consecutive matchings is a path on at most three edges. Furthermore, we obtain an algorithm to compute a Hamilton path on the chain polytope and order polytope of an $n$-element poset $P$ with amortized delay $\mathcal{O}(n)$, which lists all antichains of $P$ or all ideals of $P$, respectively, by star exchanges. Our algorithms are derived from the generic framework proposed by Merino and Mütze (FOCS'23+SICOMP'24) for computing Hamilton paths on arbitrary 0/1-polytopes, which uses a linear optimization procedure as a black box. Our algorithms bypass solving the computationally intractable maximum weight independent set problem by a simple and purely combinatorial greedy rule.

0.25

On the Parameterized Complexity of Conflict-Free Edge Cut in Undirected Graphs

cs.DS cs.DM ·2026-10-05 ·Sourav Das, Ashwin Jacob, Arpit Kumar, Diptapriyo Majumdar
theory similarity 0.65
Abstract · 26 pages

In this paper, we study CONFLICT-FREE EDGE CUT (CF-CUT), which is a recently introduced conflict-free version of the MIN-CUT problem that asks to find the minimum number of edges to disconnect a connected graph. The CF-CUT takes as input a connected undirected graph G = (V, E), a conflict graph $\widehat{G}$ such that $E(G) = V(\widehat{G})$, and the objective is to decide whether there exists $F \subseteq E(G)$ such that $G - F$ is disconnected and $F$ is an independent set in $\widehat{G}$. Rauch et. al. [IPL-2025] proved that CF-CUT is NP-Complete and also provided some results on the parameterized complexity of CF-CUT. A related variant MIN CONFLICT-FREE EDGE CUT (MIN-CF-CUT) takes a connected graph $G$, a conflict graph $\widehat{G}$ such that $V(\widehat{G}) = E(G)$, and an integer $k$ as input and asks if there is a set $F$ of at most $k$ edges such that $G - F$ is disconnected and $F$ is an independent set in $\widehat{G}$. In this paper, we extend the work of Rauch et al. [IPL-2025] and provide a systematic study on the CF-CUT and MIN-CF-CUT from the perspective of parameterized complexity and polynomial kernelization. We prove that CF-CUT is NP-hard when the dissociation number of the input graph is at most two. We also complement it by proving that CF-CUT is poly-time solvable when the dissociation number of an input graph is at most one. Additionally, for MIN-CF-CUT, we consider both solution size and various structural parameters of the input graph as parameters, and provide fixed-parameter tractability and W[1]-hardness results when the conflict graph is restricted to various graph classes. We also prove that unless NP $\subseteq$ coNP/poly, MIN-CF-CUT admits no polynomial kernel when parameterized by the vertex cover number of the input graph; and also when parameterized by the sum of the solution size and the vertex integrity of the input graph.

0.24

Zero Forcing Sets in Temporal Graphs

cs.DM cs.CC ·2026-09-24 ·Julien Baste, Simon Dreyer, Clara Marcille, Mikaël Rabie, Ronan Toullec-Streicher
similarity 0.65
Abstract

The Zero Forcing (or corruption) of a graph is the problem of finding a minimum-size ``corrupting'' set. It corresponds to a subset of its vertices that can corrupt the whole graph by iterating the following rule: if a corrupted vertex has exactly one neighbor that is not yet corrupted, the neighbor gets corrupted. The iteration of this process comes from the fact that the corruption of a vertex might enable new corruptions (from itself or some of its neighbors). For this reason, one can consider a step of corruption, where all the possible instances of the corruption rule are applied at once. This paper investigates Zero Forcing on temporal graphs, where the topology of the graph evolves throughout the experiment. At each time step (or snapshot) of the graph, a step of corruption is resolved wherever possible. We study the problem of finding a minimum-size corrupting set such that the whole (temporal) graph is corrupted at the end of the experiment. We present a panorama of results, including NP-hardness in some not-so-restrictive scenarios, polynomial algorithms, and a solution to an open question when the whole graph must be corrupted in a single step.

0.30

Single-Exponential FPT Algorithms for Minimum Bisection and Matching Cut via a New Unbreakable Decomposition

cs.DS ·2026-11-04 ·Soh Kumabe
similarity 0.65
Abstract

Minimum Bisection asks whether the vertices of a graph can be partitioned into two parts whose sizes differ by at most one and with at most k edges between the two parts. Cygan, Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, and Saurabh (SICOMP 2019) gave the first fixed-parameter algorithm, which runs in O*(2^(O(k^3))) time, by introducing an unbreakable decomposition. Cygan, Komosa, Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Saurabh, and Wahlström (TALG 2021) strengthened the decomposition and improved the running time to O*(2^(O(k log k))). However, whether the running time could be improved to single-exponential remained open. In this paper, we give a deterministic O*(2^(O(k)))-time algorithm for Minimum Bisection. Our algorithm also counts all feasible bisections. To obtain an O*(2^(O(k)))-time algorithm, we introduce two new techniques. First, we give a new algorithm that computes a (2k,k)-edge-unbreakable decomposition with adhesion at most 2k in O*(2^(O(k))) time by relaxing the unbreakability and adhesion guarantees of the decomposition in (TALG 2021). Second, we improve the running time of the dynamic program over the decomposition from O*(2^(O(k log k))) to O*(2^(O(k))) using important cuts, inclusion-exclusion, and formal logarithms and exponentials. Together with color coding, the same techniques give a deterministic O*(2^(O(k)))-time algorithm for Matching Cut, which asks for a cut whose crossing edges form a matching. This improves the O*(2^(O(k log k)))-time algorithm of Aravind and Saxena (IWOCA 2021).

0.46

Improved Approximation and Hardness Results for the Monitoring Edge-Geodetic Set Problem

cs.DS ·2026-10-20 ·Davide Bilò, Giordano Colli, Stefano Leucci
theory similarity 0.64
Abstract · 18 pages, 4 figures

We study the \emph{Monitoring Edge-Geodetic Set} problem (MEG-Set), which asks for a minimum-cardinality set $M$ of vertices of an undirected graph $G$ of $n$ vertices such that every edge of $G$ belongs to all shortest paths between some pair of vertices in $M$. We present new approximation and hardness results for MEG-Set. On the positive side, we design a deterministic polynomial-time $O(n^{1/3}\log^{2/3}n)$-approximation algorithm, improving upon the previously best-known $O(\sqrt{n\log n})$ approximation ratio. On the negative side, for every constant $\varepsilon \in (0,1)$, we prove that the problem admits no polynomial-time $\big(2^{\log^{1-\varepsilon} n}\big)$-approximation algorithm, unless $\mathsf{NP}\subseteq \mathsf{DTIME}(n^{\operatorname{polylog} n})$. This substantially improves upon the previously known logarithmic inapproximability bound. We also prove that \megset is $\mathsf{NP}$-hard on planar $2$-degenerate graphs, whereas $\mathsf{NP}$-hardness was previously known for $1$-apex $2$-degenerate graphs. We conclude by observing a connection between monitoring edge-geodetic sets and subsetwise distance preservers, i.e., subgraphs that preserve distances between all pairs of vertices in $S\subseteq V(G)$. Specifically, we show that any upper bound on the size of the latter yields a lower bound on the size of the former.

0.23