Tomohiro Koana

Tomohiro Koana, Soh Kumabe

\textsc{$H$-Packing} asks whether a graph $G$ contains $k$ vertex-disjoint copies of a fixed pattern graph $H$. Via the standard reduction to \textsc{$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_1,d_2}$ denote the subdivided star with $d_1$ branches of length $1$ and $d_2$ branches of length $2$. We obtain kernels with $O(k^2)$ vertices and $O(k^3)$ edges for $P_5=S_{0,2}$, for $S_{1,2}$, and for every $S_{d_1,1}$, kernels with $O(k^4)$ vertices and $O(k^6)$ edges for every fixed $S_{d_1,d_2}$ with $d_1\ge 1$, and a kernel with $O(k^2)$ vertices and $O(k^4)$ 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\ge 3$ and every $\varepsilon>0$, \textsc{$S_{0,d}$-Packing} does not admit a compression of size $O(k^{d-\varepsilon})$ unless $\NP\subseteq \coNP/\poly$. Thus, deleting a single vertex from the pattern may, surprisingly, make kernelization provably harder, showing that compressibility of \textsc{$H$-Packing} is not monotone under taking induced subgraphs.

Karl Bringmann, Danny Hermelin, Tomohiro Koana et al.

The Lawler-Moore dynamic programming framework is a classical tool in scheduling on parallel machines. It applies when the objective is regular, i.e. monotone in job completion times, and each machine follows a fixed priority order such as Smith's Rule or Jackson's Rule. For the basic objectives $Pm||\sum w_jC_j$, $Pm||L_{\max}$, and $Pm||\sum w_jU_j$, it gives running times $O(P^{m-1}n)$, $O(P^{m-1}n)$, and $O(P^mn)$, respectively, where $P$ is the total processing time. Recent SETH-based lower bounds indicate that the dependence on $P$ is essentially optimal, but they do not rule out improved dependence on the maximum processing time $p_{\max}$. We give the first major speedup of the Lawler-Moore recurrence. Our main ingredients are a new state-pruning method and a swapping argument based on an additive-combinatorial lemma. We prove that, whenever this swap does not increase the objective value, there exists an optimal schedule in which, for every prefix of jobs, the load difference between any two machines is at most $4p_{\max}^2$. This lets us prune redundant states throughout the dynamic program, replacing the dependence on $P$ by a dependence on $p_{\max}^2$. We show that the swap is non-increasing for all three objectives above. Hence $Pm||\sum w_jC_j$ and $Pm||L_{\max}$ admit algorithms with running time $O(p_{\max}^{2m-2}n)$, while $Pm||\sum w_jU_j$ can be solved in time $O(p_{\max}^{2m-2}Pn)\le O(p_{\max}^{2m-1}n^2)$. These bounds strictly improve the original Lawler-Moore runtimes whenever $p_{\max}=o(\sqrt{P})$. In particular, for $Pm||\sum w_jC_j$ and $Pm||L_{\max}$, we obtain the first near-linear-time algorithms when processing times are polylogarithmic in $n$.

Afrouz Jabal Ameli, Tomohiro Koana, Jesper Nederlof et al.

The Strongly Connected Steiner Subgraph (SCSS) problem is a well-studied network design problem that asks for a minimum subgraph that strongly connects a given set of terminals. In this paper, we present several new algorithmic and complexity results for SCSS. As our main result, we show that SCSS can be solved in time $17^{\mathrm{tw}} n^{O(1)}$ on directed graphs with $n$ vertices when a tree decomposition of the underlying graph of width $\mathrm{tw}$ is provided. This improves over a natural $\mathrm{tw}^{O(\mathrm{tw})}n^{O(1)}$ time algorithm, and is the first algorithm with this kind of running time for a problem involving strong connectivity. Second, we give an exact exponential-time algorithm that solves SCSS in $2^n n^{O(1)}$ time, improving the known bounds for general directed graphs. Finally, we investigate kernelization with respect to vertex cover. We prove that SCSS does not admit a polynomial kernel when parameterized by the size of a vertex cover, unless the polynomial hierarchy collapses. In contrast, we show that the closely related Strongly Connected Spanning Subgraph problem does admit a polynomial kernel under the same parameterization.