Shengzhe Wang

Bernhard Haeupler, Richard Hladík, Shengzhe Wang et al.

This paper significantly strengthens directed low-diameter decompositions in several ways. We define and give the first results for separated low-diameter decompositions in directed graphs, tighten and generalize probabilistic guarantees, and prove new independence results between (far away) edges. Our results are the first to give meaningful guarantees for decompositions with small diameters $D = Ω(\log\log n)$ in contrast to the state of the art that only applies to super-logarithmic diameters $D = ω(\log n)$. These results transfer several important and widely used aspects of undirected low-diameter decompositions to the directed setting. All our results are algorithmic -- small modifications to two existing directed low-diameter decompositions [BFHL25; Li25] can be used to sample decompositions with our new guarantees in near-linear time $\tilde{O}(m)$.

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.

Afrouz Jabal Ameli, Jesper Nederlof, Shengzhe Wang

We provide improved space-time tradeoffs for permutation problems over additively idempotent semi-rings. In particular, there is an algorithm for the Traveling Salesperson Problem that solves $N$-vertex instances using space $S$ and time $T$ where $S\cdot T \leq 3.7493^{N}$. This improves a previous work by Koivisto and Parviainen [SODA'10] where $S\cdot T \leq 3.9271^N$, and overcomes a barrier they identified, as their bound was shown to be optimal within their framework. To get our results, we introduce a new parameter of a set system that we call the chain efficiency. This relates the number of maximal chains contained in the set system with the cardinality of the system. We show that set systems of high efficiency imply efficient space-time tradeoffs for permutation problems, and give constructions of set systems with high chain efficiency, disproving a conjecture by Johnson, Leader and Russel [Comb. Probab. Comput.'15].

Shengzhe Wang, Ling Wang, Zhihao Lin et al.

Existing Deep Neural Nets on crops growth prediction mostly rely on availability of a large amount of data. In practice, it is difficult to collect enough high-quality data to utilize the full potential of these deep learning models. In this paper, we construct an innovative network architecture based on domain adaptation learning to predict crops growth curves with limited available crop data. This network architecture overcomes the challenge of data availability by incorporating generated data from the developed crops simulation model. We are the first to use the temporal convolution filters as the backbone to construct a domain adaptation network architecture which is suitable for deep learning regression models with very limited training data of the target domain. We conduct experiments to test the performance of the network and compare our proposed architecture with other state-of-the-art methods, including a recent LSTM-based domain adaptation network architecture. The results show that the proposed temporal convolution-based network architecture outperforms all benchmarks not only in accuracy but also in model size and convergence rate.