Search

Given an n vertex graph whose edges have colored from one of τ colors C = {ci, C2,..., cr}, we define the Hamilton cycle color profile hcp(G) to be the set of vectors (mi, m2,..., mr) ∈ [0, n}r such that there exists a Hamilton cycle that is the concatenation of τ paths Pi, P2, ∙.., Pr, where Pi contains rΠι edges of color cι. We study hcp(Gn p) when the edges are randomly colored. We discuss the profile close to the threshold for the existence of a Hamilton cycle and the threshold for when ∕icp(Gnjf>) = {(mι, m2,..., mr) ∈ [0,n]r: mi + m2 + ∙ ∙ ∙ + mr = n}. [ABSTRACT FROM AUTHOR]

For an undirected graph or multigraph G = (V, E) and a function f : V → ℤ+, an f-factor is a subgraph whose degree function is f. For integral edge weights of maximum magnitude W our algorithm finds a maximum weight f-factor in time Õ(Wf(V)ω), where f(V ) = ∑v∈V f(v) and ω is the exponent of matrix multiplication. The algorithm is randomized and has two versions. For worst-case time the algorithm is correct with high probability. For expected time the algorithm is Las Vegas. The algorithm is based on a detailed analysis of the structure of the optimum blossoms. A special case gives a representation for single-source shortest-paths in conservative undirected graphs, generalizing the standard shortest-path tree to a "tree of cycles". The representation can be constructed by a randomized algorithm with the same time bound as above, or deterministically by an algorithm for maximum weight matching, achieving time O(n(m+n log n)) or O(√n mlog (nW)). [ABSTRACT FROM AUTHOR]

An undirected graph G is d-degenerate if every subgraph of G has a vertex of degree at most d. By the classical theorem of Erdös and Gallai from 1959, every graph of degeneracy d > 1 contains a cycle of length at least d + 1. The proof of Erdös and Gallai is constructive and can be turned into a polynomial time algorithm constructing a cycle of length at least d + 1. But can we decide in polynomial time whether a graph contains a cycle of length at least d + 2? An easy reduction from Hamiltonian Cycle provides a negative answer to this question: Deciding whether a graph has a cycle of length at least d+2 is NP-complete. Surprisingly, the complexity of the problem changes drastically when the input graph is 2-connected. In this case we prove that deciding whether G contains a cycle of length at least d + k can be done in time 2O(k) .| V (G)| O(1). In other words, deciding whether a 2-connected n-vertex G contains a cycle of length at least d+log n can be done in polynomial time. Similar algorithmic results hold for long paths in graphs. We observe that deciding whether a graph has a path of length at least d+1 is NP-complete. However, we prove that if graph G is connected, then deciding whether G contains a path of length at least d+k can be done in time 2O(k) .nO(1). We complement these results by showing that the choice of degeneracy as the ``above guarantee parameterization"" is optimal in the following sense: For any ε > 0 it is NP-complete to decide whether a connected (2-connected) graph of degeneracy d has a path (cycle) of length at least (1 + ε )d. [ABSTRACT FROM AUTHOR]

Given an undirected graph and two pairs of vertices (si, ti) for i ∈{ 1, 2\} we show that there is a polynomial time Monte Carlo algorithm that finds disjoint paths of smallest total length joining si and ti for i ∈{ 1, 2\}, respectively, or concludes that there most likely are no such paths at all. Our algorithm applies to both the vertex- and edge-disjoint versions of the problem. Our algorithm is algebraic and uses permanents over the polynomial ring Z4[X] in combination with the isolation lemma of Mulmuley, Vazirani, and Vazirani to detect a solution. To this end, we develop a fast algorithm for permanents over the ring Zt[X], where t is a power of 2, by modifying Valiant's 1979 algorithm for the permanent over Zt. [ABSTRACT FROM AUTHOR]

We consider the existence of patterned Hamilton cycles in randomly colored random graphs. Given a string π over a set of colors { 1, 2, . . . , r}, we say that a Hamilton cycle is π -colored if the pattern repeats at intervals of length |π| as we go around the cycle. We prove a hitting time result for the existence of such a cycle. We also prove a hitting time result for the related notion of π -connected. [ABSTRACT FROM AUTHOR]

For any r ≥ 2 and k ≥ 3, the r-color size-Ramsey number R(G,r) of a k-uniform hypergraph G is the smallest integer m such that there exists a k-uniform hypergraph H on m edges such that any coloring of the edges of H with r colors yields a monochromatic copy of G. Let Pn,k-1 (k) denote the k-uniform tight path on n vertices. Dudek et al. [J. Graph Theory, 86 (2017), pp. 104-121] showed that the size-Ramsey number of tight paths R(Pn,k-1 (k), 2) = O(nk-1-α(logn)1+α) where α = (k-2)/2k-1 +1. In this paper, we improve their bound by showing that R(Pn,k-1(k), r) = O(rk(nlogn)k/2) for all k ≥ 3 and r ≥ 2. [ABSTRACT FROM AUTHOR]

The Chordal Vertex Deletion (CHVD) problem asks to delete a minimum number of vertices from an input graph to obtain a chordal graph. In this paper we develop a polynomial kernel for CHVD under the parameterization by the solution size. Using a new Erdõs-Pósa-type packing/covering duality for holes in nearly chordal graphs, we present a polynomial-time algorithm that reduces any instance (G, k) of CHVD to an equivalent instance with poly(k) vertices. The existence of a polynomial kernel answers an open problem posed by Marx in 2006 [D. Marx, "Chordal Deletion Is Fixed-Parameter Tractable," in Graph-Theoretic Concepts in Computer Science, Lecture Notes in Comput. Sci. 4271, Springer, 2006, pp. 37-48]. To obtain the kernelization, we develop the first poly(opt)-approximation algorithm for CHVD, which is of independent interest. In polynomial time, it either decides that G has no chordal deletion set of size k, or outputs a solution of size O(k4log² k). [ABSTRACT FROM AUTHOR]

Inside a two-dimensional region ("cake"), there are m nonoverlapping tiles of a certain kind ("toppings"). We want to expand the toppings while keeping them nonoverlapping, and possibly add some blank pieces of the same "certain kind," such that the entire cake is covered. How many blanks must we add? We study this question in several cases: (1) The cake and toppings are general polygons. (2) The cake and toppings are convex figures. (3) The cake and toppings are axis-parallel rectangles. (4) The cake is an axis-parallel rectilinear polygon and the toppings are axis-parallel rectangles. In all four cases, we provide tight bounds on the number of blanks. [ABSTRACT FROM AUTHOR]

We prove an upper bound on the Shannon capacity of a graph via a linear programming variation. We show that our bound can outperform both the Lov\'asz theta number and the Haemers minimum rank bound. As a by-product, we also obtain a new upper bound on the broadcast rate of index coding. [ABSTRACT FROM AUTHOR]

For given simple graphs G1 and G2, the size Ramsey number Ȓ(G1,G2) is the smallest positive integer m, where there exists a graph G with m edges such that in any edge coloring of G with two colors red and blue, there is either a red copy of G1 or a blue copy of G2. In 1981, Erdös and Faudree investigated the size Ramsey number Ȓ(Kn, tK2), where Kn is a complete graph on n vertices and tK2 is a matching of size t. They obtained the value of Ȓ(Kn, tK2) when n ≥ 4t-1 as well as for t = 2 and asked for the behavior of these numbers when t is much larger than n. In this regard, they posed the following interesting question: For every positive integer n, is it true that ... In this paper, we obtain the exact value of Ȓ(Kn, tK2) for every pair of positive integers n, t, and as a byproduct, we give an affirmative answer to the question of Erdös and Faudree. [ABSTRACT FROM AUTHOR]

In this paper, we study the connectivity properties of the random subgraph of the n-cube generated by the k-out model and denoted by Qn(k). Let k be an integer, 1 ≤ k ≤ n-1. We let Qn(k) be the graph that is generated by independently including for every ν ∊ V(Qn) a set of k distinct edges chosen uniformly from all the (k n) sets of distinct edges that are incident to ν. We study the connectivity properties of Qn(k) as k varies. We show that without high probability (w.h.p.), Qn(1) does not contain a giant component i.e., a component that spans Ω(2n) vertices. Thereafter, we show that such a component emerges when k=2. In addition, the giant component spans all but o(2n) vertices, and hence it is unique. We then establish the connectivity threshold found at k0=log2 n-2log2log2 n. The threshold is sharp in the sense that Qn([k0]) is disconnected but Qn([k0]+1) is connected w.h.p. Furthermore, we show that w.h.p., Qn(k) is k-connected for every k≥ [k0]+1. [ABSTRACT FROM AUTHOR]

The rotor-router model is a deterministic process analogous to a simple random walk on a graph, and the discrepancy of token configurations between the rotor-router model and its corresponding random walk has been investigated in some contexts. Motivated by general Markov chains beyond simple random walks, this paper investigates a generalized model which imitates a Markov chain (of multiple tokens) possibly containing irrational transition probabilities. We are concerned with the vertexwise discrepancy of the numbers of tokens between the generalized model and its corresponding Markov chain, and present an upper bound of the discrepancy in terms of the mixing time of the Markov chain. [ABSTRACT FROM AUTHOR]

We first consider the following problem. We are given a fixed perfect matching M of [n] and we add random edges one at a time until there is a Hamilton cycle containing M. We show that with high probability (w.h.p.) the hitting time for this event is the same as that for the first time there are no isolated vertices in the graph induced by the random edges. We then use this result for the following problem. We generate random edges and randomly color them black or white. A path/cycle is said to be zebraic if the colors alternate along the path. We show that w.h.p. the hitting time for a zebraic Hamilton cycle coincides with every vertex meeting at least one edge of each color. We then consider some related problems and (partially) extend our results to multiple colors. We also briefly consider directed versions. [ABSTRACT FROM AUTHOR]

A key result in the field of kernelization, a subfield of parameterized complexity, states that the classic Disjoint Cycle Packing problem, i.e., finding k vertex disjoint cycles in a given graph G, admits no polynomial kernel unless NP ⊆ coNP/poly. However, very little is known about this problem beyond the aforementioned kernelization lower bound (within the parameterized complexity framework). In the hope of clarifying the picture and better understanding the types of constraints that separate kernelizable from nonkernelizable variants of Disjoint Cycle Packing, we investigate two relaxations of the problem. The first variant, which we call Almost Disjoint Cycle Packing, introduces a global relaxation parameter t. That is, given a graph G and integers k and t, the goal is to find at least k distinct cycles such that every vertex of G appears in at most t of the cycles. The second variant, Pairwise Disjoint Cycle Packing, introduces a local relaxation parameter, and we seek at least k distinct cycles such that every two cycles intersect in at most t vertices. While the Pairwise Disjoint Cycle Packing problem admits a polynomial kernel for all t ≥ 1, the kernelization complexity of Almost Disjoint Cycle Packing reveals an interesting spectrum of upper and lower bounds. In particular, for t = k/c, where c could be a function of k, we obtain a kernel of size O(2c² k7+c log³ k) whenever c ∈ o(√k). Thus the kernel size varies from being subexponential when c ∈ o(√k), to quasi-polynomial when c ∈ o(logℓ k), ℓ ∈ R+, and polynomial when c ∈ O(1). We complement these results for Almost Disjoint Cycle Packing by showing that the problem does not admit a polynomial kernel whenever t ∈ O(k∈) for any 0≤∈< 1, unless NP 埦 coNP/poly. [ABSTRACT FROM AUTHOR]

For a simple (unbiased) random walk on a connected graph with n vertices, the cover time (the expected number of steps it takes to visit all vertices) is at most O(n³). We consider locally biased random walks, in which the probability of traversing an edge depends on the degrees of its endpoints. We confirm a conjecture of Abdullah, Cooper, and Draief [2015] that the min-degree local bias rule ensures a cover time of O(n²). For this we formulate and prove the following lemma about spanning trees. Let R(e) denote for edge e the minimum degree among its two endpoints. We say that a weight function W for the edges is feasible if it is nonnegative, dominated by R (for every edge W(e) ≤ R(e)), and the sum over all edges of the ratios W(e)/R(e) equals n - 1. For example, in trees W(e) = R(e), and in regular graphs the sum of edge weights is d(n - 1). We will show in a lemma that for every feasible W, the minimum weight spanning tree has total weight O(n). For regular graphs, a similar lemma was proved by Kahn et al. (1989). [ABSTRACT FROM AUTHOR]

We present an algorithm for maintaining a maximal matching in a graph under addition and deletion of edges. Our algorithm is randomized and it takes expected amortized O(log n) time for each edge update, where n is the number of vertices in the graph. Moreover, for any sequence of t edge updates, the total time taken by the algorithm is O(t log n+n log² n) with high probability. [ABSTRACT FROM AUTHOR]

Gyárfás, Győri, and Simonovits [J. Comb., 7 (2016), pp. 205{216] proved that if a 3-uniform hypergraph with n vertices has no linear cycles, then its independence number α ≥ 2n/5. The hypergraph consisting of vertex disjoint copies of a complete hypergraph K3/5 on five vertices shows that equality can hold. They asked whether this bound can be improved if we exclude K3/5 as a subhypergraph and whether such a hypergraph is 2-colorable. In this paper, we answer these questions affirmatively. Namely, we prove that if a 3-uniform linear-cycle-free hypergraph doesn't contain K3 5 as a subhypergraph, then it is 2-colorable. This result clearly implies that its independence number α ≥ [n/2]. We show that this bound is sharp. Gyárfás, Gy}ori, and Simonovits also proved that a linear-cycle-free 3-uniform hypergraph contains a vertex of strong degree at most 2. In this context, we show that a linear-cycle-free 3-uniform hypergraph has a vertex of degree at most n - 2 when n ≥ 10. [ABSTRACT FROM AUTHOR]

Consider a directed analogue of the random graph process on n vertices, where the n(n - 1) edges are ordered uniformly at random and revealed one at a time. It is known that with high probability (w.h.p.) the first digraph in this process with both in-degree and out-degree ≥ q has a q-edge-coloring with a Hamilton cycle in each color. We show that this coloring can be constructed online, where each edge must be irrevocably colored as soon as it appears. In a similar fashion, for the undirected random graph process, we present an online n-edge-coloring algorithm which yields w.h.p. q disjoint rainbow Hamilton cycles in the first graph containing q disjoint Hamilton cycles. [ABSTRACT FROM AUTHOR]

A key feature of Simonovits' proof of the classic Erdőos--Pósa theorem is a simple subgraph of the host graph, a frame, that determines the outcome of the theorem. We transfer this frame technique to A-paths. With it we deduce a simple proof of Gallai's theorem, although with a worse bound, and we verify the Erdős--Pósa property for long and for even A-paths. We also show that even A-paths do not have the edge-Erdős--Pósa property. [ABSTRACT FROM AUTHOR]

The complexity of testing whether a graph contains an induced odd cycle of length at least five is currently unknown. In this paper we show that this test can be done in polynomial time if the input graph has no induced subgraph isomorphic to the bull (a triangle with two disjoint pendant edges). [ABSTRACT FROM AUTHOR]

In this paper, we give the following result: If D is a digraph of order n, and if d+ D(u)+d D(v) n for every two distinct vertices u and v with (u; v) =2 A(D), then D has a directed 2-factor with exactly k directed cycles of length at least 3, where n 12k+3. This result is equivalent to the following result: If G is a balanced bipartite graph of order 2n with partite sets X and Y , and if dG(x) + dG(y) n + 2 for every two vertices x 2 X and y 2 Y with xy =2 E(G), then for every perfect matching M, G has a 2-factor with exactly k cycles of length at least 6 containing every edge of M, where n 12k + 3. These results are generalizations of theorems concerning Hamilton cycles due to Woodall [Proc. Lond. Math. Soc., 24 (1972), pp. 739{755] and Las Vergnas [Problemes de couplages et problemes hamiltoniens en theorie des graphes, Ph.D. thesis, University of Paris, 1972], respectively. [ABSTRACT FROM AUTHOR]

We prove an ear-decomposition theorem for 4-edge-connected graphs and use it to prove that for every 4-edge-connected graph G and every r \in V (G), there is a set of four spanning trees of G with the following property. For every vertex in G, the unique paths back to r in each tree are edge-disjoint. Our proof implies a polynomial-time algorithm for constructing the trees. [ABSTRACT FROM AUTHOR]

Let L be a set of positive integers. We call a (directed) graph G an L-cycle graph if all cycle lengths in G belong to L. Let c(L; n) be the maximum number of cycles possible in an n-vertex L-cycle graph (we use ~c(L; n) for the number of cycles in directed graphs). In the undirected case we show that for any fixed set L, we have c(L; n) = (nbk=`c), where k is the largest element of L and 2` is the smallest even element of L (if L contains only odd elements, then c(L; n) = (n) holds). We also give a characterization of L-cycle graphs when L is a single element. In the directed case we prove that for any fixed set L, we have ~c(L; n) = (1 + o(1))( n 1 k 1 ) k 1, where k is the largest element of L. We determine the exact value of ~c(fkg; n) for every k and characterize all graphs attaining this maximum. [ABSTRACT FROM AUTHOR]

In this paper we determine the chromatic number of graphs with two odd cycle lengths. Let G be a graph and L(G) be the set of all odd cycle lengths of G. We prove that (1) if L(G) = f3; 3 + 2lg, where l ≥ 2, then x(G) = maxf3; !(G)g, and (2) if L(G) = fk; k + 2lg, where k ≥ 5 and l ≥ 1, then x(G) = 3. These, together with the case L(G) = f3; 5g solved in [S.-S. Wang, SIAM J. Discrete Math., 22 (2008), pp. 1040{1072] give a complete solution to the general problem addressed in [S.-S. Wang, SIAM J. Discrete Math., 22 (2008), pp. 1040{1072; S.-M. Camacho and I. Schiermeyer, Discrete Math., 309 (2009), pp. 4916{4919; and T. Kaiser, O. Rucký, and R. Škrekovski, SIAM J. Discrete Math., 25 (2011), pp. 1069{1088]. Our results also improve a classical theorem of Gyárfás which asserts that x (G) ≤ 2jL(G)j + 2 for any graph G. [ABSTRACT FROM AUTHOR]

The cyclability of a graph is the maximum integer k for which every k vertices lie on a cycle. The algorithmic version of the problem, given a graph G and a nonnegative integer k, decide whether the cyclability of G is at least k, is NP-hard. We study the parametrized complexity of this problem. We prove that this problem, parameterized by k, is co-W[1]-hard and that it does not admit a polynomial kernel on planar graphs, unless NP ⊆ co-NP=poly. On the positive side, we give an FPT algorithm for planar graphs that runs in time 22O(k2 log k). n2. Our algorithm is based on a series of graph-theoretical results on cyclic linkages in planar graphs. [ABSTRACT FROM AUTHOR]

Let G be an n-node simple directed planar graph with nonnegative edge weights. We study the fundamental problems of computing (1) a global cut of G with minimum weight and (2) a cycle of G with minimum weight. The best previously known algorithm for the former problem, running in O(n log³ n) time, can be obtained from the algorithm of Łącki, Nussbaum, Sankowski, and Wulff-Nilsen for single-source all-sinks maximum flows. The best previously known result for the latter problem is the O(n log³ n)-time algorithm of Wulff-Nilsen. By exploiting duality between the two problems in planar graphs, we solve both problems in O(n log n log log n) time via a divideand-conquer algorithm that finds a shortest nondegenerate cycle. The kernel of our result is an O(n log log n)-time algorithm for computing noncrossing shortest paths among nodes well ordered on a common face of a directed plane graph, which is extended from the algorithm of Italiano, Nussbaum, Sankowski, and Wulff-Nilsen for an undirected plane graph. [ABSTRACT FROM AUTHOR]

Let G be an interval graph and take one of its vertices x. Can we find in linear time a minimum number of vertex disjoint paths of G which cover the vertex set of G and have x as one of their endpoints? This paper provides a positive answer to this problem. In the course of developing such an algorithm, we explore the possibility of getting insight on the path structure of interval graphs via greedy graph searches. [ABSTRACT FROM AUTHOR]

We show that every bridgeless cubic graph G with m edges has a cycle cover of length at most 1.6m. Moreover, if G does not contain any intersecting circuits of length 5, then G has a cycle cover of length 212/135 ·m ≈ 1.570m, and if G contains no 5-circuits, then it has a cycle cover of length at most 14/9·m ≈ 1.556m. To prove our results, we show that each 2-edge-connected cubic graph G on n vertices has a 2-factor containing at most n/10+f(G) circuits of length 5, where the value of f(G) depends only on the presence of several subgraphs arising from the Petersen graph. As a corollary we get that each 3-edge-connected cubic graph on n vertices has a 2-factor containing at most n/9 circuits of length 5, and each 4-edge-connected cubic graph on n vertices has a 2-factor containing at most n/10 circuits of length 5. [ABSTRACT FROM AUTHOR]

Given a finite graph (network), let every node (cell) represent an individual dynamics given by a system of ordinary differential equations, and every arrow (edge) encode the dynamical influence of the tail node on the head node. We have then defined a coupled cell system that is associated with the given network structure. Subspaces that are defined by equalities of cell coordinates and left invariant under every coupled cell system respecting the network structure are called synchrony subspaces. They are completely determined by the network structure and form a complete lattice under set inclusions. We analyze the transition of the lattice of synchrony subspaces of a network that is caused by structural changes in the network topology, such as deletion and addition of cells or edges, and rewirings of edges. We give sufficient, and in some cases both sufficient and necessary, conditions under which lattice elements persist or disappear. [ABSTRACT FROM AUTHOR]

One of the most relevant tasks in network analysis is the detection of community structures, or clustering. Most popular techniques for community detection are based on the maximization of a quality function called modularity, which in turn is based upon particular quadratic forms associated to a real symmetric modularity matrix M, defined in terms of the adjacency matrix and a rank-one null model matrix. That matrix could be posed inside the set of relevant matrices involved in graph theory, alongside adjacency and Laplacian matrices. In this paper we analyze certain spectral properties of modularity matrices, which are related to the community detection problem. In particular, we propose a nodal domain theorem for the eigenvectors of M; we point out several relations occurring between the graph's communities and nonnegative eigenvalues of M; and we derive a Cheeger-type inequality for the graph modularity. [ABSTRACT FROM AUTHOR]

Multiple objects in the plane are called pseudodisks if the boundaries of any two of them intersect transversely at most twice. Given a set of n (possibly intersecting) convex pseudodisks of O(1) complexity each and two points s and t in the plane, we present an efficient algorithm for computing a shortest s-to-t path avoiding the pseudodisks. After the union of the pseudodisks is computed, which can be done in O(n log n) randomized time or O(n log² n) deterministic time, our algorithm runs in O(n log n + k) deterministic time, where k is the size of the extended visibility graph of the union of the pseudodisks. Note that k = O(n²) in the worst case. In over two decades, the previously best algorithms for this problem have not improved on the bound of O(n² log n) time, even when all the pseudodisks are pairwise disjoint disks. Our technique is also applicable to a motion planning problem of finding a shortest path to translate a convex object in the plane from one location to another avoiding a given set of polygonal obstacles, improving the previously best known solution and settling an open problem posed in 1988. Our algorithm actually solves a more general version of the open problem. Further, as a byproduct of our approach, we present an O(n log n+k)-time algorithm for computing the extended visibility graph of a set of n (possibly intersecting) convex pseudodisks in the plane. The previously best known time bound for this visibility problem is O(n² log n). [ABSTRACT FROM AUTHOR]

For graph G(V,E), a minimum path cover (MPC) is a minimum cardinality set of vertex disjoint paths that cover V (i.e., every vertex of G is in exactly one path in the cover). This problem is a natural generalization of the Hamiltonian path problem. Cocomparability graphs (the complements of graphs that have an acyclic transitive orientation of their edge sets) are a well studied subfamily of perfect graphs that includes many popular families of graphs such as interval, permutation, and cographs. Furthermore, for every cocomparability graph G and acyclic transitive orientation of the edges of G there is a corresponding poset PG; it is easy to see that an MPC of G is a linear extension of PG that minimizes the bump number of PG. Although there are directly graphtheoretical MPC algorithms (i.e., algorithms that do not rely on poset formulations) for various subfamilies of cocomparability graphs, notably interval graphs, until now all MPC algorithms for cocomparability graphs themselves have been based on the bump number algorithms for posets. In this paper we present the first directly graph-theoretical MPC algorithm for cocomparability graphs; this algorithm is based on two consecutive graph searches followed by a certifying algorithm. Surprisingly, except for a lexicographic depth first search (LDFS) preprocessing step, this algorithm is identical to the corresponding algorithm for interval graphs. The running time of the algorithm is O(min(n², n + mloglogn)), with the nonlinearity coming from LDFS. [ABSTRACT FROM AUTHOR]

We consider the Minimum Linear Arrangement problem and the (Uniform) Sparsest Cut problem. So far, these two notorious NP-hard graph problems have resisted all attempts to prove inapproximability results. We show that they have no polynomial time approximation scheme, unless NP-complete problems can be solved in randomized subexponential time. Furthermore, we show that the same techniques can be used for the Maximum Edge Biclique problem, for which we obtain a hardness factor similar to previous results but under a more standard assumption. [ABSTRACT FROM AUTHOR]

Dynamic connectivity is a well-studied problem, but so far the most compelling progress has been confined to the edge-update model: maintain an understanding of connectivity ill an undirected graph, subject to edge insertions and deletions. In this paper, we study two more challenging, yet equally fundamental, problems. Subgraph connectivity asks us to maintain all understanding of connectivity under vertex updates: updates can turn vertices on and off, and queries refer to the subgraph induced by on vertices. (For instance, this is closer to applications in networks of routers, where node faults may occur.) We describe a data structure supporting vertex updates in Õ(m2/3 amortized time, where m denotes the number of edges in the graph. This greatly improves upon the previous result [T. M. Chan, in Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC), 2002, pp. 7-13], which required fast matrix multiplication and had an update time of O(m0.94). The new data structure is also simpler. Geometric connectivity asks us to maintain a dynamic set of n geometric objects and query connectivity in their intersection graph. (For instance, the intersection graph of balls describes connectivity in a network of sensors with bounded transmission radius.) Previously, nontrivial fully dynamic results were known only for special cases like axis-parallel line segments and rectangles. We provide similarly improved update times, Õ (n2/3), for these special cases. Moreover, we show how to obtain sublinear update bounds for virtually all families of geometric objects which allow sublinear time range queries. In particular, we obtain the first sublinear update time for arbitrary two-dimensional line segments: O*(n9/10); for d-dimensional simplices: O* (n 1 - 1/d(2d+1) ); and for d-dimensional balls: O* (n1 - 1/d(d+1)(2d+3)). [ABSTRACT FROM AUTHOR]

We study the PRIZE-COLLECTING STEINER TREE (PCST), PRIZE-COLLECTING TRAVELING SALESMAN (PCTSP), and PRIZE-COLLECTING PATH (PC-PATE) problems. Given a graph (V, E) with a cost on each edge and a penalty (a.k.a. prize) on each node, the goal is to find a tree (for PCST), cycle (for PCTSP), or path (for PC-PATH) that minimizes the sum of the edge costs in the tree/cycle/path and the penalties of the nodes not spanned by it. In addition to being a useful theoretical tool for helping to solve other optimization problems, PCST has been applied fruitfully by AT&T to the optimization of real-world telecommunications networks. The most recent improvements for the first two problems, a 2-approximation algorithm for each, appeared first in 1992; a 2-approximation for PC-PATH appeared in 2003. The natural linear programming relaxation of POST has an integrality gap of 2, which has been a barrier to further improvements for this problem. We present (2- e)-approximation algorithms for all three problems, connected by a unified technique for improving prize-collecting algorithms that allows us to circumvent the integrality gap barrier. Specifically, our approximation ratio for PRIZE-COLLECTING STEINER TREE is below 1.9672. [ABSTRACT FROM AUTHOR]

The balanced decomposition number f(G) of a graph G was introduced by Fujita and Nakamigawa [Discr. Appl. Math., 156 (2008), pp. 3339-3344]. A balanced coloring of a graph G is a coloring of some of the vertices of G with two colors, such that there is the same number of vertices in each color. Then, f(G) is the minimum integer s with the following property: For any balanced coloring of G, there is a partition V(G) = V1 U̇ … U̇ Vr such that, for every i, Vi induces a connected subgraph, |Vi| ≤ s, and Vi, contains the same number of colored vertices in each color. Fujita and Nakamigawa studied the function f(G) for many basic families of graphs, and demonstrated some applications. In this paper, we shall continue the study of the function f(G). We give a characterization for noncomplete graphs G of order n which are ⌊n/2⌋-connected, in view of the balanced decomposition number. We shall prove that a necessary and sufficient condition for such ⌊n/2⌋-connected graphs G is f(G) = 3. We shall also determine f(G) when G is a complete multipartite graph, and when G is a generalized Θ-graph (i.e., a graph which is a subdivision of a multiple edge). Some applications will also be discussed. Further results about the balanced decomposition number also appear in two subsequent papers by Fujita and Liu. [ABSTRACT FROM AUTHOR]

This paper focuses on the design of minimum-cost networks satisfying two technical constraints. First, the connected components should be unicyclic. Second, some given special nodes must belong to cycles. This problem is a generalization of two known problems: the perfect binary 2-matching problem and the problem of computing a minimum-weight basis of the bicircular matroid. It turns out that the problem is polynomially solvable. An exact extended linear formulation is provided. We also present a partial description of the convex hull of the incidence vectors of these Steiner networks. Polynomial-time separation algorithms are described. One of them is a generalization of the Padberg-Rao algorithm to separate blossom inequalities. [ABSTRACT FROM AUTHOR]

A k-fold coloring of a graph assigns to each vertex a set of k colors, and color sets assigned to adjacent vertices are disjoint. The kth chromatic number Xk(G) of a graph G is the minimum total number of colors needed in a k-fold coloring of G. Given a graph G = (V, E) and an integer m ≥ 0, the m-cone of G, denoted by µm(G), has vertex set (V x {0,1,… , m}) U {u} in which u is adjacent to every vertex of V x {m}, and (x, i)(y, j) is an edge if xy ∈ E and i = j = 0 or xy ∈ E and |i - j| = 1. This paper studies the kth chromatic number of the cone graphs. An upper bound for Xk(µm(G) in terms of Xk(G), k, and m are given. In particular, it is proved that for any graph G, if m ≥ 2k, then Xk(µm(G)) ≤ Xk(G) + 1. We also find a surprising connection between the kth chromatic number of the cone graph of G and the circular chromatic number of G. It is proved that if Xk(G)/k > Xc((G) and Xk(G) is even, then for sufficiently large m, Xk(µm(G)) = Xk(G). In particular, if X(G) > Xc(G) and X(G) is even, then for sufficiently large m, X(µm(G)) = X(G). [ABSTRACT FROM AUTHOR]

Let V = {P1,…, Pl} be a set of internally disjoint paths contained in a graph G, and let S be the subgraph defined by Due to image rights restrictions, multiple line equation(s) cannot be graphically displayed. Pi. A P-bridge is either an edge of G -- E(S) with both endpoints in V(S) or a component C of G -- V(S) along with all the edges from V(C) to V(S). The attachments of a bridge B are the vertices of V(B) ∩ V(S). A bridge B is k-stable if there does not exist a subset of at most k -- 1 paths in P containing every attachment of B. A classic theorem of Tutte [Graph Theory, Addison-Wesley, Menlo Park, CA, 1984] states that if G is a 3-connected graph, there exists a set of internally disjoint paths P'= {Due to image rights restrictions, multiple line equation(s) cannot be graphically displayed.,} such that Pi and Due to image rights restrictions, multiple line equation(s) cannot be graphically displayed. have the same endpoints for 1 ≤ i ≤ t and every P'-bridge is 2-stable. We prove that if the graph is sufficiently connected, the paths Due to image rights restrictions, multiple line equation(s) cannot be graphically displayed. may be chosen so that every bridge containing at least two edges is, in fact, k-stable. We also give several simple applications of this theorem related to a conjecture of Lovasz [Problems in Graph Theory, Recent Advances in Graph Theory, M. Felder, ed., Acadamia, Prague, 1975] on deleting paths while maintaining high connectivity. [ABSTRACT FROM AUTHOR]

We consider the problem of finding obnoxious centers in graphs. For arbitrary graphs with n vertices and m edges, we give a randomized algorithm with O(n log² n + m log n) expected time. For planar graphs, we give algorithms with O (n log n) expected time and O (n log³ n) worst-case time. For graphs with bounded treewidth, we give an algorithm taking O (n log n) worst-case time. The algorithms make use of parametric search and several results for computing distances on graphs of bounded treewidth and planar graphs. [ABSTRACT FROM AUTHOR]

We introduce stochastic time-dependency in evolving graphs: starting from an initial graph, at every time step, every edge changes its state (existing or not) according to a two-state Markovian process with probabilities p (edge birth-rate) and q (edge death-rate). If an edge exists at time t, then, at time t + 1, it dies with probability q. If instead the edge does not exist at time t, then it will come into existence at time t + 1 with probability p. Such an evolving graph model is a wide generalization of time-independent dynamic random graphs [A. E. F. Clementi, A. Monti, F. Pasquale, and R. Silvestri, J. Comput. System Sci., 75 (2009), pp. 213-220] and will be called edge-Markovian evolving graphs. We investigate the speed of information spreading in such evolving graphs. We provide nearly tight bounds (which in fact turn out to be tight for a wide range of probabilities p and q) on the completion time of the flooding mechanism aiming to broadcast a piece of information from a source node to all nodes. In particular, we provide i) a tight characterization of the class of edge-Markovian evolving graphs where flooding time is constant and, thus, it does not asymptotically depend on the initial graph; ii) a tight characterization of the class of edge-Markovian evolving graphs where flooding time does not asymptotically depend on the edge death-rate q. An interesting consequence of our results is that information spreading can be fast even if the graph, at every time step, is very sparse and disconnected. Furthermore, our bounds imply that the flooding time can be exponentially shorter than the mixing time of the edge-Markovian graph. [ABSTRACT FROM AUTHOR]

We introduce the S-PLEX CLUSTER EDITING problem as a generalization of the well-studied CLUSTER EDITING problem; both are NP-hard and both are motivated by graph-based data clustering. Instead of transforming a given graph by a minimum number of edge modifications into a disjoint union of cliques (this is CLUSTER EDITING), the task in the case of S-PLEX CLUSTER EDITING is to transform a graph into a cluster graph consisting of a disjoint union of so-called s-plexes. Herein, an s-plex is a vertex set S inducing a subgraph in which every vertex has degree at least |S| -- s. Cliques are 1-plexes. The advantage of s-plexes for s ≥ 2 is that they allow us to model a more relaxed cluster notion (s-plexes instead of cliques), better reflecting inaccuracies of the input data. We develop a provably effective preprocessing based on data reduction (yielding a so-called problem kernel), a forbidden subgraph characterization of s-plex cluster graphs, and a depth-bounded search tree which is used to find optimal edge modification sets. Altogether, this yields efficient algorithms in case of moderate numbers of edge modifications; this is often a reasonable assumption under a maximum parsimony model for data clustering. [ABSTRACT FROM AUTHOR]

We study the problem of recognizing graph powers and computing roots of graphs. Our focus is on classes of graphs with no short cycles. We provide a polynomial time recognition algorithm for r-th powers of graphs of girth at least 2r + 3, thus improving a recently conjectured bound. Our algorithm also finds all r-th roots of a given graph that have girth at least 2r + 3 and no degree one vertices, which is a step toward a recent conjecture of Levenshtein [Discrete Math., 308 (2008), pp. 993-998] that such roots should be unique. Similar algorithms have so far been designed only for r = 2,3. On the negative side, we prove that recognition of graph powers becomes an NP-complete problem when the bound on girth is about twice smaller. [ABSTRACT FROM AUTHOR]

Bounds on the minimum degree and on the number of vertices attaining it have been much studied for finite edge-/vertex-minimally k-connected/k-edge-connected graphs. We give an overview of the results known for finite graphs and show that most of these carry over to infinite graphs if we consider ends of small degree as well as vertices. [ABSTRACT FROM AUTHOR]

A proper vertex coloring of a graph G is equitable if the sizes of color classes differ by at most one. The equitable chromatic threshold X*eq(G) of G is the smallest integer m such that G is equitably n-colorable for all n ≥ m. We show that for planar graphs G with minimum degree at least two, X*eq(G) ≤ 4 if the girth of G is at least 10, and X*eq(G) < 3 if the girth of G is at least 14. [ABSTRACT FROM AUTHOR]

We prove that if T is a tree on n vertices with maximum degree Δ and the edge probability p(n) satisfies np ≥ C max {Δ log n, n∈} for some constant ∈ > 0, then with high probability the random graph G(n, p) contains a copy of T. The obtained bound on the edge probability is shown to be essentially tight for Δ = n Θ(1). [ABSTRACT FROM AUTHOR]

We study the partial capacitated vertex cover problem (PCVC) in which the input consists of a graph G and a covering requirement L. Each edge e in G is associated with a demand (or load) l(e), and each vertex v is associated with a (soft) capacity c(v) and a weight w(v). A feasible solution is an assignment of edges to vertices such that the total demand of assigned edges is at least L. The weight of a solution is ∑V α(v)w(v), where α(v) is the number of copies of v required to cover the demand of the edges that are assigned to v. The goal is to find a solution of minimum weight. We consider three variants of PCVC. In PCVC with separable demands the only requirement is that the total demand of edges assigned to v is at most α(v)c(v). In PCVC with inseparable demands there is an additional requirement that if an edge is assigned to v, then it must be assigned to one of its copies. The third variant is the unit demands version. We present 3-approximation algorithms for both PCVC with separable demands and PCVC with inseparable demands. We also present a 2-approximation algorithm for PCVC with unit demands. We show that similar results can be obtained for PCVC in hypergraphs and for the prize collecting version of capacitated vertex cover. Our algorithms are based on a unified approach for designing and analyzing approximation algorithms for capacitated covering problems. This approach yields simple algorithms whose analyses rely on the local ratio technique and sophisticated charging schemes. [ABSTRACT FROM AUTHOR]

The firefighter problem is the following discrete-time game on a graph. Initially, a fire starts at a vertex of the graph. In each round, a firefighter protects one vertex not yet on fire, and then the fire spreads to all unprotected neighbors of the vertices on fire. The objective of the firefighter is to save as many vertices as possible. The surviving rate of a graph is the average percentage of vertices that can be saved when a fire starts randomly at one vertex of the graph, which measures the defense ability of a graph as a whole. In this paper, we study the surviving rates of graphs with bounded treewidth. We prove that the surviving rate of every n-vertex outerplanar graph is at least 1 - Θ ( log n/n), which is asymptotically tight. We also prove that if k firefighters are available in each round, then the surviving rate of an n-vertex graph with treewidth at most k is at least 1 - O(k ² log n/n)- Furthermore, we show that the greedy strategy of Hartnell and Li [Congr. Numer., 145 (2000), pp. 187-192] for trees saves at least 1 - Θ (log n/n) percent of vertices on average for an n-vertex tree. Our results settle a conjecture and two problems of Cai and Wang [SIAM J. Discrete Math., 23 (2009), pp. 1814-1826] in affirmative. [ABSTRACT FROM AUTHOR]

In this paper, we study the relationship between eigenvalues and the existence of certain subgraphs in regular graphs. We give a condition on an appropriate eigenvalue that guarantees a lower bound for the matching number of a t-edge-connected d-regular graph when t ≤ d - 2. This work extends some classical results of von Baebler [Comment. Math. Helv., 10 (1937), pp. 275-287] and Berge [Théorie des Graphes et Ses Applications, Collection Universitaire de Mathematiques II, Dunod, Paris, 1958] and more recent work of Cioab ă, Gregory, and Haemers [J. Combin. Theory Ser. B, 99 (2009), pp. 287-297]. We also study the relationships between the eigenvalues of a d-regular t-edge-connected graph G and the maximum number of pairwise disjoint connected subgraphs in G that are each joined to the rest of the graph by exactly t edges. [ABSTRACT FROM AUTHOR]