Voting is a simple mechanism to aggregate the preferences of agents. Many voting rules have been shown to be NP-hard to manipulate. However, a number of recent theoretical results suggest that this complexity may only be in the worst-case since manipulation is often easy in practice. In this paper, we show that empirical studies are useful in improving our understanding of this issue. We demonstrate that there is a smooth transition in the probability that a coalition can elect a desired candidate using the veto rule as the size of the manipulating coalition increases. We show that a rescaled probability curve displays a simple and universal form independent of the size of the problem. We argue that manipulation of the veto rule is asymptotically easy for many independent and identically distributed votes even when the coalition of manipulators is critical in size. Based on this argument, we identify a situation in which manipulation is computationally hard. This is when votes are highly correlated and the election is "hung". We show, however, that even a single uncorrelated voter is enough to make manipulation easy again.
Finally, similar phenomena have been observed in the phase transition for the Hamiltonian cycle problem @cite_22 @cite_11 . If the number of edges is small, there is likely to be a node of degree smaller than 2. There cannot therefore be any Hamiltonian cycle. By the time that there are enough edges for all nodes to be of degree 2, there are likely to be many possible Hamiltonian cycles and even a simple heuristic can find one. Thus, the phase transition in the existence of a Hamiltonian cycle is not associated with hard instances of the problem. The behavior seen here is similar. By the time the coalition is large enough to manipulate the result, the variance in scores between the candidates is likely to be so large that computing a successful manipulation or proving none is possible is easy.
@cite_22 @cite_11
2045652154 1938603953
Abstract We continue the study of boundary classes for NP -hard problems and focus on seven NP -hard graph problems involving non-local properties: Hamiltonian Cycle , Hamiltonian Cycle Through Specified Edge , Hamiltonian Path , Feedback Vertex Set , Connected Vertex Cover , Connected Dominating Set and Graph VC CON Dimension . Our main result is the determination of the first boundary class for Feedback Vertex Set . We also determine boundary classes for Hamiltonian Cycle Through Specified Edge and Hamiltonian Path and give some insights on the structure of some boundary classes for the remaining problems. Using an improved backtrack algorithm with sophisticated pruning techniques, we revise previous observations correlating a high frequency of hard to solve Hamiltonian cycle instances with the Gn,m phase transition between Hamiltonicity and non-Hamiltonicity. Instead all tested graphs of 100 to 1500 vertices are easily solved. When we artificially restrict the degree sequence with a bounded maximum degree, although there is some increase in difficulty, the frequency of hard graphs is still low. When we consider more regular graphs based on a generalization of knight's tours, we observe frequent instances of really hard graphs, but on these the average degree is bounded by a constant. We design a set of graphs with a feature our algorithm is unable to detect and so are very hard for our algorithm, but in these we can vary the average degree from O(1) to O(n). We have so far found no class of graphs correlated with the Gn,m phase transition which asymptotically produces a high frequency of hard instances. In this paper, we consider Hamiltonian cycles of vertices in convex position on the plane, where, in general, these cycles contain crossing edges. We give several results concerning the minimum number of operations that delete two crossing edges, add two other edges and preserve hamiltonicity in transforming these cycles to non-crossing Hamiltonian cycles. This paper showed the pancyclicity of Cartesian product graphs with faulty edges.This paper showed the bipancyclicity of Cartesian product graphs with faulty edges.Determining the edge-fault pancyclicity (bipancyclicity) of NQ m r , ? , m 1 efficiently.Determining the edge-fault pancyclicity (bipancyclicity) of GQ m r , ? , m 1 efficiently. Let r? 4 be an even integer. Graph G is r-bipancyclic if it contains a cycle of every even length from r to 2 ? n ( G ) 2 ? , where n ( G ) is the number of vertices in G. A graph G is r-pancyclic if it contains a cycle of every length from r to n ( G ) , where r ? 3 . A graph is k-edge-fault Hamiltonian if, after deleting arbitrary k edges from the graph, the resulting graph remains Hamiltonian. The terms k-edge-fault r-bipancyclic and k-edge-fault r-pancyclic can be defined similarly. Given two graphs G and H, where n ( G ) , n ( H ) ? 9, let k 1 , k 2 ? 5 be the minimum degrees of G and H, respectively. This study determined the edge-fault r-bipancyclic and edge-fault r-pancyclic of Cartesian product graph G × H with some conditions. These results were then used to evaluate the edge-fault pancyclicity (bipancyclicity) of NQ m r , ? , m 1 and GQ m r , ? , m 1 . Efficient graph search is a central issue in many aspects of AI. In most of existing work there is a distinction between the active “searcher”, which both executes the algorithm and holds the memory, and the passive “searched graph”, over which the searcher has no control at all. Large dynamic networks like the Internet, where the nodes are powerful computers and the links have narrow bandwidth and are heavilydloaded, call for a different paradigm, in which most of the burden of computing and memorizing is moved from the searching agent to the nodes of the network. In this paper we suggest a method for searching an undirected, connected graph using the VertexdAntdWalk method, where an a(ge)nt walks along the edges of a graph G, occasionally leaving “pheromone” traces at nodes, and using those traces to guide its exploration. We show that the ant can cover the graph within time O (nd), where n is the number of vertices and d the diameter of G. The use of traces achieves a tradedoff between random and selfdavoiding walks, as it dictates a lower priority for alreadydvisited neighbors. Further properties of the suggested method are: (a) modularity: a group of searching agents, each applying the same protocol, can cooperate on a mission of covering a graph with minimal explicit communication between thems (b) possible convergence to a limit cycle: a Hamiltonian path in G (if one exists) is a possible limit cycle of the process. How do real graphs evolve over timeq What are normal growth patterns in social, technological, and information networksq Many studies have discovered patterns in static graphs, identifying properties in a single snapshot of a large network or in a very small number of snapshots; these include heavy tails for in- and out-degree distributions, communities, small-world phenomena, and others. However, given the lack of information about network evolution over long periods, it has been hard to convert these findings into statements about trends over time. Here we study a wide range of real graphs, and we observe some surprising phenomena. First, most of these graphs densify over time with the number of edges growing superlinearly in the number of nodes. Second, the average distance between nodes often shrinks over time in contrast to the conventional wisdom that such distance parameters should increase slowly as a function of the number of nodes (like O(log n) or O(log(log n)). Existing graph generation models do not exhibit these types of behavior even at a qualitative level. We provide a new graph generator, based on a forest fire spreading process that has a simple, intuitive justification, requires very few parameters (like the flammability of nodes), and produces graphs exhibiting the full range of properties observed both in prior work and in the present study. We also notice that the forest fire model exhibits a sharp transition between sparse graphs and graphs that are densifying. Graphs with decreasing distance between the nodes are generated around this transition point. Last, we analyze the connection between the temporal evolution of the degree distribution and densification of a graph. We find that the two are fundamentally related. We also observe that real networks exhibit this type of relation between densification and the degree distribution. A subgraph of an edge-coloured complete graph is called rainbow if all its edges have different colours. In 1980 Hahn conjectured that every properly edge-coloured complete graph @math has a rainbow Hamiltonian path. Although this conjecture turned out to be false, it was widely believed that such a colouring always contains a rainbow cycle of length almost @math . In this paper, improving on several earlier results, we confirm this by proving that every properly edge-coloured @math has a rainbow cycle of length @math . One of the main ingredients of our proof, which is of independent interest, shows that a random subgraph of a properly edge-coloured @math formed by the edges of a random set of colours has a similar edge distribution as a truly random graph with the same edge density. In particular it has very good expansion properties. 1. Fundamental Concepts. What Is a Graph? Paths, Cycles, and Trails. Vertex Degrees and Counting. Directed Graphs. 2. Trees and Distance. Basic Properties. Spanning Trees and Enumeration. Optimization and Trees. 3. Matchings and Factors. Matchings and Covers. Algorithms and Applications. Matchings in General Graphs. 4. Connectivity and Paths. Cuts and Connectivity. k-connected Graphs. Network Flow Problems. 5. Coloring of Graphs. Vertex Colorings and Upper Bounds. Structure of k-chromatic Graphs. Enumerative Aspects. 6. Planar Graphs. Embeddings and Euler's Formula. Characterization of Planar Graphs. Parameters of Planarity. 7. Edges and Cycles. Line Graphs and Edge-Coloring. Hamiltonian Cycles. Planarity, Coloring, and Cycles. 8. Additional Topics (Optional). Perfect Graphs. Matroids. Ramsey Theory. More Extremal Problems. Random Graphs. Eigenvalues of Graphs. Appendix A: Mathematical Background. Appendix B: Optimization and Complexity. Appendix C: Hints for Selected Exercises. Appendix D: Glossary of Terms. Appendix E: Supplemental Reading. Appendix F: References. Indices. Abstract We consider a refinement of the partition function of graph homomorphisms and present a quasi-polynomial algorithm to compute it in a certain domain. As a corollary, we obtain quasi-polynomial algorithms for computing partition functions for independent sets, perfect matchings, Hamiltonian cycles and dense subgraphs in graphs as well as for graph colorings. This allows us to tell apart in quasi-polynomial time graphs that are sufficiently far from having a structure of a given type (i.e., independent set of a given size, Hamiltonian cycle, etc.) from graphs that have sufficiently many structures of that type, even when the probability to hit such a structure at random is exponentially small. For many random constraint satisfaction problems, by now there exist asymptotically tight estimates of the largest constraint density for which solutions exist. At the same time, for many of these problems, all known polynomial-time algorithms stop finding solutions at much smaller densities. For example, it is well-known that it is easy to color a random graph using twice as many colors as its chromatic number. Indeed, some of the simplest possible coloring algorithms achieve this goal. Given the simplicity of those algorithms, one would expect room for improvement. Yet, to date, no algorithm is known that uses (2 - epsiv)chi colors, in spite of efforts by numerous researchers over the years. In view of the remarkable resilience of this factor of 2 against every algorithm hurled at it, we find it natural to inquire into its origin. We do so by analyzing the evolution of the set of k-colorings of a random graph, viewed as a subset of 1,...,k n, as edges are added. We prove that the factor of 2 corresponds in a precise mathematical sense to a phase transition in the geometry of this set. Roughly speaking, we prove that the set of k-colorings looks like a giant ball for k ges 2chi, but like an error-correcting code for k les (2 - epsiv)chi. We also prove that an analogous phase transition occurs both in random k-SAT and in random hypergraph 2-coloring. And that for each of these three problems, the location of the transition corresponds to the point where all known polynomial-time algorithms fail. To prove our results we develop a general technique that allows us to establish rigorously much of the celebrated 1-step replica-symmetry-breaking hypothesis of statistical physics for random CSPs. How do real graphs evolve over time? What are "normal" growth patterns in social, technological, and information networks? Many studies have discovered patterns in static graphs, identifying properties in a single snapshot of a large network, or in a very small number of snapshots; these include heavy tails for in- and out-degree distributions, communities, small-world phenomena, and others. However, given the lack of information about network evolution over long periods, it has been hard to convert these findings into statements about trends over time.Here we study a wide range of real graphs, and we observe some surprising phenomena. First, most of these graphs densify over time, with the number of edges growing super-linearly in the number of nodes. Second, the average distance between nodes often shrinks over time, in contrast to the conventional wisdom that such distance parameters should increase slowly as a function of the number of nodes (like O(log n) or O(log(log n)).Existing graph generation models do not exhibit these types of behavior, even at a qualitative level. We provide a new graph generator, based on a "forest fire" spreading process, that has a simple, intuitive justification, requires very few parameters (like the "flammability" of nodes), and produces graphs exhibiting the full range of properties observed both in prior work and in the present study. We consider the metric Traveling Salesman Problem (Δ-TSP for short) and study how stability (as defined by Bilu and Linial [3]) influences the complexity of the problem. On an intuitive level, an instance of Δ-TSP is γ-stable (γ > 1), if there is a unique optimum Hamiltonian tour and any perturbation of arbitrary edge weights by at most γ does not change the edge set of the optimal solution (i.e., there is a significant gap between the optimum tour and all other tours). We show that for γ ≥ 1.8 a simple greedy algorithm (resembling Prim's algorithm for constructing a minimum spanning tree) computes the optimum Hamiltonian tour for every γ-stable instance of the Δ-TSP, whereas a simple local search algorithm can fail to find the optimum even if γ is arbitrary. We further show that there are γ-stable instances of Δ-TSP for every 1 < γ < 2. These results provide a different view on the hardness of the Δ-TSP and give rise to a new class of problem instances which are substantially easier to solve than instances of the general Δ-TSP. For the vast majority of local graph problems standard dynamic programming techniques give c^tw V^O(1) algorithms, where tw is the treewidth of the input graph. On the other hand, for problems with a global requirement (usually connectivity) the best-known algorithms were naive dynamic programming schemes running in tw^O(tw) V^O(1) time. We breach this gap by introducing a technique we dubbed Cut&Count that allows to produce c^tw V^O(1) Monte Carlo algorithms for most connectivity-type problems, including Hamiltonian Path, Feedback Vertex Set and Connected Dominating Set, consequently answering the question raised by Lokshtanov, Marx and Saurabh [SODA'11] in a surprising way. We also show that (under reasonable complexity assumptions) the gap cannot be breached for some problems for which Cut&Count does not work, like CYCLE PACKING. The constant c we obtain is in all cases small (at most 4 for undirected problems and at most 6 for directed ones), and in several cases we are able to show that improving those constants would cause the Strong Exponential Time Hypothesis to fail. Our results have numerous consequences in various fields, like FPT algorithms, exact and approximate algorithms on planar and H-minor-free graphs and algorithms on graphs of bounded degree. In all these fields we are able to improve the best-known results for some problems. Abstract Two edge-disjoint spanning trees of a graph G are completely independent if the two paths connecting any two vertices of G in the two trees are internally disjoint. It has been asked whether sufficient conditions for hamiltonian graphs are also sufficient for the existence of two completely independent spanning trees (CISTs). We prove that it is true for the classical Ore-condition. That is, if G is a graph on n vertices in which each pair of non-adjacent vertices have degree-sum at least n , then G has two CISTs. It is known that the line graph of every 4-edge connected graph is hamiltonian. We prove that this is also true for CISTs: the line graph of every 4-edge connected graph has two CISTs. Thomassen conjectured that every 4-connected line graph is hamiltonian. Unfortunately, being 4-connected is not enough for the existence of two CISTs in line graphs. We prove that there are infinitely many 4-connected line graphs that do not have two CISTs. In this paper we propose a special computational device which uses light rays for solving the Hamiltonian path problem on a directed graph. The device has a graph-like representation and the light is traversing it by following the routes given by the connections between nodes. In each node the rays are uniquely marked so that they can be easily identified. At the destination node we will search only for particular rays that have passed only once through each node. We show that the proposed device can solve small and medium instances of the problem in reasonable time. Restoration of writing order from a single-stroked handwriting image can be seen as the problem of finding the smoothest path in its graph representation. In this paper, a 3-phase approach to restore a writing order is proposed within the framework of the edge continuity relation (ECR). In the initial, local phase, in order to obtain possible ECRs at an even-degree node, a neural network is used for the node of degree 4 and a theoretical approach is presented for the node of degree higher than 4 by introducing certain reasonable assumptions. In the second phase, we identify double-traced lines by employing maximum weighted matching. This makes it possible to transform the problem of obtaining possible ECRs at odd-degree node to that at even-degree node. In the final, global phase, we find all the candidates of single-stroked paths by depth first search and select the best one by evaluating SLALOM smoothness. Experiments on static images converted from online data in the Unipen database show that our method achieves a restoration rate of 96.0 percent Asymptotic and finite size parameters for phase transitions : Hamiltonian circuit as a case study This article investigates the stability of the ground state subspace of a canonical parent Hamiltonian of a Matrix product state against local perturbations. We prove that the spectral gap of such a Hamiltonian remains stable under weak local perturbations even in the thermodynamic limit, where the entire perturbation might not be bounded. Our discussion is based on preceding work by Yarotsky that develops a perturbation theory for relatively bounded quantum perturbations of classical Hamiltonians. We exploit a renormalization procedure, which on large scale transforms the parent Hamiltonian of a Matrix product state into a classical Hamiltonian plus some perturbation. We can thus extend Yarotsky’s results to provide a perturbation theory for parent Hamiltonians of Matrix product states and recover some of the findings of the independent contributions ( in Phys Rev B 8(11):115108, 2013) and (Michalakis and Pytel in Comm Math Phys 322(2):277–302, 2013). Polygonal objects are prevalent in man-made scenes. Early approaches to detecting them relied mainly on geometry while subsequent ones also incorporated appearance-based cues. It has recently been shown that this could be done fast by searching for cycles in graphs of line-fragments, provided that the cycle scoring function can be expressed as additive terms attached to individual fragments. In this paper, we propose an approach that eliminates this restriction. Given a weighted line-fragment graph, we use its cyclomatic number to partition the graph into managebly-sized sub-graphs that preserve nodes and edges with a high weight and are most likely to contain object contours. Object contours are then detected as maximally scoring elementary circuits enumerated in each sub-graph. Our approach can be used with any cycle scoring function and multiple candidates that share line fragments can be found. This is unlike in other approaches that rely on a greedy approach to finding candidates. We demonstrate that our approach significantly outperforms the state-of-the-art for the detection of building rooftops in aerial images and polygonal object categories from ImageNet. In this paper we suggest the use of light for performing useful computations. Namely, we propose a special device which uses light rays for solving the Hamiltonian path problem on a directed graph. The device has a graph-like representation and the light is traversing it following the routes given by the connections between nodes. In each node the rays are uniquely marked so that they can be easily identified. At the destination node we will search only for particular rays that have passed only once through each node. We show that the proposed device can solve small and medium instances of the problem in reasonable time.