Scalable heuristic algorithm for identifying critical nodes in networks

This paper presents two heuristic algorithms for the distance-based critical node problem (DCNP) that finds k nodes whose removal minimizes the pairwise connection within D hops in the remaining network. The structural properties of the complex networks have not yet been extensively addressed in the literature. Specifically, the community structure of complex networks needs to … Read more

Finding Groups with Maximum Betweenness Centrality via Integer Programming with Random Path Sampling

One popular approach to access the importance/influence of a group of nodes in a network is based on the notion of centrality. For a given group, its group betweenness centrality is computed, first, by evaluating a ratio of shortest paths between each node pair in a network that are “covered” by at least one node … Read more

Large independent sets in Markov random graphs

\(\) Computing the maximum size of an independent set in a graph is a famously hard combinatorial problem that has been well-studied for various classes of graphs. When it comes to random graphs, only the classical binomial random graph \(G_{n,p}\) has been analysed and shown to have largest independent sets of size \(\Theta(\log{n})\) w.h.p. This … Read more

Source Detection on Graphs

Spreading processes on networks (graphs) have become ubiquitous in modern society with prominent examples such as infections, rumors, excitations, contaminations, or disturbances. Finding the source of such processes based on observations is important and difficult. We abstract the problem mathematically as an optimization problem on graphs. For the deterministic setting we make connections to the … Read more

Minimum-Link Covering Trails for any Hypercubic Lattice

In 1994, Kranakis et al. published a conjecture about the minimum link-length of any rectilinear covering path for the k-dimensional grid P(n,k) := {0,1,…,n-1} × {0,1,…,n-1} × … × {0,1,…,n-1}. In this paper we consider the general, NP-complete, Line-Cover problem, where the edges are not required to be axis-parallel, showing that the original Theorem 1 … Read more

Models and Algorithms for the Weighted Safe Set Problem

Given a connected graph G = (V, E), a Safe Set S is a subset of the vertex set V such that the cardinality of each connected component in the subgraph induced by V \ S does not exceed the cardinality of any neighbor connected component in the subgraph induced by S. When the vertices … Read more

A New Bilevel Optimization Approach for Computing Ramsey Numbers

In this article we address the problem of finding lower bounds for small Ramsey numbers $R(m,n)$ using circulant graphs. Our constructive approach is based on finding feasible colorings of circulant graphs using Integer Programming (IP) techniques. First we show how to model the problem as a Stackelberg game and, using the tools of bilevel optimization, … Read more

Interdicting Low-Diameter Cohesive Subgroups in Large-Scale Social Networks

The s-clubs model cohesive social subgroups as vertex subsets that induce subgraphs of diameter at most s. In defender-attacker settings, for low values of s, they can represent tightly-knit communities whose operation is undesirable for the defender. For instance, in online social networks, large communities of malicious accounts can effectively propagate undesirable rumors. In this … Read more

The Graphical Traveling Salesperson Problem has no Integer Programming Formulation in the Original Space

The Graphical Traveling Salesperson Problem (GTSP) is the problem of assigning, for a given weighted graph, a nonnegative number x_e to each edge e such that the induced multi-subgraph is of minimum weight among those that are spanning, connected and Eulerian. Naturally, known mixed-integer programming formulations use integer variables x_e in addition to others. Denis … Read more