Search

The traveling salesman problem (TSP) is one of the classic research topics in the field of operations research, graph theory and computer science. In this paper, we propose a generalized model of traveling salesman problem, denoted by generalized traveling salesman path problem. Let G = (V , E , c) be a weighted complete graph, in which c is a nonnegative metric cost function on edge set E , i.e., c : E → R +. The traveling salesman path problem aims to find a Hamiltonian path in G with minimum cost. Compared to the traveling salesman path problem, we are given extra vertex subset V ′ and edge subset E ′ in the problem proposed in this paper; its goal is to construct a path which traverses all the edges in E ′ while only needs to visit each vertex in V ′ exactly once. Based on integer programming, we give a mathematical model of the problem, and design a 1 + 5 2 -approximation algorithm for the problem by combining linear programming rounding strategy and a special graph structure. • In this paper, we consider a generalized model of traveling salesman problem. • Based on integer programming, we give a mathematical model of the problem. • Combining linear programming rounding strategy and a special graph structure, we propose a 1 + 5 2 -approximation algorithm. [ABSTRACT FROM AUTHOR]

Dense subgraph discovery is an important graph-mining primitive with a variety of real-world applications. One of the most well-studied optimization problems for dense subgraph discovery is the densest subgraph problem, where given an edge-weighted undirected graph G = (V , E , w) , we are asked to find S ⊆ V that maximizes the density d (S) , i.e., half the weighted average degree of the induced subgraph G [ S ]. This problem can be solved exactly in polynomial time and well-approximately in almost linear time. However, a densest subgraph has a structural drawback, namely, the subgraph may not be robust to vertex/edge failure. Indeed, a densest subgraph may not be well-connected, which implies that the subgraph may be disconnected by removing only a few vertices/edges within it. In this paper, we provide an algorithmic framework to find a dense subgraph that is well-connected in terms of vertex/edge connectivity. Specifically, we introduce the following problems: given a graph G = (V , E , w) and a positive integer/real k , we are asked to find S ⊆ V that maximizes the density d (S) under the constraint that G [ S ] is k -vertex/edge-connected. For both problems, we propose polynomial-time (bicriteria and ordinary) approximation algorithms, using classic Mader's theorem in graph theory and its extensions. [ABSTRACT FROM AUTHOR]

In this article, we study a variant of the minimum dominating set problem known as the minimum liar's dominating set (MLDS) problem. We prove that the MLDS problem is NP-hard in unit disk graphs. We point out that the approximation guarantee of 11 2 for the approximation algorithm for unit disk graphs proposed by Banerjee and Bhore (2019) [11] is not correct and we propose a simple O (n + m) time 7.31-factor approximation algorithm, where n and m are the number of vertices and edges, respectively, in the given unit disk graph. Finally, we prove that the MLDS problem admits a polynomial-time approximation scheme. [ABSTRACT FROM AUTHOR]

Abstract We give an algorithm that for an input planar graph G of n vertices and an integer k , in min { O (n log 3 n) , O (n k 2) } time either constructs a branch-decomposition of G of width at most (2 + δ) k , where δ > 0 is a constant, or a (k + 1) × k + 1 2 cylinder minor of G implying bw (G) > k , where bw (G) is the branchwidth of G. This is the first O ̃ (n) time constant-factor approximation for branchwidth/treewidth and largest grid/cylinder minors of planar graphs and improves the previous min { O (n 1 + ϵ) , O (n k 2) } (where ϵ > 0 is a constant) time constant-factor approximations. For a planar graph G and k = bw (G) , a branch-decomposition of width at most (2 + δ) k and a g × g 2 cylinder/grid minor with g = k β , where β > 2 is a constant, can be computed by our algorithm in min { O (n log 3 n log k) , O (n k 2 log k) } time. [ABSTRACT FROM AUTHOR]

Abstract We develop efficient parameterized, with additive error, approximation algorithms for the (Connected) r -Domination problem and the (Connected) p -Center problem for unweighted and undirected graphs. Given a graph G , we show how to construct a (connected) (r + O (μ)) -dominating set D with | D | ≤ | D ⁎ | efficiently. Here, D ⁎ is a minimum (connected) r -dominating set of G and μ is our graph parameter, which is the tree-breadth or the cluster diameter in a layering partition of G. Additionally, we show that a + O (μ) -approximation for the (Connected) p -Center problem on G can be computed in polynomial time. Our interest in these parameters stems from the fact that in many real-world networks, including Internet application networks, web networks, collaboration networks, social networks, biological networks, and others, and in many structured classes of graphs these parameters are small constants. [ABSTRACT FROM AUTHOR]

Abstract The star chromatic index χ st ′ (G) of a graph G is the smallest integer k for which G has a proper k -edge-coloring without bichromatic paths or cycles of length four. In this paper, we prove that (1) if G is a graph with Δ = 4 , then χ st ′ (G) ≤ 14 ; and (2) if G is a bipartite graph with Δ = 4 , then χ st ′ (G) ≤ 13. [ABSTRACT FROM AUTHOR]

In this paper, we consider a variation of the classic dominating set problem - The Two Disjoint Connected Dominating Sets (DCDS) problem, which finds applications in many real domains including wireless sensor networks. In the DCDS problem, we are given a graph G = ( V , E ) and required to find a new edge set E ′ with minimum cardinality such that the resulting new graph after the adding of E ′ has a pair of disjoint connected dominating sets. This problem is very hard in general graphs, and we show that it is NP -hard even restricted to trees. We also present a polynomial time approximation algorithm for the DCDS problem for arbitrary trees with performance ratio 3 2 asymptotically. [ABSTRACT FROM AUTHOR]

Abstract In this paper, we study the conflict-free coloring of graphs induced by neighborhoods. A coloring of a graph is conflict-free if every vertex has a uniquely colored vertex in its neighborhood. The conflict-free coloring problem is to color the vertices of a graph using the minimum number of colors such that the coloring is conflict-free. We consider both closed neighborhoods, where the neighborhood of a vertex includes itself, and open neighborhoods, where a vertex does not include in its neighborhood. We study the parameterized complexity of conflict-free closed neighborhood coloring and conflict-free open neighborhood coloring problems. We show that both problems are fixed-parameter tractable (FPT) when parameterized by the cluster vertex deletion number of the input graph. This generalizes the result of Gargano and Rescigno [Theoretical Computer Science, 2015] that conflict-free coloring is FPT parameterized by the vertex cover number. Also, we show that both problems admit an additive constant approximation algorithm when parameterized by the distance to threshold graphs. We also study the complexity of the problem on special graph classes. For split graphs, we give a polynomial time algorithm for closed neighborhood conflict-free coloring problem, whereas we show that open neighborhood conflict-free coloring is NP -complete. For cographs, we show that conflict-free closed neighborhood coloring can be solved in polynomial time and conflict-free open neighborhood coloring need at most three colors. We show that interval graphs can be conflict-free colored using at most four colors. [ABSTRACT FROM AUTHOR]

An induced matching is a matching where no two edges are connected by a third edge. Finding a maximum induced matching on graphs with maximum degree Δ , for Δ ≥ 3 , is known to be NP-complete. In this work we consider the weighted version of this problem, which has not been extensively studied in the literature. We devise an almost tight fractional local ratio algorithm with approximation ratio Δ , which proves to be effective also in practice. Furthermore, we show that a simple greedy algorithm applied to K 1 , k -free graphs yields an approximation ratio 2 k − 3 . We explore the behavior of this algorithm on subclasses of chair-free graphs and we show that it yields an approximation ratio k when restricted to ( K 1 , k , chair ) -free graphs. [ABSTRACT FROM AUTHOR]

In the Canadian traveler problem, we are given an edge weighted graph with two specified vertices s and t and a probability distribution over the edges that tells which edges are present. The goal is to minimize the expected length of a walk from s to t . However, we only get to know whether an edge is active the moment we visit one of its incident vertices. Under the assumption that the edges are active independently, we show NP-hardness on series-parallel graphs and give results on the adaptivity gap. We further show that this problem is NP-hard on disjoint-path graphs and cactus graphs when the distribution is given by a list of scenarios. We also consider a special case called the multi-target graph search problem. In this problem, we are given a probability distribution over subsets of vertices. The distribution specifies which set of vertices has targets. The goal is to minimize the expected length of the walk until finding a target. For the independent decision model, we show that the problem is NP-hard on trees and give a ( 3.59 + ϵ ) -approximation for trees and a ( 14.4 + ϵ ) -approximation for general metrics. For the scenario model, we show NP-hardness on star graphs. [ABSTRACT FROM AUTHOR]

We investigate two NP -complete vertex partition problems on edge-weighted complete graphs with 3 k vertices. The first problem asks to partition the graph into k vertex disjoint paths of length 2 (referred to as 2- paths ) such that the total weight of the paths is maximized. We present a cubic time approximation algorithm that computes a 2-path partition whose total weight is at least . 5833 of the weight of an optimal partition, improving upon the ( . 5265 − ϵ ) -approximation algorithm of Tanahashi and Chen (2010). Restricting the input to graphs with edge weights in { 0 , 1 } , we present a . 75 approximation algorithm improving upon the . 55 -approximation algorithm of Hassin and Schneider (2013). Combining this algorithm with a previously known approximation algorithm for the 3-Set Packing problem, we obtain a . 6 -approximation algorithm for the problem of partitioning a { 0 , 1 } -edge-weighted graph into k vertex disjoint triangles of maximum total weight. The best known approximation algorithm for general weights is due to Chen and Tanahashi (2009) and achieves an approximation ratio of . 5257 . [ABSTRACT FROM AUTHOR]

The minimum vertex cover problem (MVCP) and minimum weighted vertex cover problem (MWVCP) have been used in a variety of applications. This paper focuses on a view of test-cost-sensitive rough set for MWVCP. We first provide a method to convert a minimum weight vertex cover of a graph into a minimal test cost attribute reduct of a test-cost-sensitive decision table. Then, an induced test-cost-sensitive decision table from an undirected weighted graph is established. On the foundation of the induced decision table, an improved heuristic algorithm for finding minimum weight vertex covers is proposed, it can avoid a mass of redundant computation. Furthermore, to improve efficiency, a quantum-behaved particle swarm optimization with immune mechanism is presented, which can avoid the phenomenon of premature, improve the global searching ability, and enhance the convergence speed. The results of the experiment show the advantages and limitations of the proposed algorithms compared with state-of-the-art algorithms. [ABSTRACT FROM AUTHOR]

Given a set S of n disjoint line segments in R 2 , the visibility counting problem (VCP) is to preprocess S such that the number of segments in S visible from any query point p can be computed quickly. This problem can be solved trivially in O ( log ⁡ n ) query time using O ( n 4 log ⁡ n ) preprocessing time and O ( n 4 ) space. Gudmundsson and Morin (2010) [10] proposed a 2-approximation algorithm for this problem with a tradeoff between the space and the query time. For any constant 0 ≤ α ≤ 1 , their algorithm answers any query in O ϵ ( m ( 1 − α ) / 2 ) time with O ϵ ( m 1 + α ) of preprocessing time and space, where ϵ > 0 is a constant that can be made arbitrarily small and O ϵ ( f ( n ) ) = O ( f ( n ) n ϵ ) and m = O ( n 2 ) is a number that depends on the configuration of the segments. In this paper, we propose two randomized approximation algorithms for VCP. The first algorithm depends on two constants 0 ≤ β ≤ 2 3 and 0 < δ ≤ 1 , and the expected preprocessing time, the expected space, and the expected query time are O ( m 2 − 3 β / 2 log ⁡ m ) , O ( m 2 − 3 β / 2 ) , and O ( 1 δ 2 m β / 2 log ⁡ m ) , respectively. The algorithm, in the preprocessing phase, selects a sequence of random samples, whose size and number depend on the tradeoff parameters. When a query point p is given by an adversary unaware of the random sample of our algorithm, it computes the number of visible segments from p , denoted by m p , exactly, if m p ≤ 3 δ 2 m β / 2 log ⁡ ( 2 m ) . Otherwise, it computes an approximated value, m p ′ , such that with the probability of at least 1 − 1 m , we have ( 1 − δ ) m p ≤ m p ′ ≤ ( 2 + 2 δ ) m p . The preprocessing time and space of the second algorithm are O ( n 2 log ⁡ n ) and O ( n 2 ) , respectively. This algorithm computes the exact value of m p if m p ≤ 1 δ 2 n log ⁡ n , otherwise it returns an approximated value m p ″ in expected O ( 1 δ 2 n log ⁡ n ) time, such that with the probability at least 1 − 1 log ⁡ n , we have ( 1 − 3 δ ) m p ≤ m p ″ ≤ ( 1.5 + 3 δ ) m p . [ABSTRACT FROM AUTHOR]

We address the problem of computing distances between permutations that take into account similarities between elements of the ground set dictated by a graph. The problem may be summarized as follows: Given two permutations and a positive cost function on transpositions that depends on the similarity of the elements involved, find a smallest cost sequence of transpositions that converts one permutation into another. Our focus is on costs that may be described via special metric-tree structures. The presented results include a linear-time algorithm for finding a minimum cost decomposition for simple cycles and a linear-time 4 ∕ 3 -approximation algorithm for permutations that contain multiple cycles. The proposed methods rely on investigating a newly introduced balancing property of cycles embedded in trees, cycle-merging methods, and shortest path optimization techniques. [ABSTRACT FROM AUTHOR]

Graph burning is a model for the spread of social contagion. The burning number is a graph parameter associated with graph burning that measures the speed of the spread of contagion in a graph; the lower the burning number, the faster the contagion spreads. We prove that the corresponding graph decision problem is NP -complete when restricted to acyclic graphs with maximum degree three, spider graphs and path-forests. We provide polynomial time algorithms for finding the burning number of spider graphs and path-forests if the number of arms and components, respectively, are fixed. Finally, we describe a polynomial time approximation algorithm with approximation factor 3 for general graphs. [ABSTRACT FROM AUTHOR]

Graph Distance Contest (GDC) was organized in the context of ICPR 2016. Its main challenge was to inspect and report performances and effectiveness of exact and approximate graph edit distance methods by comparison with a ground truth. This paper presents the context of this competition, the metrics and datasets used for evaluation, and the results obtained by the eight submitted methods. Results are analyzed and discussed in terms of computation time and accuracy. We also highlight the future challenges in graph edit distance regarding both future methods and evaluation metrics. The contest was supported by the Technical Committee on Graph-Based Representations in Pattern Recognition (TC-15) of the International Association of Pattern Recognition (IAPR). [ABSTRACT FROM AUTHOR]

In this paper we consider the 2-dominating set problem (2MDS). We look for a smallest subset of vertices D ⊆ V with the property that every vertex in V ∖ D is adjacent to at least 2 vertices of D . We are interested in the distributed complexity of this problem in the local model, where the nodes have no identifiers but there is a port ordering available. We propose a distributed local (constant time) algorithm yielding a 6-approximation in the class of planar graphs. Earlier result shows that in this case, for any ϵ > 0 , there is no deterministic distributed local/constant-round algorithm providing a ( 5 − ϵ ) -approximation of the 2MDS. [ABSTRACT FROM AUTHOR]

Given a graph with labels defined on edges and a source-sink pair ( s , t ) , the Label s - t Cut problem asks for a minimum number of labels such that the removal of edges with these labels disconnects s and t . Similarly, the Global Label Cut problem asks for a minimum number of labels to disconnect G itself. For these two problems, we identify two useful parameters, i.e., l max , the maximum length of any s - t path (only applies to Label s - t Cut ), and f max , the maximum number of appearances of any label in the graph (applies to the two problems). We show that l max = 2 and f max = 2 are two complexity thresholds for Label s - t Cut . Furthermore, we give (i) an O ⁎ ( c k ) time parameterized algorithm for Label s - t Cut with l max bounded from above, where parameter k is the number of labels in a solution, and c is a constant with l max − 1 < c < l max , (ii) a combinatorial l max -approximation algorithm for Label s - t Cut , and (iii) a polynomial time exact algorithm for Global Label Cut with f max bounded from above. [ABSTRACT FROM AUTHOR]

We study the Max k -colored clustering problem, where given an edge-colored graph with k colors, we seek to color the vertices of the graph so as to find a clustering of the vertices maximizing the number (or the weight) of matched edges, i.e. the edges having the same color as their extremities. We show that the cardinality problem is NP-hard even for edge-colored bipartite graphs with a chromatic degree equal to two and k ≥ 3 . Our main result is a constant approximation algorithm for the weighted version of the Max k -colored clustering problem which is based on a rounding of a natural linear programming relaxation. For graphs with chromatic degree equal to two we improve this ratio by exploiting the relation of our problem with the Max 2- and problem. We also present a reduction to the maximum-weight independent set (IS) problem in bipartite graphs which leads to a polynomial time algorithm for the case of two colors. [ABSTRACT FROM AUTHOR]

As a fundamental problem in graph theory, the minimum cut (min-cut) problem and solutions have many applications in networking related researches. A new approximation algorithm for the problem in undirected graph is proposed that can accelerate existing method by up to 6 orders of magnitude, while the preprocessing overhead is just a limited number of depth-first traversing. In the algorithm, after checking and recording the cut values of various types of traversal trees, the good upper bound on the min-cut value between any node pair can be approximated using the minimal cut value of all related traversal trees, and the upper bound is very likely to be the exact value. The independence between different traversal passes makes it ready for further acceleration using parallelization. The traversal tree-cut mapping algorithm with local pruning (TCLP) is compared with other methods using random, scale-free and real-world graphs, the results show that even the serial implementation of TCLP can achieve far larger acceleration ratio than existing methods while obtaining exact min-cut value of 99.9% node pairs. The results also indicate that TCLP is general enough to not rely on any special local graph structure and is seldom affected by graph types, thus can be used as an effective supplement to the existing methods. • A new and ready-for-parallelization algorithm is proposed for maximum flow calculation. • It is the first algorithm that utilizes the mapping from the set of all pruned traversal trees to the set of all cuts. • The algorithm has low preprocessing overhead, high acceleration ratio and precision. • The preprocessing overhead can be as low as just tens of depth-first traversals to provide the precision of 99.9%. • The average acceleration ratio to the fastest max-flow implementation can be more than one million. [ABSTRACT FROM AUTHOR]

A standard way to approximate the distance between two vertices p and q in a graph is to compute a shortest path from p to q that goes through one of k sources, which are well-chosen vertices. Precomputing the distance between each of the k sources to all vertices yields an efficient computation of approximate distances between any two vertices. One standard method for choosing k sources is the so-called Farthest Point Sampling (FPS), which starts with a random vertex as the first source, and iteratively selects the farthest vertex from the already selected sources. In this paper, we analyze the stretch factor F FPS of approximate geodesics computed using FPS, which is the maximum, over all pairs of distinct vertices, of their approximated distance over their geodesic distance in the graph. We show that F FPS can be bounded in terms of the minimal value F ⁎ of the stretch factor obtained using an optimal placement of k sources as F FPS ⩽ 2 r e 2 F ⁎ + 2 r e 2 + 8 r e + 1 , where r e is the length ratio of longest edge over the shortest edge in the graph. We further show that the factor r e is not an artefact of the analysis by providing a class of graphs for which F FPS ⩾ 1 2 r e F ⁎ . [ABSTRACT FROM AUTHOR]

We consider the problem of partitioning interval graphs into cliques of bounded size. Each interval has a weight, and the weight of a clique is the maximum weight of any interval in the clique. The goal is then to find such a partition of minimum total weight. This graph problem can also be interpreted as a batch scheduling problem. Solving a long-standing open question, we show NP-hardness, even if the bound on the clique sizes is constant. Moreover, we give a PTAS for this case. [ABSTRACT FROM AUTHOR]

With the integration of advanced computing and communication technologies, the Smart Grid is expected to greatly enhance efficiency and reliability of future power systems with renewable energy resources, as well as distributed intelligence and demand response. Along with the salient features of the Smart Grid, cyber security emerges to be a critical issue because millions of electronic devices are inter-connected via communication networks throughout critical power facilities, which has an immediate impact on reliability of such a widespread infrastructure. In this paper, we discuss the packet based attacks and study the Optimal Inspection Points (OIP) problem, which asks us to find a subset of nodes in a given network to perform the Deep Packet Inspection so as to maximize the number of scanned packets while satisfying the delay constraints. This problem finds many applications for malicious attack detection, especially for those cases where each single packet or the network traffic is required to be inspected. Accordingly, we prove OIP is NP-complete and provide an FPTAS in the case of single path routing. For the multiple path routings, we design an FPTAS when the routing graph takes a form of series-parallel graphs, which is commonly used to model electric networks. We also discuss the multi-scan scenario and design PIVOT algorithm to tackle the problem and evaluate the algorithms through experiments. [ABSTRACT FROM AUTHOR]

For two positive integers m , k and a connected graph G = ( V , E ) with a nonnegative vertex weight function w , the balanced m -connected k -partition problem, denoted as BC m P k , is to find a partition of V into k disjoint nonempty vertex subsets ( V 1 , V 2 , … , V k ) such that each G [ V i ] (the subgraph of G induced by V i ) is m -connected, and min 1 ≤ i ≤ k ⁡ { w ( V i ) } is maximized. The optimal value of BC m P k on graph G is denoted as β m ⁎ ( G , k ) , that is, β m ⁎ ( G , k ) = max ⁡ min 1 ≤ i ≤ k ⁡ { w ( V i ) } , where the maximum is taken over all m -connected k -partition of G . In this paper, we study the BC 2 P k problem on interval graphs, and obtain the following results. (1) For k = 2 , a 4/3-approximation algorithm is given for BC 2 P 2 on 4-connected interval graphs. (2) In the case that there exists a vertex v with weight at least W / k , where W is the total weight of the graph, we prove that the BC 2 P k problem on a 2 k -connected interval graph G can be reduced to the BC 2 P k − 1 problem on the ( 2 k − 1 ) -connected interval graph G − v . In the case that every vertex has weight at most W / k , we prove a lower bound β 2 ⁎ ( G , k ) ≥ W / ( 2 k − 1 ) for 2 k -connected interval graph G . (3) Assuming that weight w is integral, a pseudo-polynomial time algorithm is obtained. Combining this pseudo-polynomial time algorithm with the above lower bound, a fully polynomial time approximation scheme (FPTAS) is obtained for the BC 2 P k problem on 2 k -connected interval graphs. [ABSTRACT FROM AUTHOR]

We address the max min vertex cover problem, which is the maximization version of the well studied min independent dominating set problem, known to be NP -hard and highly inapproximable in polynomial time. We present tight approximation results for this problem on general graphs, namely a polynomial approximation algorithm which guarantees an n − 1 2 approximation ratio, while showing that unless P = NP , the problem is inapproximable within ratio n ε − ( 1 2 ) for any strictly positive ε . We also analyze the problem on various restricted classes of graphs, on which we show polynomiality or constant-approximability of the problem. Finally, we show that the problem is fixed-parameter tractable with respect to the size of an optimal solution, to treewidth and to the size of a maximum matching. [ABSTRACT FROM AUTHOR]

Sorting genomes by translocations is a classic combinatorial problem in genome rearrangements. The translocation distance for signed genomes can be computed exactly in polynomial time, but for unsigned genomes the problem becomes NP-hard and the current best approximation ratio is 1.5 + ε . In this paper, we investigate the problem of sorting unsigned genomes by translocations. Firstly, we propose a tighter lower bound of the optimal solution by analyzing some special sub-permutations; then, by exploiting the two well-known algorithms for approximating the maximum independent set on graphs with a bounded degree and for set packing with sets of bounded size, we devise a new polynomial-time approximation algorithm, improving the approximation ratio to 1.408 + ε , where ε = O ( 1 / log ⁡ n ) . [ABSTRACT FROM AUTHOR]

A bottleneck plane perfect matching of a set of n points in R 2 is defined to be a perfect non-crossing matching that minimizes the length of the longest edge; the length of this longest edge is known as bottleneck . The problem of computing a bottleneck plane perfect matching has been proved to be NP-hard. We present an algorithm that computes a bottleneck plane matching of size at least n 5 in O ( n log 2 ⁡ n ) -time. Then we extend our idea toward an O ( n log ⁡ n ) -time approximation algorithm which computes a plane matching of size at least 2 n 5 whose edges have length at most 2 + 3 times the bottleneck. [ABSTRACT FROM AUTHOR]

We explore in this paper some complexity issues inspired by the contig scaffolding problem in bioinformatics. We focus on the following problem: given an undirected graph with no loop, and a perfect matching on this graph, find a set of cycles and paths covering every vertex of the graph, with edges alternatively in the matching and outside the matching, and satisfying a given constraint on the numbers of cycles and paths. We show that this problem is NP -complete, even in planar bipartite graphs. Moreover, we show that there is no subexponential-time algorithm for several related problems unless the Exponential-Time Hypothesis fails. Lastly, we also design two polynomial-time approximation algorithms for complete graphs. [ABSTRACT FROM AUTHOR]

We investigate the algorithmic problems of the homophyly phenomenon in networks. Given an undirected graph G = ( V , E ) and a vertex coloring c : V → { 1 , 2 , ⋯ , k } of G , we say that a vertex v ∈ V is happy if v shares the same color with all its neighbors, and unhappy , otherwise, and that an edge e ∈ E is happy , if its two endpoints have the same color, and unhappy , otherwise. Supposing c is a partial vertex coloring of G , we define the Maximum Happy Vertices problem (MHV, for short) as to color all the remaining vertices such that the number of happy vertices is maximized, and the Maximum Happy Edges problem (MHE, for short) as to color all the remaining vertices such that the number of happy edges is maximized. Let k be the number of colors allowed in the problems. We show that both MHV and MHE can be solved in polynomial time if k = 2 , and that both MHV and MHE are NP-hard if k ≥ 3 . We devise a max ⁡ { 1 / k , Ω ( Δ − 3 ) } -approximation algorithm for the MHV problem, where Δ is the maximum degree of vertices in the input graph, and a 1/2-approximation algorithm for the MHE problem. This is the first theoretical progress of these two natural and fundamental new problems. [ABSTRACT FROM AUTHOR]

Graph spanners are sparse subgraphs that preserve the distances of the original graph up to some approximation ratio (the spanner's stretch ). A number of algorithms are known for constructing sparse spanners with small multiplicative or additive stretch. Recently, algorithms were introduced for constructing fault-tolerant multiplicative spanners of general graphs. This paper addresses the analogous problem of constructing fault tolerant additive and ( μ , α ) -spanners for general graphs, and presents a number of (deterministic and randomized) construction algorithms for such spanners. [ABSTRACT FROM AUTHOR]

We consider a variety of vehicle routing problems. The input consists of an undirected graph and edge lengths. Customers located at the nodes have to be visited by a set of vehicles. Two important parameters are k the number of vehicles, and the longest distance traveled by a vehicle denoted by λ . Here, we consider k to be a given bound on the maximum number of vehicles, and thus the decision maker cannot increase its value. Therefore, the goal will be to minimize λ . We study different variations of this problem, where for instance instead of servicing the customers using paths, we can serve them using spanning trees or cycles. For all these variations, we present new approximation algorithms with FPT time (where k is the parameter) which improve the known approximation guarantees for these problems. [ABSTRACT FROM AUTHOR]

Graph edit distance is a powerful and flexible method for error-tolerant graph matching. Yet it can only be calculated for small graphs in practice due to its exponential time complexity when considering unconstrained graphs. In this paper we propose a quadratic time approximation of graph edit distance based on Hausdorff matching. In a series of experiments we analyze the performance of the proposed Hausdorff edit distance in the context of graph classification and compare it with a cubic time algorithm based on the assignment problem. Investigated applications include nearest neighbor classification of graphs representing letter drawings, fingerprints, and molecular compounds as well as hidden Markov model classification of vector space embedded graphs representing handwriting. In many cases, a substantial speedup is achieved with only a minor loss in accuracy or, in one case, even with a gain in accuracy. Overall, the proposed Hausdorff edit distance shows a promising potential in terms of flexibility, efficiency, and accuracy. [ABSTRACT FROM AUTHOR]

Several problems that are NP -hard on general graphs are efficiently solvable on graphs with bounded treewidth. Efforts have been made to generalize treewidth and the related notion of pathwidth to digraphs. Directed treewidth, DAG-width and Kelly-width are some such notions which generalize treewidth, whereas directed pathwidth generalizes pathwidth. Each of these digraph width measures have an associated decomposition structure. In this paper, we present approximation algorithms for all these digraph width parameters. In particular, we give an O ( log ⁡ n ) -approximation algorithm for directed treewidth, and an O ( log 3 / 2 ⁡ n ) -approximation algorithm for directed pathwidth, DAG-width and Kelly-width. Our algorithms construct the corresponding decompositions whose widths agree with the above mentioned approximation factors. [ABSTRACT FROM AUTHOR]

In the gathering problem, a particular node in a graph, the base station , aims at receiving messages from some nodes in the graph. At each step, a node can send one message to one of its neighbors (such an action is called a call ). However, a node cannot send and receive a message during the same step. Moreover, the communication is subject to interference constraints, more precisely, two calls interfere in a step, if one sender is at distance at most d I from the other receiver. Given a graph with a base station and a set of nodes having some messages, the goal of the gathering problem is to compute a schedule of calls for the base station to receive all messages as fast as possible, i.e., minimizing the number of steps (called makespan ). The gathering problem is equivalent to the personalized broadcasting problem where the base station has to send messages to some nodes in the graph, with same transmission constraints. In this paper, we focus on the gathering and personalized broadcasting problem in grids. Moreover, we consider the non-buffering model: when a node receives a message at some step, it must transmit it during the next step. In this setting, though the problem of determining the complexity of computing the optimal makespan in a grid is still open, we present linear (in the number of messages) algorithms that compute schedules for gathering with d I ∈ { 0 , 1 , 2 } . In particular, we present an algorithm that achieves the optimal makespan up to an additive constant 2 when d I = 0 . If no messages are “close” to the axes (the base station being the origin), our algorithms achieve the optimal makespan up to an additive constant 1 when d I = 0 , 4 when d I = 2 , and 3 when both d I = 1 and the base station is in a corner. Note that, the approximation algorithms that we present also provide approximation up to a ratio 2 for the gathering with buffering. All our results are proved in terms of personalized broadcasting. [ABSTRACT FROM AUTHOR]

Voronoi game is a geometric model of competitive facility location problem played between two players. Users are generally modeled as points uniformly distributed on a given underlying space. Each player chooses a set of points in the underlying space to place their facilities. Each user avails service from its nearest facility. Service zone of a facility consists of the set of users which are closer to it than any other facility. Payoff of each player is defined by the quantity of users served by all of its facilities. The objective of each player is to maximize their respective payoff. In this paper we consider the two player Voronoi game where the underlying space is a road network modeled by a graph. In this framework we consider the problem of finding k optimal facility locations of Player 2 given any placement of m facilities by Player 1. Our main result is a dynamic programming based polynomial time algorithm for this problem on tree network. On the other hand, we show that the problem is strongly NP -complete for graphs. This proves that finding a winning strategy of P2 is NP -complete. Consequently, we design a 1 − 1 e factor approximation algorithm, where e ≈ 2.718 . [ABSTRACT FROM AUTHOR]

We prove the first logarithmic lower bounds for the approximability of the Minimum Dominating Set problem for the case of connected ( α , β ) -power law graphs for α being a size parameter and β the power law exponent. We give also a best up to now upper approximation bound for this problem in the case of the parameters β > 2 . We develop also a new functional method for proving lower approximation bounds and display a sharp approximation phase transition area between approximability and inapproximability of the underlying problems. Our results depend on a method which could be also of independent interest. [ABSTRACT FROM AUTHOR]

The boxicity (resp. cubicity) of a graph G ( V , E ) is the minimum integer k such that G can be represented as the intersection graph of axis parallel boxes (resp. cubes) in R k . Equivalently, it is the minimum number of interval graphs (resp. unit interval graphs) on the vertex set V , such that the intersection of their edge sets is E . The problem of computing boxicity (resp. cubicity) is known to be inapproximable, even for restricted graph classes like bipartite, co-bipartite and split graphs, within an O ( n 1 − ε ) -factor for any ε > 0 in polynomial time, unless N P = Z P P . For any well known graph class of unbounded boxicity, there is no known approximation algorithm that gives n 1 − ε -factor approximation algorithm for computing boxicity in polynomial time, for any ε > 0 . In this paper, we consider the problem of approximating the boxicity (cubicity) of circular arc graphs—intersection graphs of arcs of a circle. Circular arc graphs are known to have unbounded boxicity, which could be as large as Ω ( n ) . We give a ( 2 + 1 k ) -factor ( resp. ( 2 + ⌈ log n ⌉ k ) - factor ) polynomial time approximation algorithm for computing the boxicity (resp. cubicity) of any circular arc graph, where k ≥ 1 is the value of the optimum solution. For normal circular arc (NCA) graphs, with an NCA model given, this can be improved to an additive two approximation algorithm. The time complexity of the algorithms to approximately compute the boxicity (resp. cubicity) is O ( m n + n 2 ) in both these cases, and in O ( m n + k n 2 ) = O ( n 3 ) time we also get their corresponding box (resp. cube) representations, where n is the number of vertices of the graph and m is its number of edges. Our additive two approximation algorithm directly works for any proper circular arc graph, since their NCA models can be computed in polynomial time. [ABSTRACT FROM AUTHOR]

We consider a natural generalization of the Partial Vertex Cover problem. Here an instance consists of a graph G = ( V , E ) , a cost function c : V → Z + , a partition P 1 , … , P r of the edge set E , and a parameter k i for each partition P i . The objective is to find a minimum cost set of vertices which cover at least k i edges from the partition P i . We call this the Partition-VC problem. In this paper, we give matching upper and lower bound on the approximability of this problem. Our algorithm is based on a novel LP relaxation for this problem. This LP relaxation is obtained by adding knapsack cover inequalities to a natural LP relaxation of the problem. We show that this LP has integrality gap of O ( log ⁡ r ) , where r is the number of sets in the partition of the edge set. We also extend our result to more general settings. For example we consider a problem where additionally edges have profits, and we would like to pick a minimum cost set of vertices which cover edges of total profit at least Π i for each partition P i . We call this the Knapsack Partition Vertex Cover problem. We give an O ( log ⁡ r ) approximation algorithm for this problem as well. [ABSTRACT FROM AUTHOR]

For a graph G, let Z (G,λ) be the partition function of the monomer-dimer system defined by ∑k mk (G) λk, where mk (G) is the number of matchings of size k in G. We consider graphs of bounded degree and develop a sublinear-time algorithm for estimating log Z (G, λ) at an arbitrary value λ > 0 within additive error εn with high probability. The query complexity of our algorithm does not depend on the size of G and is polynomial in 1/ε, and we also provide a lower bound quadratic in 1/ε for this problem. This is the first analysis of a sublinear-time approximation algorithm for a #P-complete problem. Our approach is based on the correlation decay of the Gibbs distribution associated with Z (G,λ). We show that our algorithm approximates the probability for a vertex to be covered by a matching, sampled according to this Gibbs distribution, in a near-optimal sublinear time. We extend our results to approximate the average size and the entropy of such a matching within an additive error with high probability, where again the query complexity is polynomial in 1/ε and the lower bound is quadratic in 1/ε. Our algorithms are simple to implement and of practical use when dealing with massive datasets. Our results extend to other systems where the correlation decay is known to hold as for the independent set problem up to the critical activity. [ABSTRACT FROM AUTHOR]

Abstract: We study vertex selection in the presence of multiple graphs associated with a vertex set V representing an online community. First, we formulate a collection of Markov chains on the graph ensemble and describe the characteristics of the associated mean hitting times on V. Then, we design a branch and bound optimisation technique for computing the subset of vertices A that exhibits the smallest hitting time cost across the multi-graph, given a constraint on the volume of A. The complexity of the branch and bound technique limits its application to medium-size graphs. Thus, we formulate a greedy optimisation method for computing a close approximation to the optimal subset at lower complexity, which can be implemented in a decentralised way, for further complexity reduction. We prove that the objective function under consideration is supermodular and monotonic, which guarantees near-optimal solutions for the greedy method. This is verified in our numerical experiments that compare its performance to that of the branch and bound technique, on smaller size graphs. The experiments also examine the hitting-time trade-off across the multi-graph that our optimisation exhibits, governed by the sampling cost factors λ j associated with each graph layer G j . Relative to conventional community graph centrality methods for vertex selection, we demonstrate a substantially lower sampling (network) cost and higher data dissemination rate, on actual Facebook and Internet topology data. The generality of our framework allows for its application to information retrieval, from a collection of items represented by a multi-graph. Here, we demonstrate higher semantic consistency over state-of-the-art single-graph methods, on the popular DBLP data set. [Copyright &y& Elsevier]

In this paper, we study collective additive tree spanners for families of graphs enjoying special Robertson--Seymour's tree-decompositions, and demonstrate interesting consequences of obtained results. We say that a graph G admits a system of μ collective additive tree r-spanners (resp., multiplicative tree t-spanners) if there is a system T(G) of at most μ spanning trees of G such that for any two vertices x,y of G a spanning tree T∈T(G) exists such that dT(x,y)≤dG(x,y)+r (resp., dT(x,y)≤t⋅dG(x,y)). When μ one gets the notion of additive tree r-spanner (resp., multiplicative tree t-spanner). It is known that if a graph G has a multiplicative tree t-spanner, then G admits a Robertson--Seymour's tree-decomposition with bags of radius at most ⌈t/2⌉ in G. We use this to demonstrate that there is a polynomial time algorithm that, given an n-vertex graph G admitting a multiplicative tree t-spanner, constructs a system of at most log2n collective additive tree O(tlogn)-spanners of G. That is, with a slight increase in the number of trees and in the stretch, one can "turn" a multiplicative tree spanner into a small set of collective additive tree spanners. We extend this result by showing that if a graph G admits a multiplicative t-spanner with tree-width k-1, then G admits a Robertson--Seymour's tree-decomposition each bag of which can be covered with at most k disks of G of radius at most ⌈t/2⌉ each. This is used to demonstrate that, for every fixed k, there is a polynomial time algorithm that, given an n-vertex graph G admitting a multiplicative t-spanner with tree-width k-1, constructs a system of at most k(1+log2n) collective additive tree O(tlogn)-spanners of G. [ABSTRACT FROM AUTHOR]

Abstract: This paper tackles the following problem: given a connected graph with a weight function on its edges and an integer , find a partition of V into k clusters such that the sum (over all pairs of clusters) of the heaviest edges between the clusters is minimized. We first prove that this problem (and even the unweighted variant) cannot be approximated within a factor of unless , and cannot admit an algorithm unless . Next, we develop several algorithms: we first present a greedy algorithm and prove that it achieves a tight approximation ratio smaller than . Concerning the unweighted version of the problem, we study how the diameter of the input graph can influence its complexity, by obtaining negative results for graphs of low diameter, positive results for graphs of high diameter, and a polynomial-time approximation algorithm with an approximation ratio smaller than and depending on the diameter. We also highlight a link between the k -sparsest subgraph problem and the unweighted version. This allows us to develop several constant ratio approximation algorithms running in exponential time for general graphs, and in polynomial time in some restricted graph classes. Finally, we discuss the exact resolution for fixed k and the connections to a graph homomorphism problem. [Copyright &y& Elsevier]

Abstract: In this paper, we consider the selective graph coloring problem. Given an integer and a graph with a partition of V, it consists in deciding whether there exists a set in G such that for all , and such that the graph induced by is k-colorable. We investigate the complexity status of this problem in various classes of graphs. [Copyright &y& Elsevier]

Abstract: In this work we study approximation algorithms for the Restricted matching problem which is defined as follows: given a graph in which each edge e has a color and a profit , we want to compute a maximum (cardinality or profit) matching in which no more than edges of color are present. This kind of problems, beside the theoretical interest on its own right, emerges in multi-fiber optical networking systems, where we interpret each unique wavelength that can travel through the fiber as a color class and we would like to establish communication between pairs of systems. We study approximation and bi-criteria algorithms for this problem which are based on linear programming techniques and, in particular, on polyhedral characterizations of the natural linear formulation of the problem. In our setting, we allow violations of the bounds and we can model our problem as a bi-criteria problem: we have two objectives that we want to optimize namely (a) to maximize the profit (maximum matching) while (b) minimizing the violation of the color bounds. We prove how we can “beat” the integrality gap of the natural linear programming formulation of the problem by allowing only a slight violation of the color bounds. In particular, our main result is constant approximation bounds for both criteria of the corresponding bi-criteria optimization problem. [Copyright &y& Elsevier]

Abstract: A unit disk graph is the intersection graph of n congruent disks in the plane. Dominating sets in unit disk graphs are widely studied due to their applicability in wireless ad-hoc networks. Because the minimum dominating set problem for unit disk graphs is NP-hard, numerous approximation algorithms have been proposed in the literature, including some PTASs. However, since the proposal of a linear-time 5-approximation algorithm in 1995, the lack of efficient algorithms attaining better approximation factors has aroused attention. We introduce an algorithm that takes the usual adjacency representation of the graph as input and outputs a 44/9-approximation. This approximation factor is also attained by a second algorithm, which takes the geometric representation of the graph as input and runs in time regardless of the number of edges. Additionally, we propose a 43/9-approximation which can be obtained in time given only the graph's adjacency representation. It is noteworthy that the dominating sets obtained by our algorithms are also independent sets. [Copyright &y& Elsevier]

Abstract: The reload cost concept refers to the cost that occurs at a vertex along a path on an edge-colored graph when it traverses an internal vertex between two edges of different colors. This cost depends only on the colors of the traversed edges. Reload costs arise in various applications such as transportation networks, energy distribution networks, and telecommunications. Previous work on reload costs focuses on two problems of finding a spanning tree with minimum cost with respect to two different cost measures. In both problems the cost is associated with a set of paths from a given vertex r to all the leaves of the constructed tree. The first cost measure is the sum of the reload costs of all paths from r to the leaves. The second cost measure is the changeover cost, in which the cost of traversing a vertex by using two specific incident edges is paid only once regardless of the number of paths traversing it. The first problem is inapproximable within any polynomial time computable function of the input size [1], and the second problem is inapproximable within for any [2]. In this paper we show that the first hardness result holds also for the second problem. Given this strong inapproximability result, we study the complexity and approximability properties of numerous special cases of this second problem. We mainly focus on bounded costs, and consider both directed and undirected graphs, bounded and unbounded number of colors, and both bounded and unbounded degree graphs. We also present polynomial time exact algorithms and an approximation algorithm for some special case. To the best of our knowledge, these are the first algorithms with a provable performance guarantee for the problem. Moreover, our approximation algorithm shows a tight bound on the approximability of the problem for a specific family of instances. [Copyright &y& Elsevier]

Abstract: Matching problems on bipartite graphs where the entities on one side may have different sizes are intimately related to scheduling problems with processing set restrictions. We survey the close relationship between these two problems, and give new approximation algorithms for the (NP-hard) variations of the problems in which the sizes of the jobs are restricted. Specifically, we give an approximation algorithm with an additive error of one when the sizes of the jobs are either 1 or 2, and generalise this to an approximation algorithm with an additive error of for the case where each job has a size taken from the set (for any constant integer ). We show that the above two problems become polynomial-time solvable if the processing sets are nested. [Copyright &y& Elsevier]

Abstract: In this paper we construct an approximation algorithm for the Minimum Vertex Cover (Min-VC) problem with an expected approximation ratio of for random power-law graphs in the model due to Aiello et al. Here is the Riemann zeta function of β. We obtain this result by combining the Nemhauser and Trotter approach for Min-VC with a new deterministic rounding procedure which achieves an approximation ratio of on a subset of low degree vertices for which the expected contribution to the cost of the associated linear program is sufficiently large. [Copyright &y& Elsevier]