CS Paper Radar

Algorithmics for Graphical Separation Criteria

Moisés Chavira-Flores, Sebastian Weichwald, Leonard Henckel

cs.LG stat.ML ·submitted 2026-10-27 02:00 UTC · v1
published

Abstract

Statistical graphical models are representations of the dependences between the components of a random vector. They encode these dependences via graphical separation criteria. We consider the algorithmic problem of checking separation statements for the various graph classes and separation criteria that have been developed by the community. We establish that all criteria we study can be checked by modular variations of reachability. For all separation criteria but $σ$-separation, this yields a linear-time algorithm. This is effectively the optimal attainable time since loading the graph itself is linear-time in the number of edges in the graph. Using the CIfly framework for deploying modular variations of reachability, we also provide R and Python code implementing our algorithms. We evaluate empirical runtime and scaling behavior in a simulation study.

Comment
Accepted at PGM 2026, PMLR, Vol. 343

Closest papers

Nearest neighbours by meaning across the whole index.

Parameterized Complexity of Edge-Constrained Graph Partitioning

cs.DS cs.CC ·2026-08-28 ·Ajinkya Gaikwad, Jan Pokorný, Tomáš Valla
similarity 0.58
Abstract

We study the Edge-Constrained Graph Partitioning Problem (ECGP), which asks whether the vertices of a graph can be partitioned into r parts, each inducing at least gamma edges. We also consider a balanced variant (BECGP), requiring equal-sized parts, and signed variants, where the utility of a part is the difference between its numbers of positive and negative edges. We show that ECGP and BECGP remain NP-hard for fixed gamma, while BECGP is also NP-hard for fixed r. For the natural parameterization r+gamma, both problems admit polynomial kernels. We obtain FPT algorithms for ECGP and BECGP parameterized by maximum leaf number, vertex deletion distance to a clique, cluster vertex deletion number plus gamma, and vertex integrity. Furthermore, ECGP is FPT parameterized by vertex deletion distance to stars plus gamma and vertex deletion distance to paths plus gamma. On the negative side, ECGP and BECGP are W[1]-hard when parameterized by r together with several structural parameters. In particular, hardness holds for feedback edge set, vertex deletion distance to stars or paths, and modular width even when the corresponding parameter is zero. The problems are also W[1]-hard parameterized by cluster vertex deletion number plus r, and by clique-width even when gamma=3. For signed graphs, both variants are NP-hard even when r+gamma=3 and the input is a disjoint union of two cliques. Finally, the balanced signed variant is W[1]-hard parameterized by treedepth plus r, even when gamma=0.

0.09

Parameterized Complexity of Connected Network Microaggregation: The Role of Cluster Size

cs.DS ·2026-08-28 ·Ajinkya Gaikwad, Dušan Knop, Tomáš Valla
theory similarity 0.58
Abstract

Network microaggregation is a fundamental technique in statistical disclosure control, where vertices of a graph are partitioned into clusters satisfying size constraints and admitting a center within bounded distance. We study the parameterized complexity of the \emph{unweighted Connected Network Microaggregation} problem, focusing on structural parameters and natural clustering parameters such as the distance bound $d$ and cluster size gap $u-\ell$. We show that, unlike the weighted variant, the unweighted connected problem is fixed-parameter tractable when parameterized by neighborhood diversity, and hence by vertex cover. In contrast, it remains $\mathrm{W[1]}$-hard for more general structural parameters, including vertex deletion to paths, stars, and cliques. These hardness results hold even for every $d\ge 2$ and any fixed gap $u-\ell$, showing that these clustering parameters do not overcome the structural hardness. We further show that adding the cluster size bound $u$ restores tractability for structural parameters such as treewidth and cluster vertex deletion. Moreover, $u$ is essential: the problem remains $\mathrm{W[1]}$-hard when these structural parameters are considered alone. For kernelization, we prove that the problem has no polynomial kernel parameterized by vertex cover unless $\mathrm{coNP}\subseteq\mathrm{NP/poly}$, even when the distance constraint is vacuous. Adding $u$ yields a polynomial kernel for vertex cover, while kernelization remains unlikely for more general structural parameters even when combined with $u$. Finally, we show that the problem is NP-hard on graphs of bounded clique-width.

0.24

$c$-Packedness versus $λ$-Low-Density in Geometric Graphs: Theory and Practice

cs.DS cs.CG ·2026-09-23 ·Gregor Diatzko, Félix Lasseux, Sabine Storandt
theory similarity 0.57
Abstract

When designing algorithms for geometric graphs, exploiting structural parameters can lead to significantly improved bounds. Two prominent parameters in this context are $c$-packedness and $λ$-low density, both of which locally restrict graph complexity. Parameterized algorithms based on these parameters have been developed for computing well-separated pair decompositions, balanced separators, as well as distance oracles. Nevertheless the practical applicability of algorithms parameterized by $c$ or $λ$ remains unclear. While $c$-packed and $λ$-low-density graphs have been proposed as realistic models for road networks, the actual parameter values of large real-world instances have so far remained unknown, and existing theoretical guarantees are partially too loose for practical usage. In this paper we first devise scalable implementations for the approximate computation of $c$ and the exact computation of $λ$. Our experiments on road networks with millions of edges reveals a significant gap between the two parameters. On the theoretical side we prove that $c\in O(λ\sqrt n)$ which complements the known result that $λ\in O(c)$. Furthermore we present improved parameterized algorithms for balanced separator computation that reduce the separator size in theory and practice. We also show how to compute a tree decomposition with a width linear in the respective parameterized balanced separator size in polynomial time. This structural result yields a variety of new algorithmic consequences. Among them is an exact distance oracle with query time $O(c)$ for $c$-packed graphs after polynomial-time preprocessing, which improves upon the previous $O(c\log n)$ bound. Our experiments show that the proposed techniques efficiently produce small balanced separators and enable the construction of concise exact distance oracles on large road networks.

0.27

netseg: a Python Package for Measuring Structural Polarization and Segregation in Social Networks

cs.SI cs.CY ·2026-09-14 ·Onur Tuncay Bal, Michał Bojanowski
benchmarkcode/data similarity 0.57
Abstract

The study of structural polarization and segregation in social networks is an established line of research, and the quantification of both phenomena proceeds through a set of widely cited network indices. The code implementing those indices, however, is seldom released and almost never tested. We present netseg, a comprehensively documented Python package implementing these indices, most of them generalized to more than two groups and to directed as well as undirected input. It ports the R package of the same name and adds measures the R version lacks, among them Random Walk Controversy, Boundary Connectivity, Dipole Moment, and Moran's I. The package operates on igraph objects and performs the underlying graph operations (e.g., neighborhood queries and random-walk simulation) through igraph's Python interface, so that they execute in compiled code rather than in interpreted Python. For several of the indices this yields runtimes orders of magnitude below those of the available open-source implementations, which the documentation reports in benchmarks. Most of these indices are defined as a divergence from a null model, and published implementations fix that null model to a uniform random graph of matching density. netseg accepts an ensemble of graphs as a sample from an arbitrary null model, and distinguishes indices that already incorporate a baseline from those that do not, adjusting the comparison accordingly to avoid double subtraction. The documentation provides, for each index, a worked empirical example, its behaviour at the degenerate cases where it is undefined, a benchmark, and the procedure for substituting a custom null model. We report the behaviour of every index over a parameter sweep of a generative opinion model, and apply them to a county-level railroad network built from nineteenth-century operator records joined to full-count census data.

0.41

Partition Space Maps for Community Detection: Visualizing Algorithmic Behaviour and Guiding Search

cs.SI ·2026-09-29 ·Fabio Morea
benchmark similarity 0.56
Abstract

Community-detection methods search over possible partitions of a network, but the structure of this partition space is rarely examined directly. This paper introduces two complementary tools that make~$\mathcal{P}$ analytically and visually accessible. First, a canonical labelling scheme based on the Restricted Growth Sequence~(RGS) is adopted, assigning each partition a unique, permutation-invariant identifier and eliminating the need for pairwise similarity measures such as the Normalized Mutual Information. Second, granularity~$Γ$ is defined and combined with modularity~$Q$ to produce a two-dimensional projection: the Partition Space Map~(PSM). Within the $(Γ,Q)$ plane, only a discrete set of integer values of~$Γ$ is attainable, and upper and lower bounds on~$Q$ are derived directly from the deviation matrix. These tools are demonstrated through complete enumeration of~$\mathcal{P}$ for small benchmark graphs, revealing the fine structure of modularity degeneracy and the combinatorial constraints that shape the feasible region. The framework provides an exact, assumption-free reference for evaluating heuristic community detection algorithms and lays the groundwork for geometry-aware exploration of partition space in larger networks.

0.31

Destroying Rigidity in the Plane

cs.DM ·2026-10-28 ·Yu Cong, Chao Xu, Yajie Zhao
theory similarity 0.56
Abstract

Rigidity and global rigidity are fundamental graph properties in discrete geometry, with applications to structural engineering and network localization. In two dimensions, both admit combinatorial characterizations in terms of the rigidity matroid and graph connectivity. We study the computational complexity of finding minimum-cost sets of edges or vertices whose deletion destroys either property in a finite simple graph. With unit costs, we give deterministic polynomial-time algorithms for edge deletion destroying global rigidity and vertex deletion destroying either property. We prove that edge deletion destroying rigidity is NP-hard and that, with positive integer costs, all four problems are NP-hard. These results resolve, in dimension two, the open questions on recognizing robustness under edge and vertex deletions posed by Jordán and Whiteley (2017), as well as the minimum edge-deletion problem for rigidity recorded in EGRES Open.

0.42

Perfect Italian Domination on and Near Split Graphs: Algorithms, Hardness, and Approximation

cs.DM ·2026-10-07 ·Anand Babu N B, Ashwin Jacob, Manjusha M S, Renjith P
similarity 0.56
Abstract · Submitted to CALDAM 2027

A perfect Italian dominating function assigns a label from $\{0,1,2\}$ to each vertex so that the labels in the neighborhood of every zero-labeled vertex sum to exactly two. Although the associated decision problem (PID) is NP-complete on chordal graphs, the complexity status on split graphs remains open. We give an $O(n^4)$ time algorithm for split graphs on $n$ vertices. We note that this is in contrast to Roman, Italian, and perfect Roman domination, which are NP-complete on split graphs. We further show that this tractability boundary is tight: PID is NP-hard on graphs at deletion distance one from split graphs. We also provide dichotomy results for PID on restricted extensions of split graphs formed by attaching pendant stars, and establish inapproximability results for the same.

0.09

Exact computation of the network modularity with branch-and-bound

cs.SI stat.CO ·2026-10-03 ·Emily Weng, Georg Hahn
publishedbenchmark similarity 0.56
Abstract

We consider the computation of the network modularity, a common measure of the structure of networks or graphs that quantifies the division of a network into modules or clusters. The computation of the network modularity is an NP-hard problem, thus making its exact computation often infeasible in practice. This has resulted in the development of several heuristics in the literature. In this work, we consider the exact computation of the network modularity with the help of a branch-and-bound algorithm. Our algorithm is guaranteed to find the optimal clustering that maximizes the network modularity, however it achieves this without a full exploration of the search space. This is accomplished by bounding partial solutions and discarding them if it can be foreseen that a partial solution will not yield an improvement over an existing solution. We assess our algorithm with respect to accuracy and runtime and compare it to a brute-force approach as well as two benchmark algorithms, simulated annealing and the Louvain method.

0.40