Search

We study a family of reachability problems under waiting-time restrictions in temporal and vertex-colored temporal graphs. Given a temporal graph and a set of source vertices, we find the set of vertices that are reachable from a source via a time-respecting path, where the difference in timestamps between consecutive edges is at most a resting time. Given a vertex-colored temporal graph and a multiset query of colors, we find the set of vertices reachable from a source via a time-respecting path such that the vertex colors of the path agree with the multiset query and the difference in timestamps between consecutive edges is at most a resting time. These kind of problems have several applications in understanding the spread of a disease in a network, tracing contacts in epidemic outbreaks, finding signaling pathways in the brain network, and recommending tours for tourists. We present an algebraic algorithmic framework based on constrained multilinear sieving for solving the restless reachability problems we propose. In particular, parameterized by the length of a path $k$ sought, we show the problems can be solved in $O(2^k k m \Delta)$ time and $O(n \tau)$ space, where $n$ is the number of vertices, $m$ the number of edges, $\Delta$ the maximum resting time and $\tau$ the maximum timestamp of an input temporal graph. In addition, we prove that the algorithms presented for the restless reachability problems in vertex-colored temporal graphs are optimal under plausible complexity-theoretic assumptions. Finally, with an open-source implementation, we demonstrate that our algorithm scales to large graphs with up to one billion temporal edges, despite the problems being NP-hard. Specifically, we present extensive experiments to evaluate our scalability claims both on synthetic and real-world graphs., Comment: The paper is updated with more illustrations for improving readability and directed towards broader audience (non-expert group)

Combinatorial optimization problems arise in a wide range of applications from diverse domains. Many of these problems are NP-hard and designing efficient heuristics for them requires considerable time and experimentation. On the other hand, the number of optimization problems in the industry continues to grow. In recent years, machine learning techniques have been explored to address this gap. We propose a framework for leveraging machine learning techniques to scale-up exact combinatorial optimization algorithms. In contrast to the existing approaches based on deep-learning, reinforcement learning and restricted Boltzmann machines that attempt to directly learn the output of the optimization problem from its input (with limited success), our framework learns the relatively simpler task of pruning the elements in order to reduce the size of the problem instances. In addition, our framework uses only interpretable learning models based on intuitive features and thus the learning process provides deeper insights into the optimization problem and the instance class, that can be used for designing better heuristics. For the classical maximum clique enumeration problem, we show that our framework can prune a large fraction of the input graph (around 99 % of nodes in case of sparse graphs) and still detect almost all of the maximum cliques. This results in several fold speedups of state-of-the-art algorithms. Furthermore, the model used in our framework highlights that the chi-squared value of neighborhood degree has a statistically significant correlation with the presence of a node in a maximum clique, particularly in dense graphs which constitute a significant challenge for modern solvers. We leverage this insight to design a novel heuristic for this problem outperforming the state-of-the-art. Our heuristic is also of independent interest for maximum clique detection and enumeration., Comment: Integrates three works which appeared at AAAI'19 [arXiv:1902.08455], the DSO workshop at IJCAI'19 [arXiv:1910.00517] and CIKM'19

In the \probrFix problem, we are given a graph $G$, a (non-proper) vertex-coloring $c : V(G) \to [r]$, and a positive integer $k$. The goal is to decide whether a proper $r$-coloring $c'$ is obtainable from $c$ by recoloring at most $k$ vertices of $G$. Recently, Junosza-Szaniawski, Liedloff, and Rz{\k{a}}{\.z}ewski [SOFSEM 2015] asked whether the problem has a polynomial kernel parameterized by the number of recolorings $k$. In a full version of the manuscript, the authors together with Garnero and Montealegre, answered the question in the negative: for every $r \geq 3$, the problem \probrFix does not admit a polynomial kernel unless $\NP \subseteq \coNP / \poly$. Independently of their work, we give an alternative proof of the theorem. Furthermore, we study the complexity of \probrFixSwap, where the only difference from \probrFix is that instead of $k$ recolorings we have a budget of $k$ color swaps. We show that for every $r \geq 3$, the problem \probrFixSwap is $\W[1]$-hard whereas \probrFix is known to be FPT. Moreover, when $r$ is part of the input, we observe both \probFix and \probFixSwap are $\W[1]$-hard parameterized by treewidth. We also study promise variants of the problems, where we are guaranteed that a proper $r$-coloring $c'$ is indeed obtainable from $c$ by some finite number of swaps. For instance, we prove that for $r=3$, the problems \probrFixPromise and \probrFixSwapPromise are $\NP$-hard for planar graphs. As a consequence of our reduction, the problems cannot be solved in $2^{o(\sqrt{n})}$ time unless the Exponential Time Hypothesis (ETH) fails., Comment: 14 pages, 3 figures

The $n$-hypercube, denoted by $Q_n$, has a vertex for each bit string of length $n$ with two vertices adjacent whenever their Hamming distance is one. The minimum number of colors needed to color $Q_n$ such that no two vertices at a distance at most $k$ receive the same color is denoted by $\chi_{\bar{k}}(n)$. Equivalently, $\chi_{\bar{k}}(n)$ denotes the minimum number of binary codes with minimum distance at least $k+1$ required to partition the $n$-dimensional Hamming space. Using a computer search, we improve upon the known upper bound for $n=9$ by showing that $13 \leq \chi_{\bar{2}}(9) \leq 14$., Comment: 3 pages