The complexity of the zero-sum 3-flows

A zero-sum k-flow for a graph G   is a vector in the null-space of the 0,1$0,1$-incidence matrix of G   such that its entries belong to {±1,?,±(k−1)}$\{\pm 1,?,\pm (k-1)\}$. Akbari et al. (2009) [5] conjectured that if G is a graph with a zero-sum flow, then G   admits a zero-sum 6-flow. (2,3)$(2,3)$-semiregular graphs are an important family in studying zero-sum flows. Akbari et al. (2009) [5] proved that if Zero-Sum Conjecture is true for any (2,3)$(2,3)$-semiregular graph, then it is true for any graph. In this paper, we show that there is a polynomial time algorithm to determine whether a given (2,3)$(2,3)$-graph G   has a zero-sum 3-flow. In fact, we show that, there is a polynomial time algorithm to determine whether a given (2,4)$(2,4)$-graph G with n   vertices has a zero-sum 3-flow, where the number of vertices of degree four is O(log?n)$O(\log ?n)$. Furthermore, we show that it is NP-complete to determine whether a given (3,4)$(3,4)$-semiregular graph has a zero-sum 3-flow.     

MinT—Architecture and applications of the (t, m, s)-net and OOA database

Many different constructions for (t,m,s)$(t\text{,}m\text{,}s)$-nets and (t,s)$(t\text{,}s)$-sequences are known today. Propagation rules as well as connections to other mathematical objects make it difficult to determine the best net available in a given setting.     

Simplifying the weft hierarchy

We give simple, self-contained proofs of the basic hardness results for the classes W[t]$W[t]$ of the weft hierarchy. We extend these proofs to higher levels of the hierarchy and illuminate the distinctions among its classes. The anti-monotone collapse at W[1,s]$W[1,s]$ and the normalization of weft-t$t$ formulas arise as by-products of the proofs.     

Chordless paths through three vertices

Consider the following problem, which we call “Chordless path through three vertices” or CP3V, for short: Given a simple undirected graph G=(V,E)$G=(V,E)$, a positive integer k, and three distinct vertices s, t  , and v∈V$v\in V$, is there a chordless path of length at most k from s   via v$v$ to t in G? In a chordless path, no two vertices are connected by an edge that is not in the path. Alternatively, one could say that the subgraph induced by the vertex set of the path in G is the path itself. The problem has arisen in the context of service deployment in communication networks. We resolve the parametric complexity of CP3V by proving it W[1]$W[1]$-complete with respect to its natural parameter k  . Our reduction extends to a number of related problems about chordless paths and cycles. In particular, deciding on the existence of a single directed chordless (s,t)$(s,t)$-path in a digraph is also W[1]$W[1]$-complete with respect to the length of the path.     

On miniaturized problems in parameterized complexity theory

We introduce a general notion of miniaturization of a problem that comprises the different miniaturizations of concrete problems considered so far. We develop parts of the basic theory of miniaturizations. Using the appropriate logical formalism, we show that the miniaturization of a definable problem in W[t]$\mathrm{W}[t]$ lies in W[t]$\mathrm{W}[t]$, too. In particular, the miniaturization of the dominating set problem is in W[2]$\mathrm{W}[2]$. Furthermore, we investigate the relation between f(k)·n^o(k)$f(k)·n^{\mathrm{o}(k)}$ time and subexponential time algorithms for the dominating set problem and for the clique problem.     

On hypercube packings,blocking sets and a covering problem

Consider sets S of hypercubes of side 2 in the discrete n-dimensional torus of side 4 with the property that every possible hypercube of side 2 has a nonempty intersection with some hypercube in S. The problem of minimizing the size of S is studied in two settings, depending on whether intersections between hypercubes in S are allowed or not. If intersections are not allowed, then one is asking for the smallest size of a non-extensible packing S  ; this size is denoted by f(n)$f(n)$. If intersections are allowed, then the structure S is called a blocking set. The smallest size of a blocking set S   is denoted by h(n)$h(n)$. By computer-aided techniques, it is shown that f(5)=12$f(5)=12$, f(6)=16$f(6)=16$, h(6)=15$h(6)=15$ and h(7)≤23$h(7)\le 23$. Also, non-extensible packings as well as blocking sets of certain small sizes are classified for n≤6$n\le 6$. There is a direct connection between these problems and a covering problem originating from the football pools.     

An efficient delay-optimal distributed termination detection algorithm

Distributed termination detection is a fundamental problem in parallel and distributed computing and numerous schemes with different performance characteristics have been proposed. These schemes, while being efficient with regard to one performance metric, prove to be inefficient in terms of other metrics. A significant drawback shared by all previous methods is that, on most popular topologies, they take Ω(P)$\mathrm{\Omega }(P)$ time to detect and signal termination after its actual occurrence, where P   is the total number of processing elements. Detection delay is arguably the most important metric to optimize, since it is directly related to the amount of idling of computing resources and to the delay in the utilization of results of the underlying computation. In this paper, we present a novel termination detection algorithm that is simultaneously optimal or near-optimal with respect to all relevant performance measures on any topology. In particular, our algorithm has a best-case detection delay of Θ(1)$\mathrm{\Theta }(1)$ and a finite optimal worst-case detection delay on any topology equal in order terms to the time for an optimal one-to-all broadcast on that topology (which we accurately characterize for an arbitrary topology). On k-ary n  -cube tori and meshes, the worst-case delay is Θ(D)$\mathrm{\Theta }(D)$, where D   is the diameter of the target topology. Further, our algorithm has message and computational complexities of Θ(MD+P)$\mathrm{\Theta }(\mathit{MD}+P)$ in the worst case and, for most applications, Θ(M+P)$\mathrm{\Theta }(M+P)$ in the average case—the same as other message-efficient algorithms, and an optimal space complexity of Θ(P)$\mathrm{\Theta }(P)$, where M is the total number of messages used by the underlying computation. We also give a scheme using counters that greatly reduces the constant associated with the average message and computational complexities, but does not suffer from the counter-overflow problems of other schemes. Finally, unlike some previous schemes, our algorithm does not rely on first-in first-out (FIFO) ordering for message communication to work correctly.     

Topological additive numbering of directed acyclic graphs

We propose to study a problem that arises naturally from both Topological Numbering of Directed Acyclic Graphs, and Additive Coloring (also known as Lucky Labeling). Let D be a digraph and f   a labeling of its vertices with positive integers; denote by S(v)$S(v)$ the sum of labels over all neighbors of each vertex v. The labeling f is called topological additive numbering   if S(u)<S(v)$S(u)<S(v)$ for each arc (u,v)$(u,v)$ of the digraph. The problem asks to find the minimum number k for which D   has a topological additive numbering with labels belonging to {1,…,k}$\{1,\dots ,k\}$, denoted by _ηt(D)${\eta }_t(D)$.     

Algorithms for a class of infinite permutation groups

Motivated by the famous 3n+1$3n+1$ conjecture, we call a mapping from Z$\mathbb{Z}$ to Z$\mathbb{Z}$residue-class-wise affine   if there is a positive integer m$m$ such that it is affine on residue classes (mod m$m$). This article describes a collection of algorithms and methods for computation in permutation groups and monoids formed by residue-class-wise affine mappings.     

On the advice complexity of online bipartite matching and online stable marriage

In this paper, we study the advice complexity of the online bipartite matching problem and the online stable marriage problem. We show that for both problems, $\lceil {\log }_2(n!)\rceil$ bits of advice are necessary and sufficient for a deterministic online algorithm to be optimal, where n denotes the number of vertices in one bipartition in the former problem, and the number of men in the latter.     

First steps to the runtime complexity analysis of ant colony optimization

The paper presents results on the runtime complexity of two ant colony optimization (ACO) algorithms: ant system, the oldest ACO variant, and GBAS, the first ACO variant for which theoretical convergence results have been established. In both cases, as the class of test problems under consideration, a slight generalization of the well-known OneMax test function has been chosen. The techniques used for the runtime analysis of the two algorithms differ: in the case of GBAS, the expected runtime until the optimal solution is reached is studied by a direct bound estimation approach inspired by comparable results for the (1+1)$(1+1)$ evolutionary algorithm (EA). A runtime bound of order O(mlogm)$O(m\log m)$, where m   is the problem instance size, is obtained. In the case of ant system, the original discrete stochastic process is approximated by a suitable continuous deterministic process. The validity of the approximation is shown by means of a rigid convergence theorem exploiting a classical result from mathematical learning theory. Using this approximation, it is demonstrated that for the considered OneMax-type problems, a runtime of order O(mlog(1/ε))$O(m\log (1/\epsilon ))$ until reaching an expected relative   solution quality of 1-ε$1-\epsilon$, and a runtime of O(mlogm)$O(m\log m)$ until reaching the optimal   solution with high probability can be predicted. Our results are the first to show competitiveness in runtime complexity with (1+1$1+1$) EA on OneMax for a proper ACO algorithm.     

A sufficient condition involving implicit degree and neighborhood intersection for long cycles

Let id(v)$\mathit{id}(v)$ denote the implicit degree of a vertex v in a graph G. In this paper, we prove that: Let G   be a 2-connected graph. If max?{id(u),id(v)}≥c/2$\max ?\{\mathit{id}(u),\mathit{id}(v)\}\ge c/2$ for each pair of nonadjacent vertices u and v   in an induced claw, and |N(x)∩N(y)|≥2$|N(x)\cap N(y)|\ge 2$ for each pair of nonadjacent vertices x and y in an induced modified claw, then G contains either a hamiltonian cycle or a cycle of length at least c.     

Tag systems and Collatz-like functions

Tag systems were invented by Emil Leon Post and proven recursively unsolvable by Marvin Minsky. These production systems have proved to be very useful in constructing small universal (Turing complete) systems for several different classes of computational systems, including Turing machines, and are thus important instruments for studying limits or boundaries of solvability and unsolvability. Although there are some results on tag systems and their limits of solvability and unsolvability, there are hardly any that consider both   the shift number v$v$ and the number of symbols μ$\mu$. This paper aims to contribute to research on limits of solvability and unsolvability for tag systems, taking into account these two parameters. The main result is the reduction of the 3n+1$3n+1$-problem to a surprisingly small tag system. It indicates that the present unsolvability line–defined in terms of μ$\mu$ and v$v$–for tag systems might be significantly decreased.     

On the partition dimension of a class of circulant graphs

For a vertex v   of a connected graph G(V,E)$G(V,E)$ and a subset S of V, the distance between a vertex v and S   is defined by d(v,S)=min{d(v,x):x∈S}$d(v,S)=\min \{d(v,x):x\in S\}$. For an ordered k  -partition π={_S1,_S2…_Sk}$\pi =\{S_1,S_2\dots S_k\}$ of V, the partition representation of v with respect to π is the k  -vector r(v|π)=(d(v,_S1),d(v,_S2)…d(v,_Sk))$r(v|\pi )=(d(v,S_1),d(v,S_2)\dots d(v,S_k))$. The k-partition π is a resolving partition if the k  -vectors r(v|π)$r(v|\pi )$, v∈V(G)$v\in V(G)$ are distinct. The minimum k for which there is a resolving k-partition of V is the partition dimension of G. Salman et al. [1] in their paper which appeared in Acta Mathematica Sinica, English Series   proved that partition dimension of a class of circulant graph G(n,±{1,2})$G(n,\pm \{1,2\})$, for all even n?6$n?6$ is four. In this paper we prove that it is three.