In the NP-hard Π-Network Sparsification problem, we are given an edge-weighted graph G, a collection 𝒞 of c subsets of V(G), called communities, and two numbers 𝓁 and b, and the question is whether there exists a spanning subgraph G' of G with at most 𝓁 edges of total weight at most b such that G'[C] fulfills Π for each community C ∈ 𝒞. We study the fine-grained and parameterized complexity of two special cases of this problem: Connectivity NWS where Π is the connectivity property and Stars NWS, where Π is the property of having a spanning star. First, we provide a tight 2^Ω(n²+c)-time running time lower bound based on the ETH for both problems, where n is the number of vertices in G even if all communities have size at most 4, G is a clique, and every edge has unit weight. For the connectivity property, the unit weight case with G being a clique is the well-studied problem of computing a hypergraph support with a minimum number of edges. We then study the complexity of both problems parameterized by the feedback edge number t of the solution graph G'. For Stars NWS, we present an XP-algorithm for t answering an open question by Korach and Stern [Discret. Appl. Math. '08] who asked for the existence of polynomial-time algorithms for t = 0. In contrast, we show for Connectivity NWS that known polynomial-time algorithms for t = 0 [Korach and Stern, Math. Program. '03; Klemz et al., SWAT '14] cannot be extended to larger values of t by showing NP-hardness for t = 1.

In this paper we present StaTS, a precise static data-race detection mechanism for Java. It analyzes applications in four phases. The first one is a novel points-to analysis that includes approximations of threads and execution contexts. The second phase uses the results of the points-to analysis to compute which fields are accessed by which threads, while considering the locks held by the threads. The third phase carries out a context-sensitive static happens-before analysis to rule out accesses in execution contexts that can never be executed in parallel. The final phase builds upon the results of the first three to determine conflicting accesses and report them to the user. Our proof-of-concept implementation does not scale for large programs, which is why it can optionally limit the number of points-to relations it considers, based on sampling. Nevertheless, our evaluation shows that, even with sampling enabled for large programs, StaTS detects more data races than existing approaches. In terms of execution time, the analysis without sampling takes in the order of seconds for smaller programs. For larger ones and with sampling enabled, analysis takes minutes, thus being practically usable in nightly build environments in all cases.