Frank Gurski, Dominique Komander, Carolin Rehs
2019-04-02
Coloring is one of the most famous problems in graph theory. The coloring problem on undirected graphs has been well studied, whereas there are very few results for coloring problems on directed graphs. An oriented k-coloring of an oriented graph G=(V,A) is a partition of the vertex set V into k independent sets such that all the arcs linking two of these subsets have the same direction. The oriented chromatic number of an oriented graph G is the smallest k such that G allows an oriented k-coloring. Deciding whether an acyclic digraph allows an oriented 4-coloring is NP-hard. It follows, that finding the chromatic number of an oriented graph is an NP-hard problem. This motivates to consider the problem on oriented co-graphs. After giving several characterizations for this graph class, we show a linear time algorithm which computes an optimal oriented coloring for an oriented co-graph. We further prove how the oriented chromatic number can be computed for the disjoint union and order composition from the oriented chromatic number of the involved oriented co-graphs. It turns out that within oriented co-graphs the oriented chromatic number is equal to the length of a longest oriented path plus one. We also show that the graph isomorphism problem on oriented co-graphs can be solved in linear time.
Christopher Morris, Petra Mutzel
2019-04-02
The
-dimensional Weisfeiler-Leman algorithm is a well-known heuristic for the graph isomorphism problem. Moreover, it recently emerged as a powerful tool for supervised graph classification. The algorithm iteratively partitions the set of -tuples, defined over the set of vertices of a graph, by considering neighboring -tuples. Here, we propose a \new{local} variant which considers a subset of the original neighborhood in each iteration step. The cardinality of this local neighborhood, unlike the original one, only depends on the sparsity of the graph. Surprisingly, we show that the local variant has at least the same power as the original algorithm in terms of distinguishing non-isomorphic graphs. In order to demonstrate the practical utility of our local variant, we apply it to supervised graph classification. Our experimental study shows that our local algorithm leads to improved running times and classification accuracies on established benchmark datasets.
Matthew Fahrbach, Dana Randall
2019-04-02
We analyze the mixing time of Glauber dynamics for the six-vertex model in the ferroelectric and antiferroelectric phases. Specifically, we show that for all Boltzmann weights in the ferroelectric phase, there exist boundary conditions such that local Markov chains require exponential time to converge to equilibrium. This is the first rigorous result about the mixing time of Glauber dynamics for the six-vertex model in the ferroelectric phase. Furthermore, our analysis demonstrates a fundamental connection between correlated random walks and the dynamics of intersecting lattice path models. We also analyze the Glauber dynamics for the six-vertex model with free boundary conditions in the antiferroelectric phase and significantly extend the region for which local Markov chains are known to be slow mixing. This result relies on a Peierls argument and novel properties of weighted non-backtracking walks.
Friedrich Eisenbrand, Christoph Hunkenschröder, Kim-Manuel Klein, Martin Koutecký, Asaf Levin, Shmuel Onn
2019-04-02
We study the general integer programming problem where the number of variables
is a variable part of the input. We consider two natural parameters of the constraint matrix : its numeric measure and its sparsity measure . We show that integer programming can be solved in time , where is some computable function of the parameters and , and is the binary encoding length of the input. In particular, integer programming is fixed-parameter tractable parameterized by and , and is solvable in polynomial time for every fixed and . Our results also extend to nonlinear separable convex objective functions. Moreover, for linear objectives, we derive a strongly-polynomial algorithm, that is, with running time , independent of the rest of the input data. We obtain these results by developing an algorithmic framework based on the idea of iterative augmentation: starting from an initial feasible solution, we show how to quickly find augmenting steps which rapidly converge to an optimum. A central notion in this framework is the Graver basis of the matrix , which constitutes a set of fundamental augmenting steps. The iterative augmentation idea is then enhanced via the use of other techniques such as new and improved bounds on the Graver basis, rapid solution of integer programs with bounded variables, proximity theorems and a new proximity-scaling algorithm, the notion of a reduced objective function, and others. As a consequence of our work, we advance the state of the art of solving block-structured integer programs. In particular, we develop near-linear time algorithms for -fold, tree-fold, and -stage stochastic integer programs. We also discuss some of the many applications of these classes.
Giulia Bernardini, Paola Bonizzoni, Gianluca Della Vedova, Murray Patterson
2019-04-02
The problem of comparing trees representing the evolutionary histories of cancerous tumors has turned out to be crucial, since there is a variety of different methods which typically infer multiple possible trees. A departure from the widely studied setting of classical phylogenetics, where trees are leaf-labelled, tumoral trees are fully labelled, i.e., \emph{every} vertex has a label. In this paper we provide a rearrangement distance measure between two fully-labelled trees. This notion originates from two operations: one which modifies the topology of the tree, the other which permutes the labels of the vertices, hence leaving the topology unaffected. While we show that the distance between two trees in terms of each such operation alone can be decided in polynomial time, the more general notion of distance when both operations are allowed is NP-hard to decide. Despite this result, we show that it is fixed-parameter tractable, and we give a 4-approximation algorithm when one of the trees is binary.
Ikumi Hide, Soh Kumabe, Takanori Maehara
2019-04-02
The Floyd--Warshall algorithm is a well-known algorithm for the all-pairs shortest path problem that is simply implemented by triply nested loops. In this study, we show that the incorrect implementations of the Floyd--Warshall algorithm that misorder the triply nested loops give correct solutions if these are repeated three times.
Diptarama Hendrian, Takuya Takagi, Shunsuke Inenaga
2019-01-29
The suffix trees are fundamental data structures for various kinds of string processing. The suffix tree of a string
of length has nodes and edges, and the string label of each edge is encoded by a pair of positions in . Thus, even after the tree is built, the input text needs to be kept stored and random access to is still needed. The linear-size suffix tries (LSTs), proposed by Crochemore et al. [Linear-size suffix tries, TCS 638:171-178, 2016], are a stand-alone' alternative to the suffix trees. Namely, the LST of a string  of length  occupies  total space, and supports pattern matching and other tasks in the same efficiency as the suffix tree without the need to store the input text . Crochemore et al. proposed an offline algorithm which transforms the suffix tree of  into the LST of  in  time and  space, where  is the alphabet size. In this paper, we present two types of online algorithms whichdirectly' construct the LST, from right to left, and from left to right, without constructing the suffix tree as an intermediate structure. Both algorithms construct the LST incrementally when a new symbol is read, and do not access to the previously read symbols. The right-to-left construction algorithm works intime and space and the left-to-right construction algorithm works in time and space. The main feature of our algorithms is that the input text does not need to be stored.
Reyan Ahmed, Keaton Hamm, Mohammad Javad Latifi Jebelli, Stephen Kobourov, Faryad Darabi Sahneh, Richard Spence
2019-04-01
Given a weighted graph
and , a subgraph is a \emph{ --spanner} of if the lengths of shortest paths in are preserved in up to a multiplicative factor of . The \emph{subsetwise spanner} problem aims to preserve distances in for only a subset of the vertices. We generalize the minimum-cost subsetwise spanner problem to one where vertices appear on multiple levels, which we call the \emph{multi-level graph spanner} (MLGS) problem, and describe two simple heuristics. Applications of this problem include road/network building and multi-level graph visualization, especially where vertices may require different grades of service. We formulate a 0--1 integer linear program (ILP) of size for the more general minimum \emph{pairwise spanner problem}, which resolves an open question by Sigurd and Zachariasen on whether this problem admits a useful polynomial-size ILP. We extend this ILP formulation to the MLGS problem, and evaluate the heuristic and ILP performance on random graphs of up to 100 vertices and 500 edges.
Rohan Ghuge, Viswanath Nagarajan
2018-12-05
We consider the following general network design problem on directed graphs. The input is an asymmetric metric
, root , monotone submodular function and budget . The goal is to find an -rooted arborescence of cost at most that maximizes . Our main result is a simple quasi-polynomial time -approximation algorithm for this problem, where is the number of vertices in an optimal solution. To the best of our knowledge, this is the first non-trivial approximation ratio for this problem. As a consequence we obtain an -approximation algorithm for directed (polymatroid) Steiner tree in quasi-polynomial time. We also extend our main result to a setting with additional length bounds at vertices, which leads to improved -approximation algorithms for the single-source buy-at-bulk and priority Steiner tree problems. For the usual directed Steiner tree problem, our result matches the best previous approximation ratio [GLL19]. Our algorithm has the advantage of being deterministic and faster: the runtime is . For polymatroid Steiner tree and single-source buy-at-bulk, our result improves prior approximation ratios by a logarithmic factor. For directed priority Steiner tree, our result seems to be the first non-trivial approximation ratio. All our approximation ratios are tight (up to constant factors) for quasi-polynomial algorithms.
Adrien Chan-Hon-Tong
2019-01-22
This short paper presents an algorithm which aims to solve generic linear program (
or ) using simple projections and call to a sub solver dedicated to linear feasibility ( ), recently, proven to be a strongly polynomial problem thank to Chubanov algorithm. This algorithm is proven to be strongly polynomial in some restricted cases. This result calls for a consolidation and a discussion.
