Search

An exact $(k,d)$-coloring of a graph $G$ is a coloring of its vertices with $k$ colors such that each vertex $v$ is adjacent to exactly $d$ vertices having the same color as $v$. The exact $d$-defective chromatic number, denoted $\chi_d^=(G)$, is the minimum $k$ such that there exists an exact $(k,d)$-coloring of $G$. In an exact $(k,d)$-coloring, which for $d=0$ corresponds to a proper coloring, each color class induces a $d$-regular subgraph. We give basic properties for the parameter and determine its exact value for cycles, trees, and complete graphs. In addition, we establish bounds on $\chi_d^=(G)$ for all relevant values of $d$ when $G$ is planar, chordal, or has bounded treewidth. We also give polynomial-time algorithms for finding certain types of exact $(k,d)$-colorings in cactus graphs and block graphs. Our main result is on the computational complexity of $d$-EXACT DEFECTIVE $k$-COLORING in which we are given a graph $G$ and asked to decide whether $\chi_d^=(G) \leq k$. Specifically, we prove that the problem is NP-complete for all $d \geq 1$ and $k \geq 2$., Comment: 20 pages, 2 figures

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)

A path in an edge-colored graph is rainbow if no two edges of it are colored the same, and the graph is rainbow-connected if there is a rainbow path between each pair of its vertices. The minimum number of colors needed to rainbow-connect a graph $G$ is the rainbow connection number of $G$, denoted by $\text{rc}(G)$. A simple way to rainbow-connect a graph $G$ is to color the edges of a spanning tree with distinct colors and then re-use any of these colors to color the remaining edges of $G$. This proves that $\text{rc}(G) \le |V(G)|-1$. We ask whether there is a stronger connection between tree-like structures and rainbow coloring than that is implied by the above trivial argument. For instance, is it possible to find an upper bound of $t(G) -1$ for $\text{rc}(G)$, where $t(G)$ is the number of vertices in the largest induced tree of $G$? The answer turns out to be negative, as there are counter-examples that show that even $c\cdot t(G)$ is not an upper bound for $\text{rc}(G))$ for any given constant $c$. In this work we show that if we consider the forest number $f(G)$, the number of vertices in a maximum induced forest of $G$, instead of $t(G)$, then surprisingly we do get an upper bound. More specifically, we prove that $\text{rc}(G) \leq f(G) + 2$. Our result indicates a stronger connection between rainbow connection and tree-like structures than that was suggested by the simple spanning tree based upper bound.

Increasingly, critical decisions in public policy, governance, and business strategy rely on a deeper understanding of the needs and opinions of constituent members (e.g. citizens, shareholders). While it has become easier to collect a large number of opinions on a topic, there is a necessity for automated tools to help navigate the space of opinions. In such contexts understanding and quantifying the similarity between opinions is key. We find that measures based solely on text similarity or on overall sentiment often fail to effectively capture the distance between opinions. Thus, we propose a new distance measure for capturing the similarity between opinions that leverages the nuanced observation -- similar opinions express similar sentiment polarity on specific relevant entities-of-interest. Specifically, in an unsupervised setting, our distance measure achieves significantly better Adjusted Rand Index scores (up to 56x) and Silhouette coefficients (up to 21x) compared to existing approaches. Similarly, in a supervised setting, our opinion distance measure achieves considerably better accuracy (up to 20% increase) compared to extant approaches that rely on text similarity, stance similarity, and sentiment similarity, Comment: Accepted in ICWSM '20

We study a family of pattern-detection problems in vertex-colored temporal graphs. In particular, given a vertex-colored temporal graph and a multiset of colors as a query, we search for temporal paths in the graph that contain the colors specified in the query. These types of problems have several applications, for example in recommending tours for tourists or detecting abnormal behavior in a network of financial transactions. For the family of pattern-detection problems we consider, we establish complexity results and design an algebraic-algorithmic framework based on constrained multilinear sieving. We demonstrate that our solution scales to massive graphs with up to a billion edges for a multiset query with five colors and up to hundred million edges for a multiset query with ten colors, despite the problems being NP-hard. Our implementation, which is publicly available, exhibits practical edge-linear scalability and is highly optimized. For instance, in a real-world graph dataset with more than six million edges and a multiset query with ten colors, we can extract an optimum solution in less than eight minutes on a Haswell desktop with four cores., Comment: version prior to peer review

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

We propose a multi-stage learning approach for pruning the search space of maximum clique enumeration, a fundamental computationally difficult problem arising in various network analysis tasks. In each stage, our approach learns the characteristics of vertices in terms of various neighborhood features and leverage them to prune the set of vertices that are likely not contained in any maximum clique. Furthermore, we demonstrate that our approach is domain independent -- the same small set of features works well on graph instances from different domain. Compared to the state-of-the-art heuristics and preprocessing strategies, the advantages of our approach are that (i) it does not require any estimate on the maximum clique size at runtime and (ii) we demonstrate it to be effective also for dense graphs. In particular, for dense graphs, we typically prune around 30 \% of the vertices resulting in speedups of up to 53 times for state-of-the-art solvers while generally preserving the size of the maximum clique (though some maximum cliques may be lost). For large real-world sparse graphs, we routinely prune over 99 \% of the vertices resulting in several tenfold speedups at best, typically with no impact on solution quality., Comment: Appeared at the Data Science Meets Optimization Workshop (DSO) at IJCAI'19

A perfect Italian dominating function of a graph $G=(V,E)$ is a function $f : V \to \{0,1,2\}$ such that for every vertex $f(v) = 0$, it holds that $\sum_{u \in N(v)} f(u) = 2$, i.e., the weight of the labels assigned by $f$ to the neighbors of $v$ is exactly two. The weight of a perfect Italian function is the sum of the weights of the vertices. The perfect Italian domination number of $G$, denoted by $\gamma^p_I(G)$, is the minimum weight of any perfect Italian dominating function of $G$. While introducing the parameter, Haynes and Henning (Discrete Appl. Math. (2019), 164--177) also proposed the problem of determining the best possible constants $c_\mathcal{G}$ such that $\gamma^p_I(G) \leq c_\mathcal{G} \times n$ for all graphs of order $n$ when $G$ is in a particular class $\mathcal{G}$ of graphs. They proved that $c_\mathcal{G} = 1$ when $\mathcal{G}$ is the class of bipartite graphs, and raised the question for planar graphs and regular graphs. We settle their question precisely for planar graphs by proving that $c_\mathcal{G} = 1$ and for cubic graphs by proving that $c_\mathcal{G} = 2/3$. For split graphs, we also show that $c_\mathcal{G} = 1$. In addition, we characterize the graphs $G$ with $\gamma^p_I(G)$ equal to 2 and 3 and determine the exact value of the parameter for several simple structured graphs. We conclude by proving that it is NP-complete to decide whether a given bipartite planar graph admits a perfect Italian dominating function of weight $k$., Comment: To appear in Discrete Applied Mathematics

We strengthen a result by Laskar and Lyle (Discrete Appl. Math. (2009), 330-338) by proving that it is NP-complete to decide whether a bipartite planar graph can be partitioned into three independent dominating sets. In contrast, we show that this is always possible for every maximal outerplanar graph with at least three vertices. Moreover, we extend their previous result by proving that deciding whether a bipartite graph can be partitioned into $k$ independent dominating sets is NP-complete for every $k \geq 3$. We also strengthen a result by Henning et al. (Discrete Math. (2009), 6451-6458) by showing that it is NP-complete to determine if a graph has two disjoint independent dominating sets, even when the problem is restricted to triangle-free planar graphs. Finally, for every $k \geq 3$, we show that there is some constant $t$ depending only on $k$ such that deciding whether a $k$-regular graph can be partitioned into $t$ independent dominating sets is NP-complete. We conclude by deriving moderately exponential-time algorithms for the problem., Comment: To appear at the 30th International Workshop on Combinatorial Algorithms (IWOCA 2019)

We propose a simple, powerful, and flexible machine learning framework for (i) reducing the search space of computationally difficult enumeration variants of subset problems and (ii) augmenting existing state-of-the-art solvers with informative cues arising from the input distribution. We instantiate our framework for the problem of listing all maximum cliques in a graph, a central problem in network analysis, data mining, and computational biology. We demonstrate the practicality of our approach on real-world networks with millions of vertices and edges by not only retaining all optimal solutions, but also aggressively pruning the input instance size resulting in several fold speedups of state-of-the-art algorithms. Finally, we explore the limits of scalability and robustness of our proposed framework, suggesting that supervised learning is viable for tackling NP-hard problems in practice., Comment: AAAI 2019

In a vertex-colored graph, an edge is happy if its endpoints have the same color. Similarly, a vertex is happy if all its incident edges are happy. Motivated by the computation of homophily in social networks, we consider the algorithmic aspects of the following Maximum Happy Edges (k-MHE) problem: given a partially k-colored graph G, find an extended full k-coloring of G maximizing the number of happy edges. When we want to maximize the number of happy vertices, the problem is known as Maximum Happy Vertices (k-MHV). We further study the complexity of the problems and their weighted variants. For instance, we prove that for every k >= 3, both problems are NP-complete for bipartite graphs and k-MHV remains hard for split graphs. In terms of exact algorithms, we show both problems can be solved in time O*(2^n), and give an even faster O*(1.89^n)-time algorithm when k = 3. From a parameterized perspective, we give a linear vertex kernel for Weighted k-MHE, where edges are weighted and the goal is to obtain happy edges of at least a specified total weight. Finally, we prove both problems are solvable in polynomial-time when the graph has bounded treewidth or bounded neighborhood diversity.

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

A path in a vertex-colored graph $G$ is \emph{vertex rainbow} if all of its internal vertices have a distinct color. The graph $G$ is said to be \emph{rainbow vertex connected} if there is a vertex rainbow path between every pair of its vertices. Similarly, the graph $G$ is \emph{strongly rainbow vertex connected} if there is a shortest path which is vertex rainbow between every pair of its vertices. We consider the complexity of deciding if a given vertex-colored graph is rainbow or strongly rainbow vertex connected. We call these problems \probRvc and \probSrvc, respectively. We prove both problems remain NP-complete on very restricted graph classes including bipartite planar graphs of maximum degree 3, interval graphs, and $k$-regular graphs for $k \geq 3$. We settle precisely the complexity of both problems from the viewpoint of two width parameters: pathwidth and tree-depth. More precisely, we show both problems remain NP-complete for bounded pathwidth graphs, while being fixed-parameter tractable parameterized by tree-depth. Moreover, we show both problems are solvable in polynomial time for block graphs, while \probSrvc is tractable for cactus graphs and split graphs., Comment: 19 pages, 8 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

The Rainbow k-Coloring problem asks whether the edges of a given graph can be colored in $k$ colors so that every pair of vertices is connected by a rainbow path, i.e., a path with all edges of different colors. Our main result states that for any $k\ge 2$, there is no algorithm for Rainbow k-Coloring running in time $2^{o(n^{3/2})}$, unless ETH fails. Motivated by this negative result we consider two parameterized variants of the problem. In Subset Rainbow k-Coloring problem, introduced by Chakraborty et al. [STACS 2009, J. Comb. Opt. 2009], we are additionally given a set $S$ of pairs of vertices and we ask if there is a coloring in which all the pairs in $S$ are connected by rainbow paths. We show that Subset Rainbow k-Coloring is FPT when parameterized by $|S|$. We also study Maximum Rainbow k-Coloring problem, where we are additionally given an integer $q$ and we ask if there is a coloring in which at least $q$ anti-edges are connected by rainbow paths. We show that the problem is FPT when parameterized by $q$ and has a kernel of size $O(q)$ for every $k\ge 2$ (thus proving that the problem is FPT), extending the result of Ananth et al. [FSTTCS 2011].

An edge-colored graph $G$ is said to be rainbow connected if between each pair of vertices there exists a path which uses each color at most once. The rainbow connection number, denoted by $rc(G)$, is the minimum number of colors needed to make $G$ rainbow connected. Along with its variants, which consider vertex colorings and/or so-called strong colorings, the rainbow connection number has been studied from both the algorithmic and graph-theoretic points of view. In this paper we present a range of new results on the computational complexity of computing the four major variants of the rainbow connection number. In particular, we prove that the \textsc{Strong Rainbow Vertex Coloring} problem is $NP$-complete even on graphs of diameter $3$. We show that when the number of colors is fixed, then all of the considered problems can be solved in linear time on graphs of bounded treewidth. Moreover, we provide a linear-time algorithm which decides whether it is possible to obtain a rainbow coloring by saving a fixed number of colors from a trivial upper bound. Finally, we give a linear-time algorithm for computing the exact rainbow connection numbers for three variants of the problem on graphs of bounded vertex cover number.

A path in an edge-colored graph $G$ is rainbow if no two edges of it are colored the same. The graph $G$ is rainbow-connected if there is a rainbow path between every pair of vertices. If there is a rainbow shortest path between every pair of vertices, the graph $G$ is strongly rainbow-connected. The minimum number of colors needed to make $G$ rainbow-connected is known as the rainbow connection number of $G$, and is denoted by $\text{rc}(G)$. Similarly, the minimum number of colors needed to make $G$ strongly rainbow-connected is known as the strong rainbow connection number of $G$, and is denoted by $\text{src}(G)$. We prove that for every $k \geq 3$, deciding whether $\text{src}(G) \leq k$ is NP-complete for split graphs, which form a subclass of chordal graphs. Furthermore, there exists no polynomial-time algorithm for approximating the strong rainbow connection number of an $n$-vertex split graph with a factor of $n^{1/2-\epsilon}$ for any $\epsilon > 0$ unless P = NP. We then turn our attention to block graphs, which also form a subclass of chordal graphs. We determine the strong rainbow connection number of block graphs, and show it can be computed in linear time. Finally, we provide a polynomial-time characterization of bridgeless block graphs with rainbow connection number at most 4., Comment: 13 pages, 3 figures

A path in an edge-colored graph is \textit{rainbow} if no two edges of it are colored the same. The graph is said to be \textit{rainbow connected} if there is a rainbow path between every pair of vertices. If there is a rainbow shortest path between every pair of vertices, the graph is \textit{strong rainbow connected}. We consider the complexity of the problem of deciding if a given edge-colored graph is rainbow or strong rainbow connected. These problems are called \textsc{Rainbow connectivity} and \textsc{Strong rainbow connectivity}, respectively. We prove both problems remain $\NP$\hyp{}complete on interval outerplanar graphs and $k$-regular graphs for $k \geq 3$. Previously, no graph class was known where the complexity of the two problems would differ. We show that for block graphs, which form a subclass of chordal graphs, \textsc{Rainbow connectivity} is $\NP$\hyp{}complete while \textsc{Strong rainbow connectivity} is in $\P$. We conclude by considering some tractable special cases, and show for instance that both problems are in $\XP$ when parameterized by tree-depth., Comment: 13 pages, 4 figures