H-Packing asks whether a graph G contains k vertex-disjoint copies of a fixed pattern graph H. Via the standard reduction to d-Set Packing, one obtains generic kernels with O(k^{|V(H)|-1}) vertices and O(k^|V(H)|) edges. We revisit the question of beating these bounds for specific patterns H. Our main results concern subdivided stars. Let S_{d₁,d₂} denote the subdivided star with d₁ branches of length 1 and d₂ branches of length 2. We obtain kernels with O(k²) vertices and O(k³) edges for P₅ = S_{0,2}, for S_{1,2}, and for every S_{d₁,1}, kernels with O(k⁴) vertices and O(k⁶) edges for every fixed S_{d₁,d₂} with d₁ ≥ 1, and a kernel with O(k²) vertices and O(k⁴) edges for the paw. Our proofs proceed in two steps. First, we reduce to instances in which all but a small part of the graph is independent, or in which the graph has a small vertex cover. Second, we reduce the independent side by keeping only a bounded number of witness vertices for each subset of the small part. On the negative side, we prove a lower bound for the line S_{0,d}. For every d ≥ 3 and every ε > 0, S_{0,d}-Packing does not admit a compression of size O(k^{d-ε}) unless NP ⊆ coNP/poly. Thus, deleting a single vertex from the pattern may, surprisingly, make kernelization provably harder, showing that compressibility of H-Packing is not monotone under taking induced subgraphs.

Regular Expression Denial of Service (ReDoS) is a well-known type of algorithmic complexity attack, where an adversary supplies maliciously crafted strings to a regular expression matching engine, aiming to exhaust computational resources of systems. Even quadratic-time behavior in matching engines has been exploited in successful attacks, as exemplified by major outages at Stack Overflow (2016) and Cloudflare (2019). These incidents motivate a fundamental question: Is it possible to construct matching engines that run in linear or near-linear time in the length of the input string? For classical regular expressions (REGEX), Thompson’s construction yields a linear-time algorithm for fixed expressions. However, practical engines support powerful features such as backreferences, which allow capturing a substring and reusing it later. This feature strictly extends the expressive power of REGEX but unfortunately increases the risk of ReDoS attacks. This paper investigates the fine-grained complexity of the string matching problem for regular expressions with backreferences (REWBs). Specifically, we consider r-use k-REWBs, i.e., REWBs with k variables such that, in any computation, the total number of backreference executions is at most r. On the hardness side, we show that the string matching problem for k-REWBs cannot be solved in O(n^{2k-ε}) time for any ε > 0 under the Strong Exponential Time Hypothesis (SETH), where n is the length of the input string. We also prove that this problem is W[2]-hard when parameterized by the length of the REWB expression, strengthening the previous W[1]-hardness result. Moreover, we prove that this problem for 2-use 2-REWBs cannot be solved in n^{1+o(1)} time unless the triangle detection problem can be solved in that time. On the algorithmic side, we present an O(n log² n)-time algorithm for 1-use REWBs. In particular, we focus on the ABCBD problem, which is the REWB matching problem for the form A(B)_xC∖xD where A, B, C, and D are fixed REGEXes. We also show that every 1-use REWB can be transformed into this canonical form. Our algorithm significantly improves upon the recent O(n²)-time algorithm for the ABCBD problem by Nogami and Terauchi (MFCS, 2025). Our algorithm is highly nontrivial and employs several techniques, including suffix trees, transition monoids of REGEXes, factorization forest data structures, and periodicity of strings.

Lipschitz continuity of algorithms, introduced by Kumabe and Yoshida (FOCS'23), measures the stability of an algorithm against small input perturbations. Algorithms with small Lipschitz continuity are desirable, as they ensure reliable decision-making and reproducible scientific research. Several studies have proposed Lipschitz continuous algorithms for various combinatorial optimization problems, but these algorithms are problem-specific, requiring a separate design for each problem. To address this issue, we provide the first algorithmic meta-theorem in the field of Lipschitz continuous algorithms. Our result can be seen as a Lipschitz continuous analogue of Courcelle’s theorem, which offers Lipschitz continuous algorithms for problems on bounded-treewidth graphs. Specifically, we consider the problem of finding a vertex set in a graph that maximizes or minimizes the total weight, subject to constraints expressed in monadic second-order logic (MSO₂). We show that for any ε > 0, there exists a (1±ε)-approximation algorithm for the problem with a polylogarithmic Lipschitz constant on bounded treewidth graphs. On such graphs, our result outperforms most existing Lipschitz continuous algorithms in terms of approximability and/or Lipschitz continuity. Further, we provide similar results for problems on bounded-clique-width graphs subject to constraints expressed in MSO₁. Additionally, we construct a Lipschitz continuous version of Baker’s decomposition using our meta-theorem as a subroutine.

Let $\mathcal{D}$ be a set family that is the solution domain of some combinatorial problem. The \emph{max-min diversification problem on $\mathcal{D}$} is the problem to select $k$ sets from $\mathcal{D}$ such that the Hamming distance between any two selected sets is at least $d$. FPT algorithms parameterized by $k+\ell $, where $\ell=\max_{D\in \mathcal{D}}|D|$, and $k+d$ have been actively studied recently for several specific domains. This paper provides unified algorithmic frameworks to solve this problem. Specifically, for each parameterization $k+\ell $ and $k+d$, we provide an FPT oracle algorithm for the max-min diversification problem using oracles related to $\mathcal{D}$. We then demonstrate that our frameworks provide the first FPT algorithms on several new domains $\mathcal{D}$, including the domain of $t$-linear matroid intersection, almost $2$-SAT, minimum edge $s,t$-flows, vertex sets of $s,t$-mincut, vertex sets of edge bipartization, and Steiner trees. We also demonstrate that our frameworks generalize most of the existing domain-specific tractability results. Our main technical breakthrough is introducing the notion of \emph{max-distance sparsifier} of $\mathcal{D}$, a domain on which the max-min diversification problem is equivalent to the same problem on the original domain $\mathcal{D}$. The core of our framework is to design FPT oracle algorithms that construct a constant-size max-distance sparsifier of $\mathcal{D}$. Using max-distance sparsifiers, we provide FPT algorithms for the max-min and max-sum diversification problems on $\mathcal{D}$, as well as $k$-center and $k$-sum-of-radii clustering problems on $\mathcal{D}$, which are also natural problems in the context of diversification and have their own interests.

We consider Cliques or Trees Vertex Deletion, which is a hybrid of two fundamental parameterized problems: Cluster Vertex Deletion and Feedback Vertex Set. In this problem, we are given an undirected graph G and an integer k, and asked to find a vertex subset X of size at most k such that each connected component of G-X is either a clique or a tree. Jacob et al. (ISAAC, 2024) provided a kernel of O(k⁵) vertices for this problem, which was recently improved to O(k⁴) by Tsur (IPL, 2025). Our main result is a kernel of O(k²) vertices. This result closes the gap between the kernelization result for Feedback Vertex Set, which corresponds to the case where each connected component of G-X must be a tree. Although both cluster vertex deletion number and feedback vertex set number are well-studied structural parameters, little attention has been given to parameters that generalize both of them. In fact, the lowest common well-known generalization of them is clique-width, which is a highly general parameter. To fill the gap here, we initiate the study of the cliques or trees vertex deletion number as a structural parameter. We prove that Longest Cycle, which is a fundamental problem that does not admit o(n^k)-time algorithm unless ETH fails when k is the clique-width, becomes fixed-parameter tractable when parameterized by the cliques or trees vertex deletion number.

Combinatorial algorithms are widely used for decision-making and knowledge discovery, and it is important to ensure that their output remains stable even when subjected to small perturbations in the input. Failure to do so can lead to several problems, including costly decisions, reduced user trust, potential security concerns, and lack of replicability. Unfortunately, many fundamental combinatorial algorithms are vulnerable to small input perturbations. To address the impact of input perturbations on algorithms for weighted graph problems, Kumabe and Yoshida (FOCS’23) recently introduced the concept of Lipschitz continuity of algorithms. This work explores this approach and designs Lipschitz continuous algorithms for covering problems, such as the minimum vertex cover, set cover, and feedback vertex set problems.

In cooperative game theory, the primary focus is the equitable allocation of payoffs or costs among agents. However, in the practical applications of cooperative games, accurately representing games is challenging. In such cases, using an allocation method sensitive to small perturbations in the game can lead to various problems, including dissatisfaction among agents and the potential for manipulation by agents seeking to maximize their own benefits. Therefore, the allocation method must be robust against game perturbations. In this study, we explore optimization games, in which the value of the characteristic function is provided as the optimal value of an optimization problem. To assess the robustness of the allocation methods, we use the Lipschitz constant, which quantifies the extent of change in the allocation vector in response to a unit perturbation in the weight vector of the underlying problem. Thereafter, we provide an algorithm for the matching game that returns an allocation belonging to the $\left(\frac{1}{2}-ε\right)$-approximate core with Lipschitz constant $O(ε^{-1})$. Additionally, we provide an algorithm for a minimum spanning tree game that returns an allocation belonging to the $4$-approximate core with a constant Lipschitz constant. The Shapley value is a popular allocation that satisfies several desirable properties. Therefore, we investigate the robustness of the Shapley value. We demonstrate that the Lipschitz constant of the Shapley value for the minimum spanning tree is constant, whereas that for the matching game is $Ω(\log n)$, where $n$ denotes the number of vertices.

Graph algorithms are widely used for decision making and knowledge discovery. To ensure their effectiveness, it is essential that their output remains stable even when subjected to small perturbations to the input because frequent output changes can result in costly decisions, reduced user trust, potential security concerns, and lack of replicability. In this study, we consider the Lipschitz continuity of algorithms as a stability measure and initiate a systematic study of the Lipschitz continuity of algorithms for (weighted) graph problems.Depending on how we embed the output solution to a metric space, we can think of several Lipschitzness notions. We mainly consider the one that is invariant under scaling of weights, and we provide Lipschitz continuous algorithms and lower bounds for the minimum spanning tree problem, the shortest path problem, and the maximum weight matching problem. In particular, our shortest path algorithm is obtained by first designing an algorithm for unweighted graphs that are robust against edge contractions and then applying it to the unweighted graph constructed from the original weighted graph.Then, we consider another Lipschitzness notion induced by a natural mapping from the output solution to its characteristic vector. It turns out that no Lipschitz continuous algorithm exists for this Lipschitz notion, and we instead design algorithms with bounded pointwise Lipschitz constants for the minimum spanning tree problem and the maximum weight bipartite matching problem. Our algorithm for the latter problem is based on an LP relaxation with entropy regularization.

When processing data with uncertainty, it is desirable that the output of the algorithm is stable against small perturbations in the input. Varma and Yoshida [SODA'21] recently formalized this idea and proposed the notion of average sensitivity of algorithms, which is roughly speaking, the average Hamming distance between solutions for the original input and that obtained by deleting one element from the input, where the average is taken over the deleted element. In this work, we consider average sensitivity of algorithms for problems that can be solved by dynamic programming. We first present a (1–δ)-approximation algorithm for finding a maximum weight chain (MWC) in a transitive directed acyclic graph with average sensitivity O(δ–1 log3 n), where n is the number of vertices in the graph. We then show algorithms with small average sensitivity for various dynamic programming problems by reducing them to the MWC problem while preserving average sensitivity, including the longest increasing subsequence problem, the interval scheduling problem, the longest common subsequence problem, the longest palindromic subsequence problem, the knapsack problem with integral weight, and the RNA folding problem. For the RNA folding problem, our reduction is highly nontrivial because a naive reduction generates an exponentially large graph, which only provides a trivial average sensitivity bound.

In this paper, we introduce the \emph{interval query problem} on cube-free median graphs. Let $G$ be a cube-free median graph and $\mathcal{S}$ be a commutative semigroup. For each vertex $v$ in $G$, we are given an element $p(v)$ in $\mathcal{S}$. For each query, we are given two vertices $u,v$ in $G$ and asked to calculate the sum of $p(z)$ over all vertices $z$ belonging to a $u-v$ shortest path. This is a common generalization of range query problems on trees and grids. In this paper, we provide an algorithm to answer each interval query in $O(\log^2 n)$ time. The required data structure is constructed in $O(n\log^3 n)$ time and $O(n\log^2 n)$ space. To obtain our algorithm, we introduce a new technique, named the \emph{stairs decomposition}, to decompose an interval of cube-free median graphs into simpler substructures.

The b-matching game is a cooperative game defined on a graph. The game generalizes the matching game to allow each individual to have more than one partner. The game has several applications, such as the roommate assignment, the multi-item version of the seller-buyer assignment, and the international kidney exchange. Compared with the standard matching game, the b-matching game is computationally hard. In particular, the core non-emptiness problem and the core membership problem are co-NP-hard. Therefore, we focus on the convexity of the game, which is a sufficient condition of the core non-emptiness and often more tractable concept than the core non-emptiness. It also has several additional benefits. In this study, we give a necessary and sufficient condition of the convexity of the b-matching game. This condition also gives an O(n log n + m α(n)) time algorithm to determine whether a given game is convex or not, where n and m are the number of vertices and edges of a given graph, respectively, and α(・) is the inverse-Ackermann function. Using our characterization, we also give a polynomial-time algorithm to compute the Shapley value of a convex b-matching game.