\(\) 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
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
\(\) In 1994, Kranakis et al. published a conjecture about the minimum link-length of every rectilinear covering path for the \(k\)-dimensional grid \(P(n,k) := \{0,1, \dots, n-1\} \times \{0,1, \dots, n-1\} \times \cdots \times \{0,1, \dots, n-1\}\). In this paper we consider the general, NP-complete, Line-Cover problem, where the edges are not required to be … Read more
In this paper, we show enhanced upper bounds of the nontrivial n_1 × n_2 × n_3 points problem for every n_1
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
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
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 (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
We introduce a new graph-theoretic paradigm called a graph signature that describes persistent patterns in a sequence of graphs. This framework is motivated by the need to detect subgraphs of significance in temporal networks, e.g., social and biological networks that evolve over time. Because the subgraphs of interest may not all “look alike” in the … Read more
The clique problem with multiple-choice constraints (CPMC), i.e. the problem of finding a k-clique in a k-partite graph with known partition, occurs as a substructure in many real-world applications, in particular scheduling and railway timetabling. Although CPMC is NP-complete in general, it is known to be solvable in polynomial time when the so-called dependency graph … Read more