Witnessing the advancements in the scale and complexity of chip design, along with the benefits from high-performance computing technologies, the simulation of Very Large Scale Integration (VLSI) circuits increasingly demands acceleration through parallel computing with GPU devices. However, conventional parallel strategies fail to fully leverage modern GPU capabilities, introducing new challenges in GPU-based parallelism for VLSI simulations despite previous demonstrations of significant acceleration. In this paper, we propose a novel approach for accelerating the simulation of 4-value logic timing-aware gate-level circuits through waveform-based GPU parallelism. Our approach introduces an innovative strategy that effectively manages task dependencies during the parallelism of combinational circuits, significantly reducing the synchronization requirement between CPU and GPU. The proposed approach achieves one-pass parallelism by requiring only a single round of data transfer. Moreover, to address the implementation challenges associated with our strategy on GPU devices, we have developed and optimized a series of data structures that dynamically allocate and store newly generated outputs of uncertain scale. Finally, we conduct experiments on industrial-scale open-source benchmarks to demonstrate our approach’s performance gains over several state-of-the-art baselines.

Abstract We consider a two-stage submodular maximization problem subject to a cardinality constraint and k matroid constraints, where the objective function is the expected difference of a nonnegative monotone submodular function and a nonnegative monotone modular function. We give two bi-factor approximation algorithms for this problem. The first is a deterministic $\left( {{1 \over {k + 1}}\left( {1 - {1 \over {{e^{k + 1}}}}} \right),1} \right)$ -approximation algorithm, and the second is a randomized $\left( {{1 \over {k + 1}}\left( {1 - {1 \over {{e^{k + 1}}}}} \right) - \varepsilon ,1} \right)$ -approximation algorithm with improved time efficiency.

Abstract The isolated toughness of a noncomplete graph G is defined as: , where C(G) is the collection of all vertex cutsets of G and i(G − Y) stands for the number of isolated vertices in G − Y. If G is a complete graph, we set . This isolated toughness parameter is closely related to the existence of factors and fractional factors in graphs. These factors and fractional factors are well‐studied within graph theory, and have various applications in several fields related to computer science. In this article, we pay our attention to the computational complexity of computing the isolated toughness. We present polynomial algorithms for computing the exact value of for interval graphs and for split graphs, two well‐studied special graph classes.

In this paper, we consider the perfect demand matching problem ( PDM ) which combines aspects of the knapsack problem along with the b -matching problem. It is a generalization of the maximum weight matching problem which has been fundamental in the development of theory of computer science and operations research . This problem is NP-hard and there exists a constant ϵ > 0 such that the problem admits no 1 + ϵ -approximation algorithm, unless P=NP. Here, we investigate the performance of a distributed message passing algorithm called Max-sum belief propagation for computing the problem of finding the optimal perfect demand matching. As the main result, we demonstrate the rigorous theoretical analysis of the Max-sum BP algorithm for PDM , and establish that within pseudo-polynomial-time, our algorithm could converge to the optimal solution of PDM , provided that the optimal solution of its LP relaxation is unique and integral. Different from the techniques used in previous literature, our analysis is based on primal-dual complementary slackness conditions , and thus the number of iterations of the algorithm is independent of the structure of the given graph. Moreover, to the best of our knowledge, this is one of a very few instances where BP algorithm is proved correct for NP-hard problems.

As an algorithmic framework, message passing is extremely powerful and has wide applications in the context of different disciplines including communications, coding theory, statistics, signal processing, artificial intelligence and combinatorial optimization. In this paper, we investigate the performance of a message-passing algorithm called min-sum belief propagation (BP) for the vertex-disjoint shortest$k$-path problem ($k$-VDSP) on weighted directed graphs, and derive the iterative message-passing update rules. As the main result of this paper, we prove that for a weighted directed graph$G$of order$n$, BP algorithm converges to the unique optimal solution of$k$-VDSP on$G$within$O(n^{2}w_{max})$iterations, provided that the weight$w_{e}$is nonnegative integral for each arc$e\in E(G)$, where$w_{max}=\max \{w_{e}: e\in E(G)\}$. To the best of our knowledge, this is the first instance where BP algorithm is proved correct for NP-hard problems. Additionally, we establish the extensions of$k$-VDSP to the case of multiple sources or sinks.

Due to the rapid development of deep learning (DL) has brought, artificial intelligence (AI) chips were invented incorperating the traditional computing architecture with the simulated neural network structure for the sake of improving the energy efficiency. Recently, emerging deep learning AI chips imposed the challenge of allocating computing resources according to a deep neural networks (DNN), such that tasks using the DNN can be processed in a parallel and distributed manner. In this paper, we combine graph theory and combinatorial optimization technology to devise a fast floorplanning approach based on kernel graph structure, which is provided by Cerebras Systems Inc. for mapping the layers of DNN to the mesh of computing units called Wafer-Scale-Engine (WSE). Numerical experiments were carried out to evaluate our method using the public benchmarks and evaluation criteria, demonstrating its performance gain comparing to the state-of-art algorithms.

In the study of cycles and paths, the meta-conjecture of Bondy that sufficient conditions for Hamiltonicity often imply pancyclicity has motivated research on the existence of cycles and paths of many lengths. Hendry further introduced the stronger concepts of cycle extendability and path extendability, which require that every cycle or path can be extended to another one with one additional vertex. These concepts have been studied extensively, but there exist few results on path extendability in digraphs, as far as we know. In this paper, we make the first attempt in this direction. We establish a number of extremal and degree conditions for path extendability in general digraphs. Moreover, we prove that every path of length at least two in a regular tournament is extendable, with some exceptions. One of our proof approaches is a new contraction operation to transform nonextendable paths into nonextendable cycles.

In 1972, Woodall raised the following Ore-type condition for directed Hamilton cycles in digraphs: Let $D$ be a digraph. If for every vertex pair $u$ and $v$, where there is no arc from $u$ to $v$, we have $d^+(u)+d^-(v)\geq |D|$, then $D$ has a directed Hamilton cycle. By a correspondence between bipartite graphs and digraphs, the above result is equivalent to the following result of Las Vergnas: Let $G = (B,W)$ be a balanced bipartite graph. If for any $b \in B$ and $w \in W$, where $b$ and $w$ are nonadjacent, we have $d(w) +d(b) \geq |G|/2 + 1$, then every perfect matching of $G$ is contained in a Hamilton cycle. The lower bounds in both results are tight. In this paper, we reduce both bounds by $1$ and prove that the conclusions still hold, with only a few exceptional cases that can be clearly characterized.

The minimum all-ones problem was shown to be NP-complete for general graphs. Therefore, it becomes an interesting problem to identify special classes of graphs for which one can find polynomial time algorithms. In this paper we consider this problem for trees. First, for any solution to the all-ones problem for a tree, we give a characterization of the elements in the solution by introducing the concept of the quasi all-ones problem. Then we give the enumeration for the number of solutions in a tree. By using the minimum odd (even) sum problem as subprocess, we obtain a linear time algorithm for the minimum all-ones problem for trees. We also get a linear time algorithm for finding solutions to the all-ones problem in a unicyclic graph.