cs.DS

arXiv:2503.22368v1 Announce Type: new Abstract: We present an exact algorithm for computing the connected Maximum Common Subgraph (MCS) across multiple graphs, where edges or vertices may additionally be labeled to account for possible atom types or bond types, a classical labeling used in molecular graphs. Our approach leverages modular product graphs and a modified Bron-Kerbosch algorithm to enumerate maximal cliques, ensuring all intermediate solutions are retained. A pruning heuristic efficiently reduces the modular product size, improving computational feasibility. Additionally, we introduce a graph ordering strategy based on graph-kernel similarity measures to optimize the search process. Our method is particularly relevant for bioinformatics and cheminformatics, where identifying conserved structural motifs in molecular graphs is crucial. Empirical results on molecular datasets demonstrate that our approach is exact, scalable and fast.

arXiv:2503.22669v1 Announce Type: new Abstract: A $(1+\varepsilon)$-stretch tree cover of an edge-weighted $n$-vertex graph $G$ is a collection of trees, where every pair of vertices has a $(1+\varepsilon)$-stretch path in one of the trees. The celebrated Dumbbell Theorem by Arya et. al. [STOC'95] states that any set of $n$ points in $d$-dimensional Euclidean space admits a $(1+\varepsilon)$-stretch tree cover with a constant number of trees, where the constant depends on $\varepsilon$ and the dimension $d$. This result was generalized for arbitrary doubling metrics by Bartal et. al. [ICALP'19]. While the total number of edges in the tree covers of Arya et. al. and Bartal et. al. is $O(n)$, all known tree cover constructions incur a total lightness of $\Omega(\log n)$; whether one can get a tree cover of constant lightness has remained a longstanding open question, even for 2-dimensional point sets. In this work we resolve this fundamental question in the affirmative, as a direct corollary of a new construction of $(1+\varepsilon)$-stretch spanning tree cover for doubling graphs; in a spanning tree cover, every tree may only use edges of the input graph rather than the corresponding metric. To the best of our knowledge, this is the first constant-stretch spanning tree cover construction (let alone for $(1+\varepsilon)$-stretch) with a constant number of trees, for any nontrivial family of graphs. Concrete applications of our spanning tree cover include a $(1+\varepsilon)$-stretch light tree cover, a compact $(1+\varepsilon)$-stretch routing scheme in the labeled model, and a $(1+\varepsilon)$-stretch path-reporting distance oracle, for doubling graphs. [...]

arXiv:2408.07019v2 Announce Type: replace Abstract: The 2-Edge-Connected Spanning Subgraph problem (2ECSS) is among the most basic survivable network design problems: given an undirected and unweighted graph, the task is to find a spanning subgraph with the minimum number of edges that is 2-edge-connected (i.e., it remains connected after the removal of any single edge). 2ECSS is an NP-hard problem that has been extensively studied in the context of approximation algorithms. The best known approximation ratio for 2ECSS prior to this work was $1.3+\varepsilon$, for any constant $\varepsilon>0$ [Garg, Grandoni, Jabal-Ameli'23; Kobayashi, Noguchi'23]. In this paper, we present a 5/4-approximation algorithm. Our algorithm is also faster for small values of $\varepsilon$: its running time is $n^{O(1)}$ instead of $n^{O(1/\varepsilon)}$.

arXiv:2503.22521v1 Announce Type: new Abstract: The Freeze Tag Problem consists in waking up a swarm of robots starting with one initially awake robot. Whereas there is a wide literature of the centralized setting, where the location of the robots is known in advance, we focus in the distributed version where the location of the robots $\P$ are unknown, and where awake robots only detect other robots up to distance~$1$. Assuming that moving at distance $\delta$ takes a time $\delta$, we show that waking up of the whole swarm takes $O(\rho+\ell^2\log( \rho/\ell))$, where $\rho$ stands for the largest distance from the initial robot to any point of $\P$, and the $\ell$ is the connectivity threshold of $\P$. Moreover, the result is complemented by a matching lower bound in both parameters $\rho$ and $\ell$. We also provide other distributed algorithms, complemented with lower bounds, whenever each robot has a bounded amount of energy.

arXiv:2403.05943v2 Announce Type: replace Abstract: The classic theorem of Gallai and Milgram (1960) asserts that for every graph G, the vertex set of G can be partitioned into at most \alpha(G) vertex-disjoint paths, where \alpha(G) is the maximum size of an independent set in G. The proof of Gallai--Milgram's theorem is constructive and yields a polynomial-time algorithm that computes a covering of G by at most \alpha(G) vertex-disjoint paths. We prove the following algorithmic extension of Gallai--Milgram's theorem for undirected graphs: determining whether an undirected graph can be covered by fewer than \alpha(G) - k vertex-disjoint paths is fixed-parameter tractable (FPT) when parameterized by k. More precisely, we provide an algorithm that, for an n-vertex graph G and an integer parameter k \ge 1, runs in time 2^{k^{O(k^4)}} \cdot n^{O(1)}, and outputs a path cover P of G. Furthermore, it: - either correctly reports that P is a minimum-size path cover, - or outputs, together with P, an independent set of size |P| + k certifying that P contains at most \alpha(G) - k paths. A key subroutine in our algorithm is an FPT algorithm, parameterized by \alpha(G), for deciding whether G contains a Hamiltonian path. This result is of independent interest -- prior to our work, no polynomial-time algorithm for deciding Hamiltonicity was known even for graphs with independence number at most 3. Moreover, the techniques we develop apply to a wide array of problems in undirected graphs, including Hamiltonian Cycle, Path Cover, Largest Linkage, and Topological Minor Containment. We show that all these problems are FPT when parameterized by the independence number of the graph. Notably, the independence number parameterization, which describes graph's density, departs from the typical flow of research in parameterized complexity, which focuses on parameters describing graph's sparsity, like treewidth or vertex cover.

arXiv:2503.22613v1 Announce Type: new Abstract: A classical algorithm by Bellman and Ford from the 1950's computes shortest paths in weighted graphs on $n$ vertices and $m$ edges with possibly negative weights in $O(mn)$ time. Indeed, this algorithm is taught regularly in undergraduate Algorithms courses. In 2023, after nearly 70 years, Fineman \cite{fineman2024single} developed an $\tilde{O}(m n^{8/9})$ expected time algorithm for this problem. Huang, Jin and Quanrud improved on Fineman's startling breakthrough by providing an $\tilde{O}(m n^{4/5} )$ time algorithm. This paper builds on ideas from those results to produce an $\tilde{O}(m\sqrt{n})$ expected time algorithm. The simple observation that distances can be updated with respect to the reduced costs for a price function in linear time is key to the improvement. This almost immediately improves the previous work. To produce the final bound, this paper provides recursive versions of Fineman's structures.

arXiv:2503.01005v2 Announce Type: replace-cross Abstract: Let $X$ be a $d$-partite $d$-dimensional simplicial complex with parts $T_1,\dots,T_d$ and let $\mu$ be a distribution on the facets of $X$. Informally, we say $(X,\mu)$ is a path complex if for any $i<j<k$ and $F \in T_i,G \in T_j, K\in T_k$, we have $\mathbb{P}_\mu[F,K | G]=\mathbb{P}_\mu[F|G]\cdot\mathbb{P}_\mu[K|G].$ We develop a new machinery with $\mathcal{C}$-Lorentzian polynomials to show that if all links of $X$ of co-dimension 2 have spectral expansion at most $1/2$, then $X$ is a $1/2$-local spectral expander. We then prove that one can derive fast-mixing results and log-concavity statements for top-link spectral expanders. We use our machinery to prove fast mixing results for sampling maximal flags of flats of distributive lattices (a.k.a. linear extensions of posets) subject to external fields, and to sample maximal flags of flats of "typical" modular lattices. We also use it to re-prove the Heron-Rota-Welsh conjecture and to prove a conjecture of Chan and Pak which gives a generalization of Stanley's log-concavity theorem. Lastly, we use it to prove near optimal trickle-down theorems for "sparse complexes" such as constructions by Lubotzky-Samuels-Vishne, Kaufman-Oppenheim, and O'Donnell-Pratt.

arXiv:2408.14617v2 Announce Type: replace Abstract: In their pioneering work, Chan, Har-Peled, and Jones (SICOMP 2020) introduced locality-sensitive ordering (LSO), and constructed an LSO with a constant number of orderings for point sets in the $d$-dimensional Euclidean space. Furthermore, their LSO could be made dynamic effortlessly under point insertions and deletions, taking $O(\log{n})$ time per update by exploiting Euclidean geometry. Their LSO provides a powerful primitive to solve a host of geometric problems in both dynamic and static settings. Filtser and Le (STOC 2022) constructed the first LSO with a constant number of orderings in the more general setting of doubling metrics. However, their algorithm is inherently static since it relies on several sophisticated constructions in intermediate steps, none of which is known to have a dynamic version. Making their LSO dynamic would recover the full generality of LSO and provide a general tool to dynamize a vast number of static constructions in doubling metrics. In this work, we give a dynamic algorithm that has $O(\log{n})$ time per update to construct an LSO in doubling metrics under point insertions and deletions. We introduce a toolkit of several new data structures: a pairwise tree cover, a net tree cover, and a leaf tracker. A key technical is stabilizing the dynamic net tree of Cole and Gottlieb (STOC 2006), a central dynamic data structure in doubling metrics. Specifically, we show that every update to the dynamic net tree can be decomposed into a few simple updates to trees in the net tree cover. As stability is the key to any dynamic algorithm, our technique could be useful for other problems in doubling metrics. We obtain several algorithmic applications from our dynamic LSO. The most notably is the first dynamic algorithm for maintaining an $k$-fault tolerant spanner in doubling metrics with optimal sparsity in optimal $O(\log{n})$ time per update.

arXiv:2503.05934v2 Announce Type: replace Abstract: Recent work by Google DeepMind introduced assembly-optimized sorting networks that achieve faster performance for small fixed-size arrays (3-8). In this research, we investigate the integration of these networks as base cases in classical divide-and-conquer sorting algorithms, specifically Merge Sort and Quick Sort, to leverage these efficient sorting networks for small subarrays generated during the recursive process. We conducted benchmarks with 11 different optimization configurations and compared them to classical Merge Sort and Quick Sort. We tested the configurations with random, sorted and nearly sorted arrays. Our optimized Merge Sort, using a configuration of three sorting networks (sizes 6, 7, and 8), achieves at least 1.5x speedup for random and nearly sorted arrays, and at least 2x speedup for sorted arrays, in comparison to classical Merge Sort. This optimized Merge Sort surpasses both classical Quick Sort and similarly optimized Quick Sort variants when sorting random arrays of size 10,000 and larger. When comparing our optimized Quick Sort to classical Quick Sort, we observe a 1.5x speedup using the 3-to-5 configuration on sorted arrays of size 10,000. The 6-to-8 configuration maintains a consistent 1.5x improvement across sorted arrays from 25,000 to 1 million elements. Our findings demonstrate the potential of integrating AI-optimized sorting networks to enhance the performance of classical sorting algorithms.

arXiv:2503.10161v1 Announce Type: new Abstract: A minimal perfect hash function (MPHF) maps a set of n keys to unique positions {1, ..., n}. Representing an MPHF requires at least 1.44 bits per key. ShockHash is a technique to construct an MPHF and requires just slightly more space. It gives each key two pseudo random candidate positions. If each key can be mapped to one of its two candidate positions such that there is exactly one key mapped to each position, then an MPHF is found. If not, ShockHash repeats the process with a new set of random candidate positions. ShockHash has to store how many repetitions were required and for each key to which of the two candidate positions it is mapped. However, when a given set of candidate positions can be used as MPHF then there is not only one but multiple ways of mapping the keys to one of their candidate positions such that the mapping results in an MPHF. This redundancy makes up for the majority of the remaining space overhead in ShockHash. In this paper, we present MorphisHash which is a technique that almost completely eliminates this redundancy. Our theoretical result is that MorphisHash saves {\Theta}(ln(n)) bits compared to ShockHash. This corresponds to a factor of 20 less space overhead in practice. The technique to accomplish this might be of a more general interest to compress data structures.

arXiv:2408.07831v2 Announce Type: replace Abstract: We introduce and study spatiotemporal online allocation with deadline constraints ($\mathsf{SOAD}$), a new online problem motivated by emerging challenges in sustainability and energy. In $\mathsf{SOAD}$, an online player completes a workload by allocating and scheduling it on the points of a metric space $(X, d)$ while subject to a deadline $T$. At each time step, a service cost function is revealed that represents the cost of servicing the workload at each point, and the player must irrevocably decide the current allocation of work to points. Whenever the player moves this allocation, they incur a movement cost defined by the distance metric $d(\cdot, \ \cdot)$ that captures, e.g., an overhead cost. $\mathsf{SOAD}$ formalizes the open problem of combining general metrics and deadline constraints in the online algorithms literature, unifying problems such as metrical task systems and online search. We propose a competitive algorithm for $\mathsf{SOAD}$ along with a matching lower bound establishing its optimality. Our main algorithm, \textsc{ST-CLIP}, is a learning-augmented algorithm that takes advantage of predictions (e.g., forecasts of relevant costs) and achieves an optimal consistency-robustness trade-off. We evaluate our proposed algorithms in a simulated case study of carbon-aware spatiotemporal workload management, an application in sustainable computing that schedules a delay-tolerant batch compute job on a distributed network of data centers. In these experiments, we show that \textsc{ST-CLIP} substantially improves on heuristic baseline methods.

arXiv:2301.13735v2 Announce Type: replace Abstract: A class of graphs $\mathscr{C}$ is monadically stable if for any unary expansion $\widehat{\mathscr{C}}$ of $\mathscr{C}$, one cannot interpret, in first-order logic, arbitrarily long linear orders in graphs from $\widehat{\mathscr{C}}$. It is known that nowhere dense graph classes are monadically stable; these encompass most of the studied concepts of sparsity in graphs, including graph classes that exclude a fixed topological minor. On the other hand, monadic stability is a property expressed in purely model-theoretic terms and hence it is also suited for capturing structure in dense graphs. For several years, it has been suspected that one can create a structure theory for monadically stable graph classes that mirrors the theory of nowhere dense graph classes in the dense setting. In this work we provide a step in this direction by giving a characterization of monadic stability through the Flipper game: a game on a graph played by Flipper, who in each round can complement the edge relation between any pair of vertex subsets, and Connector, who in each round localizes the game to a ball of bounded radius. This is an analog of the Splitter game, which characterizes nowhere dense classes of graphs (Grohe, Kreutzer, and Siebertz, J.ACM'17). We give two different proofs of our main result. The first proof uses tools from model theory, and it exposes an additional property of monadically stable graph classes that is close in spirit to definability of types. Also, as a byproduct, we give an alternative proof of the recent result of Braunfeld and Laskowski (arXiv 2209.05120) that monadic stability for graph classes coincides with existential monadic stability. The second proof relies on the recently introduced notion of flip-wideness (Dreier, M\"ahlmann, Siebertz, and Toru\'nczyk, ICALP 2023) and provides an efficient algorithm to compute Flipper's moves in a winning strategy.

arXiv:2410.07388v2 Announce Type: replace Abstract: The Densest $k$-Subgraph (D$k$S) problem aims to find a subgraph comprising $k$ vertices with the maximum number of edges between them. A continuous reformulation of the binary quadratic D$k$S problem is considered, which incorporates a diagonal loading term. It is shown that this non-convex, continuous relaxation is tight for a range of diagonal loading parameters, and the impact of the diagonal loading parameter on the optimization landscape is studied. On the algorithmic side, two projection-free algorithms are proposed to tackle the relaxed problem, based on Frank-Wolfe and explicit constraint parametrization, respectively. Experiments suggest that both algorithms have merits relative to the state-of-art, while the Frank-Wolfe-based algorithm stands out in terms of subgraph density, computational complexity, and ability to scale up to very large datasets.

arXiv:2503.10541v1 Announce Type: new Abstract: In a digraph $D$, an arc $e=(x,y) $ in $D$ is considered transitive if there is a path from $x$ to $y$ in $D- e$. A digraph is transitive-free if it does not contain any transitive arc. In the Transitive-free Vertex Deletion (TVD) problem, the goal is to find at most $k$ vertices $S$ such that $D-S$ has no transitive arcs. In our work, we study a more general version of the TVD problem, denoted by $\ell$-Relaxed Transitive-free Vertex Deletion ($\ell$-RTVD), where we look for at most $k$ vertices $S$ such that $D-S$ has no more than $\ell$ transitive arcs. We explore $\ell$-RTVD on various well-known graph classes of digraphs such as directed acyclic graphs (DAGs), planar DAGs, $\alpha$-bounded digraphs, tournaments, and their multiple generalizations such as in-tournaments, out-tournaments, local tournaments, acyclic local tournaments, and obtain the following results. Although the problem admits polynomial-time algorithms in tournaments, $\alpha$-bounded digraphs, and acyclic local tournaments for fixed values of $\ell$, it remains NP-hard even in planar DAGs with maximum degree 6. In the parameterized realm, for $\ell$-RTVD on in-tournaments and out-tournaments, we obtain polynomial kernels parameterized by $k+\ell$ for bounded independence number. But the problem remains fixed-parameter intractable on DAGs when parameterized by $k$.

arXiv:2503.09802v1 Announce Type: new Abstract: We study the task of list-decodable linear regression using batches. A batch is called clean if it consists of i.i.d. samples from an unknown linear regression distribution. For a parameter $\alpha \in (0, 1/2)$, an unknown $\alpha$-fraction of the batches are clean and no assumptions are made on the remaining ones. The goal is to output a small list of vectors at least one of which is close to the true regressor vector in $\ell_2$-norm. [DJKS23] gave an efficient algorithm, under natural distributional assumptions, with the following guarantee. Assuming that the batch size $n$ satisfies $n \geq \tilde{\Omega}(\alpha^{-1})$ and the number of batches is $m = \mathrm{poly}(d, n, 1/\alpha)$, their algorithm runs in polynomial time and outputs a list of $O(1/\alpha^2)$ vectors at least one of which is $\tilde{O}(\alpha^{-1/2}/\sqrt{n})$ close to the target regressor. Here we design a new polynomial time algorithm with significantly stronger guarantees under the assumption that the low-degree moments of the covariates distribution are Sum-of-Squares (SoS) certifiably bounded. Specifically, for any constant $\delta>0$, as long as the batch size is $n \geq \Omega_{\delta}(\alpha^{-\delta})$ and the degree-$\Theta(1/\delta)$ moments of the covariates are SoS certifiably bounded, our algorithm uses $m = \mathrm{poly}((dn)^{1/\delta}, 1/\alpha)$ batches, runs in polynomial-time, and outputs an $O(1/\alpha)$-sized list of vectors one of which is $O(\alpha^{-\delta/2}/\sqrt{n})$ close to the target. That is, our algorithm achieves substantially smaller minimum batch size and final error, while achieving the optimal list size. Our approach uses higher-order moment information by carefully combining the SoS paradigm interleaved with an iterative method and a novel list pruning procedure. In the process, we give an SoS proof of the Marcinkiewicz-Zygmund inequality that may be of broader applicability.

arXiv:2503.09908v1 Announce Type: new Abstract: We present a work optimal algorithm for parallel fully batch-dynamic maximal matching against an oblivious adversary. In particular it processes batches of updates (either insertions or deletions of edges) in constant expected amortized work per edge update, and in $O(\log^3 m)$ depth per batch whp, where $m$ is the maximum number of edges in the graph over time. This greatly improves on the recent result by Ghaffari and Trygub (2024) that requires $O(\log^9 m)$ amortized work per update and $O(\log^4 m )$ depth per batch, both whp. The algorithm can also be used for hyperedge maximal matching. For hypergraphs with rank $r$ (maximum cardinality of any edge) the algorithm supports batches of insertions and deletions with $O(r^3)$ expected amortized work per edge update, and $O(\log^3 m)$ depth per batch whp. This is a factor of $O(r)$ work off of the best sequential algorithm, Assadi and Solomon (2021), which uses $O(r^2)$ work per update. Ghaffari and Trygub's parallel batch-dynamic algorithm on hypergraphs requires $O(r^8 \log^9 m)$ amortized work per edge update whp. We leverage ideas from the prior algorithms but introduce substantial new ideas. Furthermore, our algorithm is relatively simple, perhaps even simpler than the sequential hyperedge algorithm. We also present the first work-efficient algorithm for maximal matching on hypergraphs. For a hypergraph with total cardinality $m'$ (i.e., sum over the cardinality of each edge), the algorithm runs in $O(m')$ work in expectation and $O(\log^2 m)$ depth whp. The algorithm also has some properties that allow us to use it as a subroutine in the dynamic algorithm to select random edges in the graph to add to the matching.

arXiv:2503.09762v1 Announce Type: new Abstract: We study a centralized discrete-time dynamic two-way matching model with finitely many agent types. Agents arrive stochastically over time and join their type-dedicated queues waiting to be matched. We focus on state-independent greedy policies that achieve constant regret at all times by making matching decisions based solely on agent availability across types, rather than requiring complete queue-length information. Such policies are particularly appealing for life-saving applications such as kidney exchange, as they require less information and provide more transparency compared to state-dependent policies. First, for acyclic matching networks, we analyze a deterministic priority policy proposed by Kerimov et al. [2023] that follows a static priority order over matches. We derive the first explicit regret bound in terms of the general position gap (GPG) parameter $\epsilon$, which measures the distance of the fluid relaxation from degeneracy. Second, for general two-way matching networks, we design a randomized state-independent greedy policy that achieves constant regret with optimal scaling $O(\epsilon^{-1})$, matching the existing lower bound established by Kerimov et al. [2024].

arXiv:2503.10416v1 Announce Type: new Abstract: Runtime repeated recursion unfolding was recently introduced as a just-in-time program transformation strategy that can achieve super-linear speedup. So far, the method was restricted to single linear direct recursive rules in the programming language Constraint Handling Rules (CHR). In this companion paper, we generalize the technique to multiple recursion and to multiple recursive rules and provide an implementation of the generalized method in the logic programming language Prolog. The basic idea of the approach is as follows: When a recursive call is encountered at runtime, the recursive rule is unfolded with itself and this process is repeated with each resulting unfolded rule as long as it is applicable to the current call. In this way, more and more recursive steps are combined into one recursive step. Then an interpreter applies these rules to the call starting from the most unfolded rule. For recursions which have sufficiently simplifyable unfoldings, a super-linear can be achieved, i.e. the time complexity is reduced. We implement an unfolder, a generalized meta-interpreter and a novel round-robin rule processor for our generalization of runtime repeated recursion unfolding with just ten clauses in Prolog. We illustrate the feasibility of our technique with worst-case time complexity estimates and benchmarks for some basic classical algorithms that achieve a super-linear speedup.

arXiv:2503.09810v1 Announce Type: new Abstract: Counting small subgraphs, referred to as motifs, in large graphs is a fundamental task in graph analysis, extensively studied across various contexts and computational models. In the sublinear-time regime, the relaxed problem of approximate counting has been explored within two prominent query frameworks: the standard model, which permits degree, neighbor, and pair queries, and the strictly more powerful augmented model, which additionally allows for uniform edge sampling. Currently, in the standard model, (optimal) results have been established only for approximately counting edges, stars, and cliques, all of which have a radius of one. This contrasts sharply with the state of affairs in the augmented model, where algorithmic results (some of which are optimal) are known for any input motif, leading to a disparity which we term the ``scope gap" between the two models. In this work, we make significant progress in bridging this gap. Our approach draws inspiration from recent advancements in the augmented model and utilizes a framework centered on counting by uniform sampling, thus allowing us to establish new results in the standard model and simplify on previous results. In particular, our first, and main, contribution is a new algorithm in the standard model for approximately counting any Hamiltonian motif in sublinear time. Our second contribution is a variant of our algorithm that enables nearly uniform sampling of these motifs, a capability previously limited in the standard model to edges and cliques. Our third contribution is to introduce even simpler algorithms for stars and cliques by exploiting their radius-one property. As a result, we simplify all previously known algorithms in the standard model for stars (Gonen, Ron, Shavitt (SODA 2010)), triangles (Eden, Levi, Ron Seshadhri (FOCS 2015)) and cliques (Eden, Ron, Seshadri (STOC 2018)).

arXiv:2503.10447v1 Announce Type: new Abstract: In the Feedback Arc Set in Tournaments (Subset-FAST) problem, we are given a tournament $D$ and a positive integer $k$, and the objective is to determine whether there exists an arc set $S \subseteq A(D)$ of size at most $k$ whose removal makes the graph acyclic. This problem is well-known to be equivalent to a natural tournament ranking problem, whose task is to rank players in a tournament such that the number of pairs in which the lower-ranked player defeats the higher-ranked player is no more than $k$. Using the PTAS for Subset-FAST [STOC 2007], Bessy et al. [JCSS 2011] present a $(2 + \varepsilon)k$-vertex kernel for this problem, given any fixed $\varepsilon > 0$. A generalization of Subset-FAST, called Subset-FAST, further includes an additional terminal subset $T \subseteq V(D)$ in the input. The goal of Subset-FAST is to determine whether there is an arc set $S \subseteq A(D)$ of size at most $k$ whose removal ensures that no directed cycle passes through any terminal in $T$. Prior to our work, no polynomial kernel for Subset-FAST was known. In our work, we show that Subset-FAST admits an $\mathcal{O}((\alpha k)^{2})$-vertex kernel, provided that Subset-FAST has an approximation algorithm with an approximation ratio $\alpha$. Consequently, based on the known $\mathcal{O}(\log k \log \log k)$-approximation algorithm, we obtain an almost quadratic kernel for Subset-FAST.