Search

Graph coloring is one of the most famous computational problems with applications in a wide range of areas such as planning and scheduling, resource allocation, and pattern matching. So far coloring problems are mostly studied on static graphs, which often stand in contrast to practice where data is inherently dynamic. A temporal graph has an edge set that changes over time. We present a natural temporal extension of the classical graph coloring problem. Given a temporal graph and integers k and Δ, we ask for a coloring sequence with at most k colors for each vertex such that in every time window of Δ consecutive time steps, in which an edge is present, this edge is properly colored at least once. We thoroughly investigate the computational complexity of this temporal coloring problem. More specifically, we prove strong computational hardness results, complemented by efficient exact and approximation algorithms. [ABSTRACT FROM AUTHOR]

Spreading processes on graphs are a natural model for a wide variety of real-world phenomena, including information spread over social networks and biological diseases spreading over contact networks. Often, the networks over which these processes spread are dynamic in nature, and can be modelled with temporal graphs. Here, we study the problem of deleting edges from a given temporal graph in order to reduce the number of vertices (temporally) reachable from a given starting point. This could be used to control the spread of a disease, rumour, etc. in a temporal graph. In particular, our aim is to find a temporal subgraph in which a process starting at any single vertex can be transferred to only a limited number of other vertices using a temporally-feasible path. We introduce a natural edge-deletion problem for temporal graphs and provide positive and negative results on its computational complexity and approximability. [ABSTRACT FROM AUTHOR]

Modern, inherently dynamic systems are usually characterized by a network structure which is subject to discrete changes over time. Given a static underlying graph, a temporal graph can be represented via an assignment of a set of integer time-labels to every edge, indicating the discrete time steps when this edge is active. While most of the recent theoretical research on temporal graphs focused on temporal paths and other "path-related" temporal notions, only few attempts have been made to investigate "non-path" temporal problems. In this paper we introduce and study two natural temporal extensions of the classical problem VERTEX COVER. We present a thorough investigation of the computational complexity and approximability of these two temporal covering problems. We provide strong hardness results, complemented by approximation and exact algorithms. Some of our algorithms are polynomial-time, while others are asymptotically almost optimal under the Exponential Time Hypothesis (ETH) and other plausible complexity assumptions. [ABSTRACT FROM AUTHOR]

Abstract An HV-graph is a planar graph with vertex-degree at most four such that each edge is labeled either H (horizontal) or V (vertical). The HV-planarity testing problem asks whether an HV-graph admits an HV-drawing , that is, a planar drawing such that each edge with label H is drawn as a horizontal segment and each edge with label V is drawn as a vertical segment. We prove that the HV-planarity testing problem is NP-complete even for graphs with vertex-degree at most three, which answers an open question posed by both Manuch et al. [30] and Durocher et al. [17]. On the positive side, we prove that the HV-planarity testing problem can be solved in polynomial-time for series-parallel graphs. This result significantly extends a previous result by Durocher et al. about HV-planarity testing of biconnected outerplanar graphs of maximum vertex-degree three. Highlights • HV-planarity testing is NP-complete, even for graphs with vertex-degree at most 3. • Polynomial-time HV-planarity testing for 2-connected series-parallel graphs. • Polynomial-time HV-planarity testing for partial 2-trees. [ABSTRACT FROM AUTHOR]

The network verification problem is that of establishing the accuracy of a high-level description of its physical topology, by making as few measurements as possible on its nodes. This task can be formalized as an optimization problem that, given a graph and a query model specifying the information returned by a query at a node, asks for finding a minimum-size subset of nodes to be queried so as to univocally identify the graph. This problem has been studied with respect to different query models, assuming that a node had some global knowledge about the network. Here, we propose a new query model based on the local knowledge a node instead usually has. Quite naturally, we assume that a query at a given node returns the associated routing table, i.e., a set of entries which provides, for each destination node, a corresponding (set of) first-hop node(s) along an underlying shortest path. [ABSTRACT FROM AUTHOR]

Abstract: Given a graph of interactions, a module (also called a community or cluster) is a subset of nodes whose fitness is a function of the statistical significance of the pairwise interactions of nodes in the module. The topic of this paper is a model-based community finding approach, commonly referred to as modularity clustering, that was originally proposed by Newman (Leicht and Newman, 2008 [25]) and has subsequently been extremely popular in practice (e.g., see Agarwal and Kempe, 2008 [1], Guimer‘a et al., 2007 [20], Newman, 2006 [28], Newman and Girvan, 2004 [30], Ravasz et al., 2002 [32]). Various heuristic methods are currently employed for finding the optimal solution. However, as observed in Agarwal and Kempe (2008) [1], the exact computational complexity of this approach is still largely unknown. To this end, we initiate a systematic study of the computational complexity of modularity clustering. Due to the specific quadratic nature of the modularity function, it is necessary to study its value on sparse graphs and dense graphs separately. Our main results include a -inapproximability for dense graphs and a logarithmic approximation for sparse graphs. We make use of several combinatorial properties of modularity to get these results. These are the first non-trivial approximability results beyond the NP-hardness results in Brandes et al. (2007) [10]. [Copyright &y& Elsevier]

Abstract: The problem Constrained Longest Common Subsequence is a natural extension to the classical problem Longest Common Subsequence, and has important applications to bioinformatics. Given k input sequences and l constraint sequences , is the problem of finding a longest common subsequence of that is also a common supersequence of . Gotthilf et al. gave a polynomial-time algorithm that approximates within a factor , where is the length of the shortest input sequence and is the alphabet size. They asked whether there are better approximation algorithms and whether there exists a lower bound. In this paper, we answer their questions by showing that their approximation factor is in fact already very close to optimal although a small improvement is still possible: [1.] For any computable function f and any , there is no polynomial-time algorithm that approximates within a factor unless . Moreover, this holds even if the constraint sequence is unary. [2.] There is a polynomial-time randomized algorithm that approximates within a factor with high probability, where OPT is the length of the optimal solution, . For the problem over an alphabet of arbitrary size, we show that [3.] For any , there is no polynomial-time algorithm that approximates within a factor unless . [4.] There is a polynomial-time algorithm that approximates within a factor . We also present some complementary results on exact and parameterized algorithms for . [Copyright &y& Elsevier]

Abstract: We give a trichotomy theorem for the complexity of approximately counting the number of satisfying assignments of a Boolean CSP instance. Such problems are parameterised by a constraint language specifying the relations that may be used in constraints. If every relation in the constraint language is affine then the number of satisfying assignments can be exactly counted in polynomial time. Otherwise, if every relation in the constraint language is in the co-clone from Post''s lattice, then the problem of counting satisfying assignments is complete with respect to approximation-preserving reductions for the complexity class . This means that the problem of approximately counting satisfying assignments of such a CSP instance is equivalent in complexity to several other known counting problems, including the problem of approximately counting the number of independent sets in a bipartite graph. For every other fixed constraint language, the problem is complete for #P with respect to approximation-preserving reductions, meaning that there is no fully polynomial randomised approximation scheme for counting satisfying assignments unless NP=RP. [Copyright &y& Elsevier]

Abstract: We present a new hardness of approximation result for the Shortest Vector Problem in norm (denoted by ). Assuming NP ZPP, we show that for every , there is a constant such that for all integers , the problem has no polynomial time approximation algorithm with approximation ratio . [Copyright &y& Elsevier]