Given a graph \(G = (V,\!E)\) with \(n\) vertices and \(m\) edges, the Dominating Set problem asks for a set \(\mathcal{D} \subseteq V\) of minimal cardinality such that every vertex either is in \(D\) or adjacent to a member of \(D\). Although there is little hope for a kernelization algorithm on general graphs due to the W[2]-hardness of Dominating Set, data reduction rules are extensively used in practice.

We consider a maximum entropy edge weight model that allows for negative weights. Given a graph $G$ and possible weights $\mathcal{W}$ typically consisting of positive and negative values, the model selects edge weights $w \in \mathcal{W}^m$ uniformly at random from all weights that do not introduce a negative cycle. We propose an MCMC process and show that it converges to the required distribution. We then engineer an implementation of the process using a dynamic version of Johnson's algorithm in connection with a bidirectional Dijkstra search as well as an innovative resampling method. We empirically study the performance characteristics of these novel sampling algorithms as well as the output produced by the model.

A graph is called a $(k,ρ)$-graph iff every node can reach $ρ$ of its nearest neighbors in at most k hops. This property proved useful in the analysis and design of parallel shortest-path algorithms. Any graph can be transformed into a $(k,ρ)$-graph by adding shortcuts. Formally, the $(k,ρ)$-Minimum-Shortcut problem asks to find an appropriate shortcut set of minimal cardinality. We show that the $(k,ρ)$-Minimum-Shortcut problem is NP-complete in the practical regime of $k \ge 3$ and $ρ= Θ(n^ε)$ for $ε> 0$. With a related construction, we bound the approximation factor of known $(k,ρ)$-Minimum-Shortcut problem heuristics from below and propose algorithmic countermeasures improving the approximation quality. Further, we describe an integer linear problem (ILP) solving the $(k,ρ)$-Minimum-Shortcut problem optimally. Finally, we compare the practical performance and quality of all algorithms in an empirical campaign.