No-Three-in-Line-in-3D

The no-three-in-line problem, introduced by Dudeney in 1917, asks for the maximum number of points in the n × n grid with no three points collinear. Erdos proved that the answer is Θ(n). We consider the analogous problem in three dimensions, and prove that the maximum number of points in the n × n × n grid with no three collinear is Θ(n²). This result is generalised by the notion of a 3D drawing of a graph. Here each vertex is represented by a distinct gridpoint in , such that the line-segment representing each edge does not intersect any vertex, except for its own endpoints. Note that edges may cross. A 3D drawing of a complete graph K_n is nothing more than a set of n gridpoints with no three collinear. A slight generalisation of our first result is that the minimum volume for a 3D drawing of K_n is Θ(n^3/2). This compares favourably with Θ(n³) when edges are not allowed to cross. Generalising the construction for K_n, we prove that every k-colourable graph on n vertices has a 3D drawing with volume, which is optimal for the k-partite Turan graph.     

Efficient Prüfer-Like Coding and Counting Labelled Hypertrees

We consider labelled r-uniform hypertrees, 2≤r≤n, where n is the number of vertices in the hypertree. Any two hyperedges in a hypertree share at most one vertex and each hyperedge in an r-uniform hypertree contains exactly r vertices. We show that r-uniform hypertrees can be encoded in linear time using as little as n−2 integers in the range [1,n]. The decoding algorithm also runs in linear time. For general hypertrees, we require codes of length n+p−2 where p is the number of vertices belonging to more than one hyperedge in the given hypertree. Based on our coding technique, we show that there are at most distinct labelled r-uniform hypertrees, where f(n,r) is a lower bound on the number of labelled trees with maximum (vertex) degree exceeding . We suggest a counting scheme for determining such a lower bound f(n,r).     

On the complexity of graph self-assembly in accretive systems

We study the complexity of the Accretive Graph Assembly Problem (). An instance of consists of an edge-weighted graph G, a seed vertex in G, and a temperature τ. The goal is to determine if the graph G can be assembled by a sequence of vertex additions starting from the seed vertex. The edge weights model the forces of attraction and repulsion, and determine which vertices can be added to a partially assembled graph at the given temperature. A vertex can be added when the total weight to its already built neighbors in the graph is at least τ. The assembly process is sequential meaning that only one vertex can be added at a time. Our first result is that is NP-complete even on planar graphs with maximum degree 3 when edges have only two different types of weights. This resolves the complexity of in the sense that the problem is poly-time solvable when either the maximum degree is at most 2 or the number of distinct edge weights is one, and is NP-complete otherwise. Our second result is a dichotomy theorem that completely characterizes the complexity of on graphs with maximum degree 3 and two distinct weights: w _p and w _n . We give a simple system of linear constraints on w _p , w _n , and τ that determines whether the problem is NP-complete or is poly-time solvable. In the process of establishing this dichotomy, we give a poly-time algorithm to solve a non-trivial class of Finally, we consider the optimization version of where the goal is to assemble a largest-possible induced subgraph of the given input graph. We show that even on graphs that can be assembled and have maximum degree 3, it is NP-hard to assemble a (1/n ^1-ε)-fraction of the input graph for any here n denotes the number of vertices in G.     

Quantum Algorithms for Matching Problems

We present quantum algorithms for the following matching problems in unweighted and weighted graphs with n vertices and m edges:

Fast 3-coloring Triangle-Free Planar Graphs

Although deciding whether the vertices of a planar graph can be colored with three colors is NP-hard, the widely known Grötzsch’s theorem states that every triangle-free planar graph is 3-colorable. We show the first o(n ²) algorithm for 3-coloring vertices of triangle-free planar graphs. The time complexity of the algorithm is $\mathcal{O}(n\log n)Although deciding whether the vertices of a planar graph can be colored with three colors is NP-hard, the widely known Gr?tzsch’s theorem states that every triangle-free planar graph is 3-colorable. We show the first o(n ²) algorithm for 3-coloring vertices of triangle-free planar graphs. The time complexity of the algorithm is O(nlogn)\mathcal{O}(n\log n) .     

Approximating the Bandwidth of Caterpillars

A caterpillar is a tree in which all vertices of degree three or more lie on one path, called the backbone. We present a polynomial time algorithm that produces a linear arrangement of the vertices of a caterpillar with bandwidth at most O(log n/log log n) times the local density of the caterpillar, where the local density is a well known lower bound on the bandwidth. This result is best possible in the sense that there are caterpillars whose bandwidth is larger than their local density by a factor of Ω(log n/log log n). The previous best approximation ratio for the bandwidth of caterpillars was O(log n). We show that any further improvement in the approximation ratio would require using linear arrangements that do not respect the order of the vertices of the backbone. We also show how to obtain a (1+ε) approximation for the bandwidth of caterpillars in time . This result generalizes to trees, planar graphs, and any family of graphs with treewidth .     

Minimum Weakly Fundamental Cycle Bases Are Hard To Find

In the last years, new variants of the minimum cycle basis (MCB) problem and new classes of cycle bases have been introduced, as motivated by several applications from disparate areas of scientific and technological inquiry. At present, the complexity status of the MCB problem is settled only for undirected, directed, and strictly fundamental cycle bases (SFCB’s). Weakly fundamental cycle bases (WFCB’s) form a natural superclass of SFCB’s. A cycle basis of a graph G is a WFCB iff ν=0 or there exists an edge e of G and a circuit C _i in such that is a WFCB of G∖e. WFCB’s still possess several of the nice properties offered by SFCB’s. At the same time, several classes of graphs enjoying WFCB’s of cost asymptotically inferior to the cost of the cheapest SFCB’s have been found and exhibited in the literature. Considered also the computational difficulty of finding cheap SFCB’s, these works advocated an in-depth study of WFCB’s. In this paper, we settle the complexity status of the MCB problem for WFCB’s (the MWFCB problem). The problem turns out to be -hard. However, in this paper, we also offer a simple and practical 2⌈log ₂ n⌉-approximation algorithm for the MWFCB problem. In O(n ν) time, this algorithm actually returns a WFCB whose cost is at most 2⌈log ₂ n⌉∑ _e∈E(G) w _e , thus allowing a fast 2⌈log ₂ n⌉-approximation also for the MCB problem. With this algorithm, we provide tight bounds on the cost of any MCB and MWFCB.     

Approximating Minimum Feedback Sets and Multicuts in Directed Graphs

This paper deals with approximating feedback sets in directed graphs. We consider two related problems: the weighted feedback vertex set (FVS) problem, and the weighted feedback edge set (FES) problem. In the {FVS} (resp. FES) problem, one is given a directed graph with weights (each of which is at least one) on the vertices (resp. edges), and is asked to find a subset of vertices (resp. edges) with minimum total weight that intersects every directed cycle in the graph. These problems are among the classical NP-hard problems and have many applications. We also consider a generalization of these problems: subset-fvs and subset-fes, in which the feedback set has to intersect only a subset of the directed cycles in the graph. This subset consists of all the cycles that go through a distinguished input subset of vertices and edges, denoted by X . This generalization is also NP-hard even when |X|=2 . We present approximation algorithms for the subset-fvs and subset-fes problems. The first algorithm we present achieves an approximation factor of O(log ² |X|) . The second algorithm achieves an approximation factor of O(min{log τ ^* log log τ ^* , log n log log n)} , where τ ^* is the value of the optimum fractional solution of the problem at hand, and n is the number of vertices in the graph. We also define a multicut problem in a special type of directed networks which we call circular networks, and show that the subset-fes and subset-fvs problems are equivalent to this multicut problem. Another contribution of our paper is a combinatorial algorithm that computes a (1+ɛ) approximation to the fractional optimal feedback vertex set. Computing the approximate solution is much simpler and more efficient than general linear programming methods. All of our algorithms use this approximate solution. Received May 31, 1995; revised June 11, 1996, and October 9, 1996.     

Parallel merging with restriction

In this paper, we study the merging of two sorted arrays and on EREW PRAM with two restrictions: (1) The elements of two arrays are taken from the integer range [1,n], where n=Max(n ₁,n ₂). (2) The elements are taken from either uniform distribution or non-uniform distribution such that , for 1≤i≤p (number of processors). We give a new optimal deterministic algorithm runs in time using p processors on EREW PRAM. For ; the running time of the algorithm is O(log ^(g) n) which is faster than the previous results, where log ^(g) n=log log ^(g−1) n for g>1 and log ⁽¹⁾ n=log n. We also extend the domain of input data to [1,n ^k ], where k is a constant.

Approximately Fair Cost Allocation in Metric Traveling Salesman Games

A traveling salesman game is a cooperative game . Here N, the set of players, is the set of cities (or the vertices of the complete graph) and c _D is the characteristic function where D is the underlying cost matrix. For all S⊆N, define c _D (S) to be the cost of a minimum cost Hamiltonian tour through the vertices of S∪{0} where is called as the home city. Define Core as the core of a traveling salesman game . Okamoto (Discrete Appl. Math. 138:349–369, [2004]) conjectured that for the traveling salesman game with D satisfying triangle inequality, the problem of testing whether Core is empty or not is -hard. We prove that this conjecture is true. This result directly implies the -hardness for the general case when D is asymmetric. We also study approximately fair cost allocations for these games. For this, we introduce the cycle cover games and show that the core of a cycle cover game is non-empty by finding a fair cost allocation vector in polynomial time. For a traveling salesman game, let and ∀ S⊆N, x(S)≤ε⋅c _D (S)} be an ε-approximate core, for a given ε>1. By viewing an approximate fair cost allocation vector for this game as a sum of exact fair cost allocation vectors of several related cycle cover games, we provide a polynomial time algorithm demonstrating the non-emptiness of the log ₂(|N|−1)-approximate core by exhibiting a vector in this approximate core for the asymmetric traveling salesman game. We improve it further by finding a -approximate core in polynomial time for some constant c. We also show that there exists an ε ₀>1 such that it is -hard to decide whether ε ₀-Core is empty or not. A preliminary version of the paper appeared in the third Workshop on Approximation and Online Algorithms (WAOA), 2005.     

Bent and hyper-bent functions over a field of 2ℓ elements

We study the parameters of bent and hyper-bent (HB) functions in n variables over a field $ P = \mathbb{F}_q We study the parameters of bent and hyper-bent (HB) functions in n variables over a field with q = 2^ℓ elements, ℓ > 1. Any such function is identified with a function F: Q → P, where . The latter has a reduced trace representation F = tr _P ^Q (Φ), where Φ(x) is a uniquely defined polynomial of a special type. It is shown that the most accurate generalization of results on parameters of bent functions from the case ℓ = 1 to the case ℓ > 1 is obtained if instead of the nonlinearity degree of a function one considers its binary nonlinearity index (in the case ℓ = 1 these parameters coincide). We construct a class of HB functions that generalize binary HB functions found in [1]; we indicate a set of parameters q and n for which there are no other HB functions. We introduce the notion of the period of a function and establish a relation between periods of (hyper-)bent functions and their frequency characteristics. Original Russian Text ? A.S. Kuz’min, V.T. Markov, A.A. Nechaev, V.A. Shishkin, A.B. Shishkov, 2008, published in Problemy Peredachi Informatsii, 2008, Vol. 44, No. 1, pp. 15–37. Supported in part by the Russian Foundation for Basic Research, project nos. 05-01-01018 and 05-01-01048, and the President of the Russian Federation Council for State Support of Leading Scientific Schools, project nos. NSh-8564.2006.10 and NSh-5666.2006.1. A part of the results were obtained in the course of research in the Cryptography Academy of the Russian Federation.     

An Improved Parameterized Algorithm for the Minimum Node Multiway Cut Problem

The parameterized node multiway cut problem is for a given graph to find a separator of size bounded by k whose removal separates a collection of terminal sets in the graph. In this paper, we develop an O(k4 ^k n ³) time algorithm for this problem, significantly improving the previous algorithm of time for the problem. Our result gives the first polynomial time algorithm for the minimum node multiway cut problem when the separator size is bounded by O(log n). A preliminary version of this paper was presented at The 10th Workshop on Algorithms and Data Structures (WADS 2007). This work was supported in part by the National Science Foundation under the Grants CCR-0311590 and CCF-0430683.     

Combinatorial Algorithms for Data Migration to Minimize Average Completion Time

The data migration problem is to compute an efficient plan for moving data stored on devices in a network from one configuration to another. It is modeled by a transfer graph, where vertices represent the storage devices, and edges represent data transfers required between pairs of devices. Each vertex has a non-negative weight, and each edge has a processing time. A vertex completes when all the edges incident on it complete; the constraint is that two edges incident on the same vertex cannot be processed simultaneously. The objective is to minimize the sum of weighted completion times of all vertices. Kim (J. Algorithms 55, 42–57, 2005) gave an LP-rounding 3-approximation algorithm when edges have unit processing times. We give a more efficient primal-dual algorithm that achieves the same approximation guarantee. When edges have arbitrary processing times we give a primal-dual 5.83-approximation algorithm. We also study a variant of the open shop scheduling problem. This is a special case of the data migration problem in which the transfer graph is bipartite and the objective is to minimize the sum of completion times of edges. We present a simple algorithm that achieves an approximation ratio of , thus improving the 1.796-approximation given by Gandhi et al. (ACM Trans. Algorithms 2(1), 116–129, 2006). We show that the analysis of our algorithm is almost tight. A preliminary version of the paper appeared in the Proceedings of the 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006. Research of R. Gandhi partially supported by Rutgers University Research Council Grant. Research of J. Mestre done at the University of Maryland; supported by NSF Awards CCR-0113192 and CCF-0430650, and the University of Maryland Dean’s Dissertation Fellowship.     

On “Exploiting” Node-Heterogeneous Clusters Optimally

It is proved that “FIFO” worksharing protocols provide asymptotically optimal solutions to two problems related to sharing large collections of independent tasks in a heterogeneous network of workstations (HNOW) . In the , one seeks to accomplish as much work as possible on during a prespecified fixed period of L time units. In the , one seeks to complete W units of work by “renting” for as short a time as necessary. The worksharing protocols we study are crafted within an architectural model that characterizes via parameters that measure ’s workstations’ computational and communicational powers. All valid protocols are self-scheduling, in the sense that they determine completely both an amount of work to allocate to each of ’s workstations and a schedule for all related interworkstation communications. The schedules provide either a value for W given L, or a value for L given W, hence solve both of the motivating problems. A protocol observes a FIFO regimen if it has ’s workstations finish their assigned work, and return their results, in the same order in which they are supplied with their workloads. The proven optimality of FIFO protocols resides in the fact that they accomplish at least as much work as any other protocol during all sufficiently long worksharing episodes, and that they complete sufficiently large given collections of tasks at least as fast as any other protocol. Simulation experiments illustrate that the superiority of FIFO protocols is often observed during worksharing episodes of only a few minutes’ duration. A portion of this research was presented at the 15th ACM Symp. on Parallelism in Algorithms and Architectures (2003).     

Linear Data Structures for Fast Ray-Shooting amidst Convex Polyhedra

We consider the problem of ray shooting in a three-dimensional scene consisting of k (possibly intersecting) convex polyhedra with a total of n facets. That is, we want to preprocess them into a data structure, so that the first intersection point of a query ray and the given polyhedra can be determined quickly. We describe data structures that require preprocessing time and storage (where the notation hides polylogarithmic factors), and have polylogarithmic query time, for several special instances of the problem. These include the case when the ray origins are restricted to lie on a fixed line ℓ ₀, but the directions of the rays are arbitrary, the more general case when the supporting lines of the rays pass through ℓ ₀, and the case of rays orthogonal to some fixed line with arbitrary origins and orientations. We also present a simpler solution for the case of vertical ray-shooting with arbitrary origins. In all cases, this is a significant improvement over previously known techniques (which require Ω(n ²) storage, even when k ≪ n). Work by Haim Kaplan and Natan Rubin has been supported by Grant 975/06 from the Israel Science Fund. Work by Micha Sharir and Natan Rubin was partially supported by NSF Grant CCF-05-14079, by a grant from the U.S.–Israeli Binational Science Foundation, by grant 155/05 from the Israel Science Fund, Israeli Academy of Sciences, by a grant from the AFIRST French–Israeli program, and by the Hermann Minkowski–MINERVA Center for Geometry at Tel Aviv University. A preliminary version of this paper appeared in Proc. 15th Annu. Europ. Sympos. Alg. (2007), 287–298.     

Exponential Lower Bounds for the Running Time of DPLL Algorithms on Satisfiable Formulas

DPLL (for Davis, Putnam, Logemann, and Loveland) algorithms form the largest family of contemporary algorithms for SAT (the propositional satisfiability problem) and are widely used in applications. The recursion trees of DPLL algorithm executions on unsatisfiable formulas are equivalent to treelike resolution proofs. Therefore, lower bounds for treelike resolution (known since the 1960s) apply to them. However, these lower bounds say nothing about the behavior of such algorithms on satisfiable formulas. Proving exponential lower bounds for them in the most general setting is impossible without proving P ≠ NP; therefore, to prove lower bounds, one has to restrict the power of branching heuristics. In this paper, we give exponential lower bounds for two families of DPLL algorithms: generalized myopic algorithms, which read up to n ^1−ε of clauses at each step and see the remaining part of the formula without negations, and drunk algorithms, which choose a variable using any complicated rule and then pick its value at random. ^★Extended abstract of this paper appeared in Proceedings of ICALP 2004, LNCS 3142, Springer, 2004, pp. 84–96. ^†Supported by CCR grant CCR-0324906. ^‡Supported in part by Russian Science Support Foundation, RAS program of fundamental research “Research in principal areas of contemporary mathematics,” and INTAS grant 04-77-7173. ^§Supported in part by INTAS grant 04-77-7173.     

Path Hitting in Acyclic Graphs

An instance of the path hitting problem consists of two families of paths, and ℋ, in a common undirected graph, where each path in ℋ is associated with a non-negative cost. We refer to and ℋ as the sets of demand and hitting paths, respectively. When p∈ℋ and share at least one mutual edge, we say that p hits q. The objective is to find a minimum cost subset of ℋ whose members collectively hit those of . In this paper we provide constant factor approximation algorithms for path hitting, confined to instances in which the underlying graph is a tree, a spider, or a star. Although such restricted settings may appear to be very simple, we demonstrate that they still capture some of the most basic covering problems in graphs. Our approach combines several novel ideas: We extend the algorithm of Garg, Vazirani and Yannakakis (Algorithmica, 18:3–20, 1997) for approximate multicuts and multicommodity flows in trees to prove new integrality properties; we present a reduction that involves multiple calls to this extended algorithm; and we introduce a polynomial-time solvable variant of the edge cover problem, which may be of independent interest. An extended abstract of this paper appeared in Proceedings of the 14th Annual European Symposium on Algorithms, 2006. This work is part of D. Segev’s Ph.D. thesis prepared at Tel-Aviv University under the supervision of Prof. Refael Hassin.     

Mapping computations

Let Z be a set of integers and Z ^n×n be a ring for any integer n. We define as a latter point. Hom(Z ⁿ ,Z ^m ) denotes as a homomorphism of Z ⁿ into Z ^m . For any element in Z ⁿ , we define S+T:Z ⁿ →Z ^m as . As a result, S+T become a homomorphism of Z ⁿ into Z ^m . We also define kU:Z ⁿ →Z ^m as . Consequently, kU become a homomorphism of Z ⁿ into Z ^m . Moreover, Hom (Z ⁿ ,Z ^m ) is isomorphic to Z ^n×m . A novel class of the structured matrices which is a set of elements of Hom (Z ⁿ ,Z ⁿ ) over a ring of integers with a displacement structure, referred to as a C-Cauchy-like matrix, will be formulated and presented. Using the displacement approach, which was originally discovered by Kailath, Kung, and Morf (J. Math. Anal. Appl. 68:395–407, 1979), a new superfast algorithm for the multiplication of a C-Cauchy-like matrix of the size n×n over a field with a vector will be designed. The memory space for storing a C-Cauchy-like matrix of the size n×n over a field is O(n) versus O(n ²) for a general matrix of the size n×n over a field. The arithmetic operations of a product of a C-Cauchy-like matrix and a vector is reduced dramatically to O(n) from O(n ²), which can be used to transform a latter point to another latter point such that . Moreover, the displacement structure can also be extended to a Kronecker matrix W ⊗ Z. A new class of the Kronecker-like matrices with the displacement rank r, r<n will be also discovered. The memory space for storing a Kronecker-like matrix of the size (n×1)⊗(1×n) over a field is decreased to O(rn). The arithmetic operations for a product of a Kronecker-like matrix with the displacement rank r and a vector is also accelerated to O(rn).