Jun 29 2017

cs.DS arXiv:1706.09185v1

In the $k$-dispersion problem, we need to select $k$ nodes of a given graph so as to maximize the minimum distance between any two chosen nodes. This can be seen as a generalization of the independent set problem, where the goal is to select nodes so that the minimum distance is larger than 1. We design an optimal $O(n)$ time algorithm for the dispersion problem on trees consisting of $n$ nodes, thus improving the previous $O(n\log n)$ time solution from 1997. We also consider the weighted case, where the goal is to choose a set of nodes of total weight at least $W$. We present an $O(n\log^2n)$ algorithm improving the previous $O(n\log^4 n)$ solution. Our solution builds on the search version (where we know the minimum distance $\lambda$ between the chosen nodes) for which we present tight $\Theta(n\log n)$ upper and lower bounds.

In this paper, we present two main results. First, by only one conjecture (Conjecture 2.9) for recognizing a vertex symmetric graph, which is the hardest task for our problem, we construct an algorithm for finding an isomorphism between two graphs in polynomial time $ O(n^{3}) $. Second, without that conjecture, we prove the algorithm to be of quasi-polynomial time $ O(n^{1.5\log n}) $. The conjectures in this paper are correct for all graphs of size no larger than $ 5 $ and all graphs we have encountered. At least the conjecture for determining if a graph is vertex symmetric is quite true intuitively. We are not able to prove them by hand, so we have planned to find possible counterexamples by a computer. We also introduce new concepts like collapse pattern and collapse tomography, which play important roles in our algorithms.

By a tight tour in a $k$-uniform hypergraph $H$ we mean any sequence of its vertices $(w_0,w_1,\ldots,w_{s-1})$ such that for all $i=0,\ldots,s-1$ the set $e_i=\{w_i,w_{i+1}\ldots,w_{i+k-1}\}$ is an edge of $H$ (where operations on indices are computed modulo $s$) and the sets $e_i$ for $i=0,\ldots,s-1$ are pairwise different. A tight tour in $H$ is a tight Euler tour if it contains all edges of $H$. We prove that the problem of deciding if a given $3$-uniform hypergraph has a tight Euler tour is NP-complete, and that it cannot be solved in time $2^{o(m)}$ (where $m$ is the number of edges in the input hypergraph), unless the ETH fails. We also present an exact exponential algorithm for the problem, whose time complexity matches this lower bound, and the space complexity is polynomial. In fact, this algorithm solves a more general problem of computing the number of tight Euler tours in a given uniform hypergraph.

Jun 29 2017

cs.DS arXiv:1706.09355v1

In this paper we present some new complexity results on the routing time of a graph under the \textitrouting via matching model. This is a parallel routing model which was introduced by Alon et al\citealon1994routing. The model can be viewed as a communication scheme on a distributed network. The nodes in the network can communicate via matchings (a step), where a node exchanges data (pebbles) with its matched partner. Let $G$ be a connected graph with vertices labeled from $\{1,...,n\}$ and the destination vertices of the pebbles are given by a permutation $\pi$. The problem is to find a minimum step routing scheme for the input permutation $\pi$. This is denoted as the routing time $rt(G,\pi)$ of $G$ given $\pi$. In this paper we characterize the complexity of some known problems under the routing via matching model and discuss their relationship to graph connectivity and clique number. We also introduce some new problems in this domain, which may be of independent interest.

Given a graph $G$ and $k\in{\mathbb N}$, the Dominating Set problem asks for a subset $D$ of $k$ vertices such that every vertex in $G$ is either in $D$ or has a neighbor in $D$. It is well known that Dominating Set is ${\sf W}[2]$-hard when parameterized by $k$. But it admits a linear kernel on graphs of bounded expansion and a polynomial kernel on $K_{d,d}$-free graphs, for a fixed constant $d$. In contrast, the closely related Connected Dominating Set problem (where $G[D]$ is required to be connected) is known not to admit such kernels unless $\textsf{NP} \subseteq \textsf{coNP/poly}$. We show that even though the kernelization complexity of Dominating Set and Connected Dominating Set diverges on sparse graphs this divergence is not as extreme as kernelization lower bounds suggest. To do so, we study the Connected Dominating Set problem under the recently introduced framework of lossy kernelization. In this framework, for $\alpha>1$, an $\alpha$-approximate bikernel (kernel) is a polynomial-time algorithm that takes as input an instance $(I,k)$ and outputs an instance $(I',k')$ of a problem (the same problem) such that, for every $c > 1$, a $c$-approximate solution for the new instance can be turned into a $c\alpha$-approximate solution of the original instance in polynomial time. Moreover, the size of $(I',k')$ is bounded by a function of $k$ and $\alpha$. We show that Connected Dominating Set admits an $\alpha$-approximate bikernel on graphs of bounded expansion and an $\alpha$-approximate kernel on $K_{d,d}$-free graphs, for every $\alpha>1$. For $K_{d,d}$-free graphs we obtain instances of size $k^{\mathcal{O}(d^2 / (\alpha-1))}$ while for bounded expansion graphs we obtain instances of size $\mathcal{O}(f(\alpha) k)$ (i.e, linear in $k$), where $f(\alpha)$ is a computable function depending only on $\alpha$.

For two positive integers $k$ and $\ell$, a $(k \times \ell)$-spindle is the union of $k$ pairwise internally vertex-disjoint directed paths with $\ell$ arcs between two vertices $u$ and $v$. We are interested in the (parameterized) complexity of several problems consisting in deciding whether a given digraph contains a subdivision of a spindle, which generalize both the Maximum Flow and Longest Path problems. We obtain the following complexity dichotomy: for a fixed $\ell \geq 1$, finding the largest $k$ such that an input digraph $G$ contains a subdivision of a $(k \times \ell)$-spindle is polynomial-time solvable if $\ell \leq 3$, and NP-hard otherwise. We place special emphasis on finding spindles with exactly two paths and present FPT algorithms that are asymptotically optimal under the ETH. These algorithms are based on the technique of representative families in matroids, and use also color-coding as a subroutine. Finally, we study the case where the input graph is acyclic, and present several algorithmic and hardness results.

We study the following problem: for given integers $d$, $k$ and graph $G$, can we reduce some fixed graph parameter $\pi$ of $G$ by at least $d$ via at most $k$ graph operations from some fixed set $S$? As parameters we take the chromatic number $\chi$, clique number $\omega$ and independence number $\alpha$, and as operations we choose the edge contraction ec and vertex deletion vd. We determine the complexity of this problem for $S=\{\mbox{ec}\}$ and $S=\{\mbox{vd}\}$ and $\pi\in \{\chi,\omega,\alpha\}$ for a number of subclasses of perfect graphs. We use these results to determine the complexity of the problem for $S=\{\mbox{ec}\}$ and $S=\{\mbox{vd}\}$ and $\pi\in \{\chi,\omega,\alpha\}$ restricted to $H$-free graphs.