Search for: All records

Packing disjoint subgraphs in a given graph is a fundamental problem with many applications. Motivated by political districting, we focus on connected subgraphs that are compact (e.g., having constant radius from a single center vertex) and that satisfy additional composition requirements, such as a minimum population/weight threshold or balanced weight types (e.g., political affiliations). We aim to maximize coverage by disjoint districts that meet these requirements. In this work, we present new results that substantially improve the previously known bounds on balanced star districts for planar and minor-free graphs (Dharangutte et al. 2025). In particular, we improve the approximation factor from to for packing balanced star districts using the exact same algorithm, but with a refined analysis. We also extend the results beyond planar graphs to minor-free graphs and an even broader family of graphs of bounded expansion. Additionally, we obtain an approximation for packing radius- districts (with a constant ) in planar and apex-minor-free graphs. In order to get a approximation on the max coverage, we show that this can be achieved if we allow a slight relaxation of the balancedness parameters (by a factor that can be made arbitrarily close to ), for bounded radius- districts on planar and apex-minor-free graphs. We show that all of these results can also be obtained if we enforce a minimum weight threshold for each district as the composition requirement, rather than balancedness. We present various results on hardness and hardness of approximation for this variant, by graph and district types. 

Abstract In‐stream wood structures, such as single logs, river steps, and debris dams, are known to drive hyporheic flow, defined as the flow that goes into the subsurface region and then back to the free‐flowing surface water. The hyporheic flow plays an important role in regulating water quality and biogeochemical cycles in rivers. Here, we investigated the impact of a channel‐spanning porous log jam, representing piles of wood logs, on hyporheic flow through a combination of direct visualization and theories. Specifically, we developed a method using refractive index‐matched sediment to directly visualize the hyporheic flow around and below a porous log jam, formed by piles of cylindrical rods, in a laboratory flume. We tracked the velocity of a fluorescent dye moving through the transparent sediment underneath the log jam. In addition, we measured the water surface profile and the spatially varying flow velocity near the log jam. Our results show that the normalized log jam‐induced hyporheic flux remained smaller than 10% at Froude numbers () below 0.06 and increased by a factor of five with increasing at . We combined the mass and momentum conservation equations of surface flow with Darcy's equation to explain the dependency of the log jam‐induced hyporheic flux on . Further, we observed that at , the water surface dropped noticeably and the turbulent kinetic energy increased immediately on the downstream side of the log jam. These findings will facilitate future quantification of hyporheic flow caused by channel‐spanning porous log jams. 

Abstract Hyporheic exchange leads to the transfer of gases, solutes, and fine particles across the sediment‐water interface, playing a critical role in biogeochemical cycles and pollutant transport in aquatic environments. While in‐channel vegetation has been recognized to enhance hyporheic exchange, the mechanisms remain poorly understood. Here, we investigated how an emergent vegetation canopy impacts hyporheic exchange using refractive index‐matched flume experiments and coupled numerical simulations. Our results show that at the same mean surface flow velocity, vegetation increases the hyporheic exchange velocity by four times compared to the non‐vegetated channel. However, the hyporheic exchange velocity does not increase further with increasing vegetation density. In addition, our results show that the hyporheic exchange velocity scales with the square root of sediment permeability. Our findings provide a predictive framework for hyporheic exchange in vegetated channels with varying vegetation densities and sediment permeabilities and could guide the future design of environmental management and restoration projects using vegetation. 

Many real-world networks evolve over time, and predicting the evolution of such networks remains a challenging task. Graph Neural Networks (GNNs) have shown empirical success for learning on static graphs, but they lack the ability to effectively learn from nodes and edges with different timestamps. Consequently, the prediction of future properties in temporal graphs remains a relatively under-explored area. In this paper, we aim to bridge this gap by introducing a principled framework, named GraphPulse. The framework combines two important techniques for the analysis of temporal graphs within a Newtonian framework. First, we employ the Mapper method, a key tool in topological data analysis, to extract essential clustering information from graph nodes. Next, we harness the sequential modeling capabilities of Recurrent Neural Networks (RNNs) for temporal reasoning regarding the graph's evolution. Through extensive experimentation, we demonstrate that our model enhances the ROC-AUC metric by 10.2% in comparison to the top-performing state-of-the-art method across various temporal networks. We provide the implementation of GraphPulse at https://github.com/kiarashamsi/GraphPulse.