CS Paper Radar

Algorithms for Robust Dedicated Actuator Placement

Qichao Wang, Daoyu Dong

eess.SY ·submitted 2026-11-11 09:00 UTC · v1

Abstract

We study dedicated actuators installed at distinct states of a structured linear system. Failures remove actuators but preserve states and state arcs. For unit costs and one failure, an exact source-quota relaxation followed by maximum matching in a \emph{common-repair graph} yields a $3/2$-approximation on arbitrary directed state graphs using $O(n^3)$ elementary graph operations. The analysis combines fundamental cocircuit unions with the Tutte--Berge formula. For multiple failures, we give an exact algorithm fixed-parameter tractable in the maximum-matching deficiency and failure budget, independently of the number of source strongly connected components. The underlying result solves resilient matroid spanning with an arbitrary number of disjoint unit-cost quota constraints. We also establish an exact weighted spanning algorithm for safe and vulnerable elements in the independence-oracle model, with an application to strongly connected state graphs.

Comment
13 pages, 1 figure. Source code and verification scripts available on GitHub

Closest papers

Nearest neighbours by meaning across the whole index.

When Elements Fail: Weighted Fault-Tolerant Matroid Bases

cs.DS cs.DM ·2026-11-12 ·Madhumita Kundu, Soumi Nandi, Saket Saurabh
similarity 0.67
Abstract

Given a rank-\(r\) matroid on \(n\) elements with nonnegative costs and a partition into safe and vulnerable elements, we seek a minimum-cost set that spans after every deletion of at most \(k\) selected vulnerable elements. We resolve several open questions posed by Bentert, Fomin, Golovach, and Morelle (ESA 2025) concerning weighted costs, nonuniform failures, and explicitly specified failure scenarios. To this end, we develop two compression methods. For matroids given by an independence oracle, weighted flat-avoidance representatives yield a bounded subset of the ground set containing an optimal solution and a \(2^{\mathcal{O}((r+k)^4)}n^{\mathcal{O}(1)}\)-time algorithm. This establishes fixed-parameter tractability for weighted costs and nonuniform failures simultaneously. For explicitly represented linear matroids, polynomial certificates allow us to compress families of partial solutions while preserving successful completions under all allowed failures. This yields a deterministic algorithm using \(2^{\mathcal{O}(kr(r+k)\log(r+1))}n^{\mathcal{O}(1)}\) field operations over arbitrary fields. Over fixed finite fields, a simpler reduction uses parallel classes. For explicitly listed failure scenarios, we obtain fixed-parameter algorithms parameterized by rank and the number of scenarios. In contrast, the size-budget decision version is W[1]-hard parameterized by rank and maximum scenario size, even on uniform matroids with two-element scenarios. \keywords{Matroids \and Fault tolerance \and Fixed-parameter algorithms \and Representative families}

0.20

Sensitivity Oracles for Matroid Packing, Matroid Covering, and Matching Problems with Applications

cs.DS ·2026-09-01 ·Keerti Choudhary, Amit Kumar, Lakshay Saggi
theory similarity 0.59
Abstract · 65 pages, 3 figures

Sensitivity oracles preprocess a graph so that queries can be answered after any $f$ edge insertions and deletions, without recomputing from scratch. For structural optimization problems the known landscape is limited: for flows and cuts, all known compact oracles handle only $f\le2$ failures; existing oracles for $s$- and global min-cut apply only to undirected graphs; and for matchings, arborescence and spanning-tree packings, and arboricity, no efficient oracle is known for $f>1$. We present a unified algebraic framework based on sensitivity oracles for matroid packing, covering, and parity of sparse linear matroids, yielding the first oracles supporting an arbitrary number $f$ of updates across all of these problems (all constructions randomized Monte-Carlo). Concretely, we obtain efficient oracles for exact $(s,t)$-max-flow/min-cut, resolving an open problem of Baswana, Bhanja, and Pandey (ICALP'22) with near-optimal space; for all-pairs $k$-bounded flow, generalizing the near-optimal reachability oracle of Brand and Saranurak (FOCS'19, the case $k=1$); the first oracles for any $f$ for directed $s$- and global min-cut; oracles for $k$-disjoint arborescences, $k$-disjoint spanning trees, colorful spanning trees, and arboricity; and oracles for the existence of an $α$-factor, with perfect matching as the case $α=1$. We further introduce the \emph{subset sensitivity model}, in which updates are confined to a susceptible edge set of size $σ$ fixed during preprocessing. Here we decouple updates from the matroid representation and eliminate the dependence on $k$ and the matroid density altogether: all of the above are supported with $\widetilde O(f^ω)$ query time and $O(fσ^2)$ space. We also prove a matching $Ω(\min\{σ^2,n^2\})$-bit lower bound when $f\ge2$, establishing optimality.

0.27

Destroying Rigidity in the Plane

cs.DM ·2026-10-28 ·Yu Cong, Chao Xu, Yajie Zhao
theory similarity 0.58
Abstract

Rigidity and global rigidity are fundamental graph properties in discrete geometry, with applications to structural engineering and network localization. In two dimensions, both admit combinatorial characterizations in terms of the rigidity matroid and graph connectivity. We study the computational complexity of finding minimum-cost sets of edges or vertices whose deletion destroys either property in a finite simple graph. With unit costs, we give deterministic polynomial-time algorithms for edge deletion destroying global rigidity and vertex deletion destroying either property. We prove that edge deletion destroying rigidity is NP-hard and that, with positive integer costs, all four problems are NP-hard. These results resolve, in dimension two, the open questions on recognizing robustness under edge and vertex deletions posed by Jordán and Whiteley (2017), as well as the minimum edge-deletion problem for rigidity recorded in EGRES Open.

0.42

Safe Hypergraph Contraction via Capacity-Aware Repair Certificates

cs.DS ·2026-10-01 ·Yu Deng, Xinyi Yang, Keren Zhu
theory similarity 0.57
Abstract

Multilevel partitioners shrink circuit hypergraphs through vertex contractions, yet a contraction that satisfies block capacity can still eliminate every optimal balanced bipartition. We develop certified safe coarsening (CSC) to identify contractions that preserve an optimum without computing that optimum. CSC certifies a repair for any feasible partition that splits a candidate group: the repair must respect the fixed block capacities and must not increase the cut-net objective. Its bounds exclude hyperedges that capacity constraints force to be cut. A pair certificate checks individual merges, while a directed minimum-cut test certifies groups whose savings emerge only when vertices move together. We prove that certified disjoint batches and successive rounds with recertification retain at least one globally optimal feasible partition for hypergraphs with positive integer vertex and net weights. Experiments on exactly solvable instances confirm optimum preservation for every tested configuration; integration with KaHyPar lowers the sum of per-instance best cuts on circuit benchmarks, with additional runtime.

0.35

Controlled Islanding and Reconnection with Stability Guarantees via Submodular Optimization

eess.SY ·2026-09-11 ·Shiyu Cheng, Andrew Clark
benchmark similarity 0.56
Abstract

In large-scale networked dynamical systems, local faults or disturbances may propagate through the interconnections and compromise the stability of the entire network. Partitioning the network into disjoint subsystems, or islands, limits this propagation by isolating unstable portions of the network from those that remain stable. This paper studies a two-stage controlled islanding and reconnection problem. In the first stage, the network is partitioned into stable and unstable islands. In the second stage, selected stable islands are reconnected to recover connectivity lost during islanding while satisfying stability requirements. We derive Lyapunov-based sufficient conditions for both stages. To address the coupling between the islanding and reconnection decisions, we construct an augmented graph on which the bases of a graphic matroid induce exactly the admissible islanding and reconnection pairs. We further show that the resulting optimization problem admits an equivalent nonincreasing supermodular formulation. Based on this structure, we develop a local-search algorithm with counterexample refinement and establish a performance guarantee for its inner loop with fixed sample sets. Numerical studies on linear networked systems illustrate the proposed procedure, examine its sensitivity to fault locations, and compare the proposed method with a mixed-integer linear programming benchmark in terms of solution quality and computational performance.

0.24

Matroid Connectedness and Component Decomposition: Breaking the Quadratic Barrier

cs.DM ·2026-11-17 ·Manuel Aprile, Roberto Ronco
theory similarity 0.56
Abstract

Deciding whether a matroid is connected and computing its connected components are two fundamental algorithmic problems in matroid theory. Since the 1970s, the best known algorithms for both problems have used $O(n^2)$ independence queries on an $n$-element ground set. Our main contribution is to break this quadratic barrier: we give a deterministic algorithm that computes all connected components of a matroid on $n$ elements with $O(n \log{n})$ independence queries. Our algorithm for component decomposition combines fundamental basis exchanges with a disjoint-set union data structure, avoiding the explicit construction of the fundamental graph. Moreover, we show that our algorithm is asymptotically optimal by giving a lower bound based on a simple information-theoretic argument: any (deterministic or bounded-error randomized) algorithm to compute connected components needs $Ω(n \log{n})$ independence queries. Then, we turn to the query complexity of deciding whether a matroid is connected. For this problem, we present an algorithm that uses $O(nh)$ independence queries, where $h \ge 1$ bounds the size of any chain of nonempty proper cyclic flats. The algorithm achieves asymptotically optimal linear query complexity on elementary split matroids, that include all paving matroids, and on arbitrary direct sums of uniform matroids.

0.15

Capacity-Aware Redistribution Control for Mitigation of Cascading Failures in Networks

eess.SY math.OC ·2026-11-18 ·Ujjwal Pratap, Christian A. Hans
similarity 0.56
Abstract

This paper studies the control of irreversible cascading failures in networks with finite node capacities. Each node carries a nonnegative divisible quantity, referred to as load, and fails irreversibly when its load exceeds its capacity. The network dynamics are represented by topology-dependent row-stochastic matrices. When nodes fail, these matrices must be updated. However, directly deleting rows and columns corresponding to failed nodes can reduce the total load in the network. We therefore introduce a topology update that preserves unit row sums and quantifies any unserved load explicitly. We derive the resulting load-balance relation and a necessary and sufficient condition for lossless redistribution after simultaneous failures. Based on these results, we formulate a two-stage optimization problem: the first stage minimizes unserved load, and the second stage minimizes the highest capacity utilization among the surviving nodes. Simulations on grid and Barabasi-Albert networks show that, unlike the standard equal and residual-capacity redistribution approaches, the proposed method prevents secondary failures in all tested cases, with a tradeoff against served load on scale-free networks.

0.32

Simplified and Faster Algorithms for the Directed Single/Dual-Failure Replacement Paths via Modulo-Layer Hitting Sets

cs.DS ·2026-10-17 ·Kaito Harada, Tatsuya Terao
similarity 0.56
Abstract · 25 pages

We study the replacement paths problem in unweighted directed graphs with $n$ vertices and $m$ edges under one or two edge failures. We give simpler and faster algorithms for both settings. Both algorithms are based on a new technique, which we call \emph{modulo-layer hitting sets}. For the single-failure setting, we obtain a simple deterministic combinatorial algorithm running in $O(m\sqrt{n})$ time, which is nearly optimal under the combinatorial Boolean Matrix Multiplication (BMM) conjecture. In addition to removing the logarithmic overhead of the deterministic $\tilde{O}(m\sqrt{n})$-time algorithm of Alon, Chechik, and Cohen~[ICALP'19], our algorithm admits a much simpler implementation and analysis. For the dual-failure setting, we obtain a randomized combinatorial algorithm running in $\tilde{O}(n^{3-1/4})$ time. This improves upon the previous $\tilde{O}(n^{3-1/18})$-time combinatorial algorithm of Chechik and Zhang~[ICALP'24].

0.14