Paths and trails in edge-colored graphs

This paper deals with the existence and search for properly edge-colored paths/trails between two, not necessarily distinct, vertices s$s$ and t$t$ in an edge-colored graph from an algorithmic perspective. First we show that several versions of the s−t$s-t$ path/trail problem have polynomial solutions including the shortest path/trail case. We give polynomial algorithms for finding a longest properly edge-colored path/trail between s$s$ and t$t$ for a particular class of graphs and characterize edge-colored graphs without properly edge-colored closed trails. Next, we prove that deciding whether there exist k$k$ pairwise vertex/edge disjoint properly edge-colored s−t$s-t$ paths/trails in a c$c$-edge-colored graph G^c$G^c$ is NP-complete even for k=2$k=2$ and c=Ω(n²)$c=\Omega \left(n^2\right)$, where n$n$ denotes the number of vertices in G^c$G^c$. Moreover, we prove that these problems remain NP-complete for c$c$-edge-colored graphs containing no properly edge-colored cycles and c=Ω(n)$c=\Omega \left(n\right)$. We obtain some approximation results for those maximization problems together with polynomial results for some particular classes of edge-colored graphs.     

Divergence bounded computable real numbers

A real x$x$ is called h$h$-bounded computable  , for some function h:N→N$h:\mathbb{N}\to \mathbb{N}$, if there is a computable sequence (_xs)$(x_s)$ of rational numbers which converges to x$x$ such that, for any n∈N$n\in \mathbb{N}$, at most h(n)$h(n)$ non-overlapping pairs of its members are separated by a distance larger than 2^-n$2^{-n}$. In this paper we discuss properties of h$h$-bounded computable reals for various functions h$h$. We will show a simple sufficient condition for a class of functions h$h$ such that the corresponding h$h$-bounded computable reals form an algebraic field. A hierarchy theorem for h$h$-bounded computable reals is also shown. Besides we compare semi-computability and weak computability with the h$h$-bounded computability for special functions h$h$.     

Faster algorithms for computing Hong’s bound on absolute positiveness

We show how to compute Hong’s bound for the absolute positiveness of a polynomial in d$d$ variables with maximum degree δ$\delta$ in O(nlog^dn)$O\left(n{log}^{d}n\right)$ time, where n$n$ is the number of non-zero coefficients. For the univariate case, we give a linear time algorithm. As a consequence, the time bounds for the continued fraction algorithm for real root isolation improve by a factor of δ$\delta$.     

Swapping a failing edge of a shortest paths tree by minimizing the average stretch factor

We consider a two-edge connected, undirected graph G=(V,E)$G=(V,E)$, with n$n$ nodes and m$m$ non-negatively real weighted edges, and a single source shortest paths tree (SPT) T$T$ of G$G$ rooted at an arbitrary node r$r$. If an edge in T$T$ is temporarily removed, it makes sense to reconnect the nodes disconnected from the root by adding a single non-tree edge, called a swap edge  , instead of rebuilding a new optimal SPT from scratch. In the past, several optimality criteria have been considered to select a best possible swap edge. In this paper we focus on the most prominent one, that is the minimization of the average distance between the root and the disconnected nodes. To this respect, we present an O(mlog²n)$O\left(m{log}^{2}n\right)$ time and O(m)$O\left(m\right)$ space algorithm to find a best swap edge for every edge of T$T$, thus improving for m=o(n²/log²n)$m=o(n^2/{log}^{2}n)$ the previously known O(n²)$O\left(n^2\right)$ time and space complexity algorithm.     

Efficient pebbling for list traversal synopses with application to program rollback

We show how to support efficient back traversal in a unidirectional list, using small memory and with essentially no slowdown in forward steps. Using O(lgn)$O(lgn)$ memory for a list of size n$n$, the i$i$’th back-step from the farthest point reached so far takes O(lgi)$O(lgi)$ time in the worst case, while the overhead per forward step is at most ?$?$ for arbitrary small constant ?>0$?>0$. An arbitrary sequence of forward and back steps is allowed. A full trade-off between memory usage and time per back-step is presented: k$k$ vs. kn^1/k$k{n}^{1/k}$ and vice versa. Our algorithms are based on a novel pebbling technique which moves pebbles on a virtual binary, or n^1/k$n^{1/k}$-ary, tree that can only be traversed in a pre-order fashion.     

Spanners for bounded tree-length graphs

This paper concerns construction of additive stretched spanners with few edges for n$n$-vertex graphs having a tree-decomposition into bags of diameter at most δ$\delta$, i.e., the tree-length δ$\delta$ graphs. For such graphs we construct additive 2δ$2\delta$-spanners with O(δn+nlogn)$O(\delta n+nlogn)$ edges, and additive 4δ$4\delta$-spanners with O(δn)$O\left(\delta n\right)$ edges. This provides new upper bounds for chordal graphs for which δ=1$\delta =1$. We also show a lower bound, and prove that there are graphs of tree-length δ$\delta$ for which every multiplicative δ$\delta$-spanner (and thus every additive (δ−1)$(\delta -1)$-spanner) requires Ω(n^1+1/Θ(δ))$\Omega \left(n^{1+1/\Theta \left(\delta \right)}\right)$ edges.     

Minimum leaf out-branching and related problems

Given a digraph D$D$, the Minimum Leaf Out-Branching problem (MinLOB) is the problem of finding in D$D$ an out-branching with the minimum possible number of leaves, i.e., vertices of out-degree 0. We prove that MinLOB is polynomial-time solvable for acyclic digraphs. In general, MinLOB is NP-hard and we consider three parameterizations of MinLOB. We prove that two of them are NP-complete for every value of the parameter, but the third one is fixed-parameter tractable (FPT). The FPT parameterization is as follows: given a digraph D$D$ of order n$n$ and a positive integral parameter k$k$, check whether D$D$ contains an out-branching with at most n−k$n-k$ leaves (and find such an out-branching if it exists). We find a problem kernel of order O(k²)$O\left(k^2\right)$ and construct an algorithm of running time O(2^O(klogk)+n⁶)$O(2^{O(klogk)}+n^6)$, which is an ‘additive’ FPT algorithm. We also consider transformations from two related problems, the minimum path covering and the maximum internal out-tree problems into MinLOB, which imply that some parameterizations of the two problems are FPT as well.     

A parameterized view on matroid optimization problems

Matroid theory gives us powerful techniques for understanding combinatorial optimization problems and for designing polynomial-time algorithms. However, several natural matroid problems, such as 3-matroid intersection, are NP-hard. Here we investigate these problems from the parameterized complexity point of view: instead of the trivial n^O(k)$n^{O\left(k\right)}$ time brute force algorithm for finding a k$k$-element solution, we try to give algorithms with uniformly polynomial (i.e., f(k)⋅n^O(1)$f\left(k\right)\cdot n^{O\left(1\right)}$) running time. The main result is that if the ground set of a represented linear matroid is partitioned into blocks of size ?$?$, then we can determine in randomized time f(k,?)⋅n^O(1)$f(k,?)\cdot n^{O\left(1\right)}$ whether there is an independent set that is the union of k$k$ blocks. As a consequence, algorithms with similar running time are obtained for other problems such as finding a k$k$-element set in the intersection of ?$?$ matroids, or finding k$k$ terminals in a network such that each of them can be connected simultaneously to the source by ?$?$ disjoint paths.     

Approximately optimal trees for group key management with batch updates

We investigate the group key management problem for broadcasting applications. Previous work showed that, in handling key updates, batch rekeying can be more cost effective than individual rekeying. One model for batch rekeying is to assume that every user has probability p$p$ of being replaced by a new user during a batch period with the total number of users unchanged. Under this model, it was recently shown that an optimal key tree can be constructed in linear time when p$p$ is a constant and in O(n⁴)$O\left(n^4\right)$ time when p→0$p\to 0$. In this paper, we investigate more efficient algorithms for the case p→0$p\to 0$, i.e., when membership changes are sparse. We design an O(n)$O\left(n\right)$ heuristic algorithm for the sparse case and show that it produces a nearly 2-approximation to the optimal key tree. Simulation results show that its performance is even better in practice. We also design a refined heuristic algorithm and show that it achieves an approximation ratio of 1+?$1+?$ for any fixed ?>0$?>0$ and n$n$, as p→0$p\to 0$. Finally, we give another approximation algorithm for any p∈(0,0.693)$p\in (0,0.693)$ which is shown to be quite good by our simulations.     

Algorithms for near solutions to polynomial equations

Let F(x,y)$F(x,y)$ be a polynomial over a field K$K$ and m$m$ a nonnegative integer. We call a polynomial g$g$ over K$K$ an m$m$-near solution of F(x,y)$F(x,y)$ if there exists a c∈K$c\in K$ such that F(x,g)=cx^m$F(x,g)=c{x}^m$, and the number c$c$ is called an m$m$-value of F(x,y)$F(x,y)$ corresponding to g$g$. In particular, c$c$ can be 0. Hence, by viewing F(x,y)=0$F(x,y)=0$ as a polynomial equation over K[x]$K\left[x\right]$ with variable y$y$, every solution of the equation F(x,y)=0$F(x,y)=0$ in K[x]$K\left[x\right]$ is also an m$m$-near solution. We provide an algorithm that gives all m$m$-near solutions of a given polynomial F(x,y)$F(x,y)$ over K$K$, and this algorithm is polynomial time reducible to solving one variable equations over K$K$. We introduce approximate solutions to analyze the algorithm. We also give some interesting properties of approximate solutions.     

An efficient construction of one-to-many node-disjoint paths in folded hypercubes

A folded hypercube is basically a hypercube with additional links augmented, where the additional links connect all pairs of nodes with longest distance in the hypercube. In an n$n$-dimensional folded hypercube, it has been shown that n+1$n+1$ node-disjoint paths from one source node to other n+1$n+1$ (mutually) distinct destination nodes, respectively, can be constructed in O(n⁴)$O\left(n^4\right)$ time so that their maximal length is not greater than ⌈n/2⌉+1$\lceil n/2\rceil +1$, where n+1$n+1$ is the connectivity and ⌈n/2⌉$\lceil n/2\rceil$ is the diameter. Besides, their maximal length is minimized in the worst case. In this paper, we further show that by minimizing the computations of minimal routing functions, these node-disjoint paths can be constructed in O(n³)$O\left(n^3\right)$ time, which is more efficient, and is hard to be reduced because it must take O(n³)$O\left(n^3\right)$ time to compute a minimal routing function by solving a corresponding maximum weighted bipartite matching problem with the best known algorithm.     

A linear-time 2-approximation algorithm for the watchman route problem for simple polygons

Given a simple polygon P$P$ of n$n$ vertices, the watchman route problem   asks for a shortest (closed) route inside P$P$ such that each point in the interior of P$P$ can be seen from at least one point along the route. In this paper, we present a simple, linear-time algorithm for computing a watchman route of length at most two times that of the shortest watchman route. The best known algorithm for computing a shortest watchman route takes O(n⁴logn)$O(n^{4}logn)$ time, which is too complicated to be suitable in practice.     

Claw finding algorithms using quantum walk

The claw finding problem has been studied in terms of query complexity as one of the problems closely connected to cryptography. Given two functions, f$f$ and g$g$, with domain sizes N$N$ and M$M$(N≤M)$(N\le M)$, respectively, and the same range, the goal of the problem is to find x$x$ and y$y$ such that f(x)=g(y)$f\left(x\right)=g\left(y\right)$. This problem has been considered in both quantum and classical settings in terms of query complexity. This paper describes an optimal algorithm that uses quantum walk to solve this problem. Our algorithm can be slightly modified to solve the more general problem of finding a tuple consisting of elements in the two function domains that has a prespecified property. It can also be generalized to find a claw of k$k$ functions for any constant integer k>1$k>1$, where the domain sizes of the functions may be different.