In some professional sports leagues, inter-league games are scheduled among multiple divisions or conferences. This inspired us to study the p-partite Traveling Tournament Problem (p-partite TTP), where teams are partitioned into p leagues, and each team plays games against teams from different leagues. Previously, only the case of p=2, known as the Bipartite TTP or BTTP, has been introduced and studied. In this paper, we show that the p-partite TTP is NP-hard for any fixed p≥3, and we propose an efficient algorithm based on a solution to the Traveling Salesman Problem. Furthermore, we prove that the algorithm achieves a notable approximation ratio of 8/3+O(1/n) when p=3. We also conduct experiments demonstrating that the algorithm produces practical schedules with significantly reduced total travel distances, highlighting its effectiveness in generating high-quality multipartite tournament schedules.

We prove that every class of Eulerian directed graphs of bounded carving width (equivalently, of bounded degree and treewidth) is well-quasi-ordered by strong immersion. In fact, we prove a stronger result, namely that every class of Eulerian directed graphs of bounded carving width, where every vertex is additionally labelled from a well-quasi-order, fixes a linear order on its incident edges, and may impose further restrictions on how the immersion is allowed to route paths through it, is well-quasi-ordered by an adequate notion of strong immersion. To this extent, we develop a framework seemingly suited to prove well-quasi-ordering for classes of Eulerian directed graphs by (strong) immersion and present a first meta theorem in that direction. We complement our results by observing that the class of Eulerian directed graphs of unbounded degree is not well-quasi-ordered by strong immersion, even if we assume the treewidth of the class to be at most two. We conclude with a dichotomy result, proving for a very restricted class of Eulerian directed graphs of unbounded degree that it is not well-quasi-ordered by strong immersion, but it is well-quasi-ordered by weak immersion.

The classic result by Fortune, Hopcroft, and Wyllie [TCS ’80] states that the directed disjoint paths problem is NP-complete even for two pairs of terminals. Extending this well-known result, we show that the directed disjoint paths problem is NP-complete for any constant congestion \(c \ge 1\) and \(k \ge 3c - 1\) pairs of terminals. This refutes a conjecture by Giannopoulou et al. [SODA ’22], which says that the directed disjoint paths problem with congestion two is polynomial-time solvable for any constant number \(k\) of terminal pairs. We then consider the cases that are not covered by this hardness result. The first nontrivial case is \(c = 2\) and \(k = 3\). Our second main result is to show that this case is polynomial-time solvable.

As part of their graph minor project, Robertson and Seymour showed in 1990 that the class of graphs that can be embedded in a given surface can be characterized by a finite set of minimal excluded minors. However, their proof, because existential, does not provide any information on these excluded minors. Seymour proved in 1993 the first and, until now, only known upper bound on the order of the minimal excluded minors for a given surface. This bound is double exponential in the Euler genus \(g\) of the surface and, therefore, very far from the \(\Omega(g)\) lower bound on the maximal order of minimal excluded minors for a surface and most likely far from the best possible bound. More than thirty years later, this paper finally makes progress in lowering this bound to a quasi-polynomial in the Euler genus of the surface. The main catalyzer to reach a quasi-polynomial bound is a breakthrough on the characteristic size of a forbidden structure for a minimal excluded minor \(G\) for a surface of Euler genus \(g\): although it is not hard to show that \(G\) does not contain \(O(g)\) disjoint cycles that are contractible and nested in some embedding of \(G\) as demonstrated by Seymour, this bound can be lowered to \(O(\log g)\) which is essential to obtain the quasi-polynomial bound in this paper. Moreover, we find an upper bound on the maximum degree of \(G\) and the maximum size of a face in an embedding of \(G\) in a surface of Euler genus \(g + 1\) or \(g + 2\), which is, to our understanding, the first such bound. Finally, we develop a new method to bound the height of the tree in a tree decomposition of \(G\). As subsidiary results, we also improve the current bound on the treewidth of a minimal excluded minor \(G\) for a surface by improving the first and, until now, only known bound provided by Seymour. Moreover, we show a better upper bound on the order of a grid minor in \(G\), improving the result by Thomassen from 1997.

We prove that every cyclically 4-edge-connected cubic graph that can be embedded in the torus, with the exception of two specific infinite families of “Petersen-like” graphs, is 3-edge-colorable. This shows that every toroidal snark can be obtained from several copies of the Petersen graph using the dot product operation. The first two snarks in this family are the Petersen graph and one of the Blanuša snarks; the rest were exposed by Belcastro and Kaminski and by Vodopivec. This proves a strengthening of the well-known, long-standing conjecture of Grünbaum from 1968.

Abstract. We show that any planar graph [Formula: see text] has a 5-coloring such that one color class contains at most [Formula: see text] vertices. In other words, there exists a partition of [Formula: see text] into five independent sets [Formula: see text] such that [Formula: see text]. Our proof yields an [Formula: see text]-time algorithm to find such a partition, and unlike the Four Color Theorem, our proof is fully verifiable without computer assistance.

In the Vertex-Disjoint-Paths-With-Congestion problem, the input consists of a digraph D, an integer c and k pairs of vertices (s_i, t_i), and the task is to find a set of paths connecting each s_i to its corresponding t_i, whereas each vertex of D appears in at most c many paths. The case where c = 1 is known to be NP-complete even if k = 2 [Fortune, Hopcroft and Wyllie, 1980] on general digraphs and is W[1]-hard with respect to k (excluding the possibility of an f(k)n^O(1)-time algorithm under standard assumptions) on acyclic digraphs [Slivkins, 2010]. The proof of [Slivkins, 2010] can also be adapted to show W[1]-hardness with respect to k for every congestion c ≥ 1. We strengthen the existing hardness result by showing that the problem remains W[1]-hard for every congestion c ≥ 1 even if: (1) the input digraph D is acyclic, (2) D does not contain an acyclic (5, 5)-grid as a butterfly minor, (3) D does not contain an acyclic tournament on 9 vertices as a butterfly minor, and (4) D has ear-anonymity at most 5. Further, we also show that the edge-congestion variant of the problem remains W[1]-hard for every congestion c ≥ 1 even if: (1) the input digraph D is acyclic, (2) D has maximum undirected degree 3, (3) D does not contain an acyclic (7, 7)-wall as a weak immersion and (4) D has ear-anonymity at most 5.

Reed in 1998 conjectured that every graph G satisfies . As a partial result, he proved the existence of ε > 0 for which every graph G satisfies . We propose an analogue conjecture for digraphs. Given a digraph D, we denote by (D ) the dichromatic number of D, which is the minimum number of colours needed to partition D into acyclic induced subdigraphs. We let denote the size of a largest biclique (a set of vertices inducing a complete digraph) of D and . We conjecture that every digraph D satisfies , which if true implies Reed’s conjecture. As a partial result, we prove the existence of ε > 0 for which every digraph D satisfies . This implies both Reed’s result and an independent result of Harutyunyan and Mohar for oriented graphs.

Abstract. A tripod with feet [Formula: see text] is obtained by six internally disjoint paths, three of them starting at a single vertex [Formula: see text] and ending at [Formula: see text], and another three of them starting at another vertex [Formula: see text] and ending at [Formula: see text]. Tripods play an important role in the proof of the two paths theorem, as well as some other structure theorems concerning rooted minors. The complete characterization of a tripod is well-known; if we cannot get such a tripod, then assuming some mild connectivity, a given graph must be embedded in a plane with [Formula: see text] in the outer face boundary. In this paper, by using the tripod result as a base, we give a structure theorem that, given four vertices [Formula: see text] in a graph [Formula: see text], guarantees a subgraph of [Formula: see text] that is homeomorphic to a subgraph of [Formula: see text] and contains at least three of [Formula: see text] as branches. This result is also motivated by the following problem: Every minimum counterexample to Hajós’ conjecture for [Formula: see text] is internally 5-connected.

A map is a \(2\) -cell decomposition of a closed compact surface, i.e., an embedding of a graph such that every face is homeomorphic to an open disc. An automorphism of a map can be thought of as a permutation of the vertices, which preserves the vertex-edge-face incidences in the embedding. Every automorphism of a map determines an angle-preserving homeomorphism of the surface. While it is conjectured that there is no “truly subquadratic” algorithm for testing map isomorphism for unconstrained genus, we present a linear-time algorithm for computing the generators of the automorphism group of a map on an orientable surface of genus \(g\neq 0\) , parametrized by the genus \(g\) . A map on an orientable surface is uniform if the cyclic vector of sizes of faces incident to a vertex \(v\) does not depend on the choice of \(v\) . The algorithm applies a sequence of local reductions and produces a uniform map while preserving the automorphism group. The automorphism group of the original map can be reconstructed from the automorphism group of the associated uniform map in linear time. We also extend the algorithm to non-orientable surfaces by making use of the antipodal double-cover. The algorithm can be used to solve the map isomorphism problem between maps (orientable or non-orientable) of bounded negative Euler characteristic.

Sentence embeddings represent the meaning of a given sentence using a fixed dimensional vector. Different approaches have been proposed in the Natural Language Processing (NLP) community for learning encoders that can produce accurate sentence embeddings that perform well for diverse downstream tasks requiring sentence representations. Despite prior work focusing mainly on creating accurate sentence embeddings, how to keep private the sensitive information contained in the sentences remains an unexplored research problem. In this article, we propose Covering Metric Analytic Gaussian (CMAG), a covering metric Differential Privacy (DP) mechanism for sentence embeddings such that minimal random noise is added to a set of sentence embeddings produced by an encoder to protect the private information expressed in those sentences. Given a sentence embedding s , CMAG considers the Mahalanobis distance between s and the other sentence embeddings s ’ in the local neighbourhood of s to determine the minimal amount of random noise that must be added to s to obtain provable metric DP guarantees. Experimental results show that the proposed DP mechanism protects private information better than previously proposed DP mechanisms while reporting good performance in a broad range of downstream NLP tasks.

We consider the sparse contextual bandit problem where arm feature affects reward through the inner product of sparse parameters. Recent studies have developed sparsity-agnostic algorithms based on the greedy arm selection policy. However, the analysis of these algorithms requires strong assumptions on the arm feature distribution to ensure that the greedily selected samples are sufficiently diverse; One of the most common assumptions, relaxed symmetry, imposes approximate origin-symmetry on the distribution, which cannot allow distributions that has origin-asymmetric support. In this paper, we show that the greedy algorithm is applicable to a wider range of the arm feature distributions from two aspects. Firstly, we show that a mixture distribution that has a greedy-applicable component is also greedy-applicable. Second, we propose new distribution classes, related to Gaussian mixture, discrete, and radial distribution, for which the sample diversity is guaranteed. The proposed classes can describe distributions with origin-asymmetric support and, in conjunction with the first claim, provide theoretical guarantees of the greedy policy for a very wide range of the arm feature distributions.

We prove that every cyclically 4-edge-connected cubic graph that can be embedded in the projective plane, with the single exception of the Petersen graph, is 3-edge-colorable. In other words, the only (nontrivial) snark that can be embedded in the projective plane is the Petersen graph. This implies that a 2-connected cubic (multi)graph that can be embedded in the projective plane is not 3-edge-colorable if and only if it can be obtained from the Petersen graph by replacing each vertex by a 2-edge-connected planar cubic (multi)graph. Here, a replacement of a vertex$v$in a cubic graph$G$is the operation that takes a 2-connected planar (cubic) multigraph$H$containing some vertex$u$of degree 3, unifying$G-v$and$H-u$, and connecting the vertices in$N_{G}[v]$in$G-v$with the three neighbors of$u$in$H-u$with 3 edges. Any graph obtained in such a way is said to be Petersen-like. This result is a nontrivial generalization of the Four Color Theorem, and its proof requires a combination of extensive computer verification and computer-free extension of existing proofs on colorability. Using this result, we obtain the following algorithmic consequence. Input: A cubic graph$G$. Output: Either a 3-edge-coloring of$G$, an obstruction showing that$G$is not 3-edge-colorable, or the conclusion that$G$cannot be embedded in the projective plane (certified by exposing a forbidden minor for the projective plane contained in$G$). Time complexity:$O(n^{2})$, where$n=\vert V(G)\vert$. An unexpected consequence of this result is a coloring-flow duality statement for the projective plane: A cubic graph embedded in the projective plane is 3-edge-colorable if and only if its dual multigraph is 5-vertex-colorable. Moreover, we show that a 2-edge connected graph embedded in the projective plane admits a nowhere-zero 4-flow unless it is Petersen-like (in which case it does not admit nowhere-zero 4-flows). This proves a strengthening of the Tutte 4-flow conjecture for graphs on the projective plane. Some of our proofs require extensive computer verification. The necessary source codes, together with the input and output files and the complete set of more than 5000 reducible configurations, are available on Github11https://github.com/edge-coloring. Refer to the “README.md” file in each directory for instructions on how to run each program. which can be considered as an addendum to this paper. Moreover, we provide pseudocodes for all our computer verifications.

Disjoint paths problems are among the most prominent problems in combinatorial optimisation. The edge- as well as the Vertex-Disjoint Paths problem are NP-complete, both on directed and undirected graphs. But on undirected graphs, Robertson and Seymour developed an algorithm for both problems that runs in cubic time for every fixed number ‍p of terminal pairs, i.e. they proved that the problem is fixed-parameter tractable on undirected graphs. This is in sharp contrast to the situation on directed graphs, where Fortune, Hopcroft, and Wyllie proved that both problems are NP-complete already for ‍p=2 terminal pairs. In this paper, we study the Edge-Disjoint Paths problem (EDPP) on Eulerian digraphs, a problem that has received significant attention in the literature. Marx proved that the Eulerian EDPP is NP-complete even on structurally very simple Eulerian digraphs. On the positive side, polynomial time algorithms are known only for very restricted cases, such as ‍p≤ 3 or where the demand graph is a union of two stars. The question for which values of ‍p the Edge-Disjoint Paths problem can be solved in polynomial time on Eulerian digraphs has already been raised by Frank, Ibaraki, and Nagamochi almost 30 years ago. But despite considerable effort, the complexity of the problem is still wide open and is considered to be the main open problem in this area. In this paper, we solve this long-open problem by showing that the Edge-Disjoint Paths problem is fixed-parameter tractable on Eulerian digraphs in general (parameterized by the number of terminal pairs). The algorithm itself is reasonably simple but the proof of its correctness requires a deep structural analysis of Eulerian digraphs.

We prove the existence of a computable function f∶ℕ→ℕ such that for every integer k and every digraph D, either D contains a collection C of k directed cycles of even length such that no vertex of D belongs to more than four cycles in C, or there exists a set S⊆ V(D) of size at most f(k) such that D−S has no directed cycle of even length. Moreover, we provide an algorithm that finds one of the two outcomes of this statement in time g(k)nO(1) for some computable function g∶ ℕ→ℕ.

We consider the problem of coloring a 3-colorable graph in polynomial time using as few colors as possible. This is one of the most challenging problems in graph algorithms. In this paper using Blum’s notion of “progress”, we develop a new combinatorial algorithm for the following: Given any 3-colorable graph with minimum degree >√n, we can, in polynomial time, make progress towards a k-coloring for some k=√n/· no(1). We balance our main result with the best-known semi-definite(SDP) approach which we use for degrees below n0.605073. As a result, we show that (n0.19747) colors suffice for coloring 3-colorable graphs. This improves on the previous best bound of (n0.19996) by Kawarabayashi and Thorup from 2017.

This study considers a novel problem setting, referred to as \textit{bandit task assignment}, that incorporates the processing time of each task in the bandit setting. In this problem setting, a player sequentially chooses a set of tasks to start so that the set of processing tasks satisfies a given combinatorial constraint. The reward and processing time for each task follow unknown distributions, values of which are revealed only after the task has been completed. The problem generalizes the stochastic combinatorial semi-bandit problem and the budget-constrained bandit problem. For this problem setting, we propose an algorithm based on upper confidence bounds~(UCB) combined with a phased-update approach. The proposed algorithm admits a gap-dependent regret upper bound of $O(MN(1/\Delta){\log T})$ and a gap-free regret upper bound of $\tilde{O}( \sqrt{MNT} )$, where $N$ is the number of the tasks, $M$ is the maximum number of tasks run at the same time, $T$ is the time horizon, and $\Delta$ is the gap between expected per-round rewards of the optimal and best suboptimal sets of tasks. These regret bounds nearly match lower bounds.

We prove that there exists a function f : ℕ → ℝ such that every directed graph G contains either k directed odd cycles where every vertex of G is contained in at most two of them, or a set of at most f(k) vertices meeting all directed odd cycles. We also give a polynomial-time algorithm for fixed k which outputs one of the two outcomes. Using this algorithmic result, we give a polynomial-time algorithm for fixed k to decide whether such k directed odd cycles exist, or there are no k vertex-disjoint directed odd cycles. This extends the half-integral Erdős-Pósa theorem for undirected odd cycles by Reed [Combinatorica 1999] to directed graphs.

Abstract We present a time-optimal deterministic distributed algorithm for approximating a minimum weight vertex cover in hypergraphs of rank f. This problem is equivalent to the Minimum Weight Set Cover problem in which the frequency of every element is bounded by f. The approximation factor of our algorithm is $$(f+\varepsilon )$$ ( f + ε ) . Let $$\varDelta $$ Δ denote the maximum degree in the hypergraph. Our algorithm runs in the congest model and requires $$O(\log {\varDelta } / \log \log \varDelta )$$ O ( log Δ / log log Δ ) rounds, for constants $$\varepsilon \in (0,1]$$ ε ∈ ( 0 , 1 ] and $$f\in {\mathbb {N}}^+$$ f ∈ N + . This is the first distributed algorithm for this problem whose running time does not depend on the vertex weights nor the number of vertices. Thus adding another member to the exclusive family of provably optimal distributed algorithms. For constant values of f and $$\varepsilon $$ ε , our algorithm improves over the $$(f+\varepsilon )$$ ( f + ε ) -approximation algorithm of Kuhn et al. (SODA, 2006)whose running time is $$O(\log \varDelta + \log W)$$ O ( log Δ + log W ) , where W is the ratio between the largest and smallest vertex weights in the graph. Our algorithm also achieves an f-approximation for the problem in $$O(f\log n)$$ O ( f log n ) rounds, improving over the classical result of Khuller et al. (J Algorithms, 1994) that achieves a running time of $$O(f\log ^2 n)$$ O ( f log 2 n ) . Finally, for weighted vertex cover ( $$f=2$$ f = 2 ) our algorithm achieves a deterministic running time of $$O(\log n)$$ O ( log n ) , matching the randomized previously best result of Koufogiannakis and Young (Distrib Comput, 2011). We also show that integer covering-programs can be reduced to the Minimum Weight Set Cover problem in the distributed setting. This allows us to achieve an $$(f\lceil \log _2(M)+1 \rceil +\varepsilon )$$ ( f ⌈ log 2 ( M ) + 1 ⌉ + ε ) -approximate integral solution in $$\begin{aligned} O\left( (1+f/\log n)\cdot \left( {\frac{\log \varDelta }{ \log \log \varDelta } + ({f\cdot \log M})^{1.01}\cdot \log \varepsilon ^{-1}\cdot (\log \varDelta )^{0.01}}\right) \right) \end{aligned}$$ O ( 1 + f / log n ) · log

We study online task assignment problem with reusable resources, motivated by practical applications such as ridesharing, crowdsourcing and job hiring. In the problem, we are given a set of offline vertices (agents), and, at each time, an online vertex (task) arrives randomly according to a known time-dependent distribution. Upon arrival, we assign the task to agents immediately and irrevocably. The goal of the problem is to maximize the expected total profit produced by completed tasks. The key features of our problem are (1) an agent is reusable, i.e., an agent comes back to the market after completing the assigned task, (2) an agent may reject the assigned task to stay the market, and (3) a task may accommodate multiple agents. The setting generalizes that of existing work in which an online task is assigned to one agent under (1). In this paper, we propose an online algorithm that is 1/2-competitive for the above setting, which is tight. Moreover, when each agent can reject assigned tasks at most Δ times, the algorithm is shown to have the competitive ratio Δ/(3Δ-1), which is at least 1/3. We also evaluate our proposed algorithm with numerical experiments.

We propose a method to protect the privacy of search engine users by decomposing the queries using semantically related and unrelated distractor terms. Instead of a single query, the search engine receives multiple decomposed query terms. Next, we reconstruct the search results relevant to the original query term by aggregating the search results retrieved for the decomposed query terms. We show that the word embeddings learnt using a distributed representation learning method can be used to find semantically related and distractor query terms. We derive the relationship between the obfuscity achieved through the proposed query anonymisation method and the reconstructability of the original search results using the decomposed queries. We analytically study the risk of discovering the search engine users’ information intents under the proposed query obfuscation method, and empirically evaluate its robustness against clustering-based attacks. Our experimental results show that the proposed method can accurately reconstruct the search results for user queries, without compromising the privacy of the search engine users.

The tangle tree-decomposition theorem, proved by Robertson and Seymour in their seminal graph minors series, turns out to be an extremely valuable tool in structural and algorithmic graph theory. In this paper, we prove the analogous result for digraphs, the directed tangle tree-decomposition theorem. More precisely, we introduce directed tangles and provide a directed tree-decomposition of digraphs G that distinguishes all maximal directed tangles in G. Furthermore, for any integer k, we construct a directed tree-decomposition that distinguishes all directed tangles of order k. By relaxing the bound slightly, we can make the previous result algorithmic: for fixed k, we design a polynomial-time algorithm that finds a directed tree-decomposition distinguishing all directed tangles of order 6k–1 separated by some separation of order less than k. As a direct application of the tangle tree-decomposition theorem, we prove that for every fixed k there is a polynomial-time algorithm which, on input G, and source and sink vertices (s1, t1),…, (sk, tk), either finds a family of paths P1,…, Pk such that each Pi links si to ti and every vertex of G is contained in at most two paths, or determines that there is no set of pairwise vertex-disjoint paths each connecting si to ti. This result improves previous results (with “two” replaced by “three”), and given known hardness results, our result cannot be extended to fixed parameter tractability nor fully vertex-disjoint directed paths.

The contextual combinatorial semi-bandit problem with linear payoff functions is a decision-making problem in which a learner chooses a set of arms with the feature vectors in each round under given constraints so as to maximize the sum of rewards of arms. Several existing algorithms have regret bounds that are optimal with respect to the number of rounds T. However, there is a gap of Õ(max(√d, √k)) between the current best upper and lower bounds, where d is the dimension of the feature vectors, k is the number of the chosen arms in a round, and Õ(·) ignores the logarithmic factors. The dependence of k and d is of practical importance because k may be larger than T in real-world applications such as recommender systems. In this paper, we fill the gap by improving the upper and lower bounds. More precisely, we show that the C2UCB algorithm proposed by Qin, Chen, and Zhu (2014) has the optimal regret bound Õ(d√kT + dk) for the partition matroid constraints. For general constraints, we propose an algorithm that modifies the reward estimates of arms in the C2UCB algorithm and demonstrate that it enjoys the optimal regret bound for a more general problem that can take into account other objectives simultaneously. We also show that our technique would be applicable to related problems. Numerical experiments support our theoretical results and considerations.

We investigate the misspecified linear contextual bandit (MLCB) problem, which is a generalization of the linear contextual bandit (LCB) problem. The MLCB problem is a decision-making problem in which a learner observes $d$-dimensional feature vectors, called arms, chooses an arm from $K$ arms, and then obtains a reward from the chosen arm in each round. The learner aims to maximize the sum of the rewards over $T$ rounds. In contrast to the LCB problem, the rewards in the MLCB problem may not be represented by a linear function in feature vectors; instead, it is approximated by a linear function with additive approximation parameter $\varepsilon \geq 0$. In this paper, we propose an algorithm that achieves $\tilde{O}(\sqrt{dT\log(K)} + \varepsilon\sqrt{d}T)$ regret, where $\tilde{O}(\cdot)$ ignores polylogarithmic factors in $d$ and $T$. This is the first algorithm that guarantees a high-probability regret bound for the MLCB problem without knowledge of the approximation parameter $\varepsilon$.

Embedding entities and relations of a knowledge graph in a low-dimensional space has shown impressive performance in predicting missing links between entities.Although progresses have been achieved, existing methods are heuristically motivated and theoretical understanding of such embeddings is comparatively underdeveloped.This paper extends the random walk model (Arora et al., 2016a) of word embeddings to Knowledge Graph Embeddings (KGEs) to derive a scoring function that evaluates the strength of a relation R between two entities h (head) and t (tail).Moreover, we show that marginal loss minimisation, a popular objective used in much prior work in KGE, follows naturally from the loglikelihood ratio maximisation under the probabilities estimated from the KGEs according to our theoretical relationship.We propose a learning objective motivated by the theoretical analysis to learn KGEs from a given knowledge graph.Using the derived objective, accurate KGEs are learnt from FB15K237 and WN18RR benchmark datasets, providing empirical evidence in support of the theory. *Danushka Bollegala holds concurrent appointments as a Professor at University of Liverpool and as an Amazon Scholar.This paper describes work performed at the University of Liverpool and is not associated with Amazon.

The multi-commodity flow-cut gap is a fundamental parameter that affects the performance of several divide & conquer algorithms, and has been extensively studied for various classes of undirected graphs. It has been shown by Linial, London and Rabinovich [20] and by Aumann and Rabani [5] that for general n-vertex graphs it is bounded by O(log n) and the Gupta-Newman-Rabinovich-Sinclair conjecture [13] asserts that it is O(1) for any family of graphs that excludes some fixed minor. We show that the multicommodity flow-cut gap on directed planar graphs is O(log3n). This is the first sub-polynomial bound for any family of directed graphs of super-constant treewidth. We remark that for general directed graphs, it has been shown by Chuzhoy and Khanna [11] that the gap is Ω(n1/7), even for directed acyclic graphs. As a direct consequence of our result, we also obtain the first polynomial-time polylogarithmic-approximation algorithms for the Directed Non-Bipartite Sparsest-Cut, and the Directed Multicut problems for directed planar graphs, which extends the long-standing result for undirectd planar graphs by Rao [22] (with a slightly weaker bound). At the heart of our result we investigate low-distortion quasimetric embeddings into directed$e$1. More precisely, we construct O(log2n)-Lipschitz quasipartitions for the shortest-path quasimetric spaces of planar digrap$hs$, which generalize the notion of Lipschitz partitions from the theory of metric embeddings. This construction combines ideas from the theory of bi-Lipschitz embeddings, with tools form data structures on directed planar graphs.

A map is a 2-cell decomposition of a closed compact surface, i.e., an embedding of a graph such that every face is homeomorphic to an open disc. An automorphism of a map can be thought of as a permutation of the vertices which preserves the vertex-edge-face incidences in the embedding. When the underlying surface is orientable, every automorphism of a map determines an angle-preserving homeomorphism of the surface. While it is conjectured that there is no "truly subquadratic" algorithm for testing map isomorphism for unconstrained genus, we present a linear-time algorithm for computing the generators of the automorphism group of a map, parametrized by the genus of the underlying surface. The algorithm applies a sequence of local reductions and produces a uniform map, while preserving the automorphism group. The automorphism group of the original map can be reconstructed from the automorphism group of the uniform map in linear time. We also extend the algorithm to non-orientable surfaces by making use of the antipodal double-cover.

Abstract Algorithmic problem of computing the most influential nodes in an arbitrary graph (influence maximization) is an important theoretical and practical problem and has been extensively studied for decades. For massive graphs (e.g. modelling huge social networks), randomized algorithms are the answer as the exact computation is prohibitively complex, both for runtime and space. This paper concentrates on developing new accurate and efficient randomized algorithms that drastically cut the memory footprint and scale up the computation of the most influential nodes. Implementing the Reverse Influence Sampling method proposed by Borgs, Brautbar, Chayes and Lucier in 2013, we engineered a novel algorithm, CutTheTail (CTT), which solves the problem of influence maximization (IM) while using up to five orders of magnitude smaller space than the existing renown algorithms. CTT is a heuristic algorithm. We tested the accuracy of CTT on large real-world graphs using Monte Carlo simulation as the benchmark and comparing the quality of CTT solution to the algorithms with theoretically proven guaranteed approximation to optimal. Experiments show that CTT provides solutions with the quality equal to the quality of such algorithms. Savings in required space allow to successfully run CTT on a consumer-grade laptop for a graph with almost a billion of edges. To the best of our knowledge, no other IM algorithm can compute a solution on such a scale using a 16 GB RAM laptop.

This paper offers a nearly optimal algorithm for online linear optimization with delayed bandit feedback. Online linear optimization with bandit feedback, or nonstochastic linear bandits, provides a generic framework for sequential decision-making problems with limited information. This framework, however, assumes that feedback can be observed just after choosing the action, and, hence, does not apply directly to many practical applications, in which the feedback can often only be obtained after a while. To cope with such situations, we consider problem settings in which the feedback can be observed $d$ rounds after the choice of an action, and propose an algorithm for which the expected regret is $\tilde{O}( \sqrt{m (m + d) T} )$, ignoring logarithmic factors in $m$ and $T$, where $m$ and $T$ denote the dimensionality of the action set and the number of rounds, respectively. This algorithm achieves nearly optimal performance, as we are able to show that arbitrary algorithms suffer the regret of $\Omega(\sqrt{m (m+d) T})$ in the worst case. To develop the algorithm, we introduce a technique we refer to as \textit{distribution truncation}, which plays an essential role in bounding the regret. We also apply our approach to cooperative bandits, as studied by Cesa-Bianchi et al. [17] and Bar-On and Mansour [12], and extend their results to the linear bandits setting.

We present improved algorithms for approximating maximum-weight independent set (MaxIS) in the CONGEST model. Given an input graph, let n and Δ be the number of nodes and maximum degree, respectively, and let MIS(n, Δ) be the running time of finding a maximal independent set (MIS) in the CONGEST model. Bar-Yehuda et al. [PODC 2017] showed that there is an algorithm in the CONGEST model that finds a Δ-approximation for MaxIS in O(MIS(n, Δ) log W) rounds, where W is the maximum weight of a node in the graph, which can be as high as poly(n). Whether their algorithm is deterministic or randomized depends on the MIS algorithm that is used as a black-box. Our results:

At the core of the Robertson-Seymour Theory of Graph Minors lies a powerful structure theorem which captures, for any fixed graph H, the common structural features of all the graphs not containing H as a minor [15]. An important step towards this structure theorem is the Flat Wall Theorem [14], which has a lot of algorithmic applications (for example, the minor-testing and the disjoint paths problem with fixed number terminals). In this paper, we prove the directed analogue of this Flat Wall Theorem. Our result builds on the recent Directed Grid Theorem by two of the authors (Kawarabayashi and Kreutzer), and we hope that this is an important and significant step toward the directed structure theorem, as with the case for the undirected graph for the graph minor project.

Given an edged-weighted graph G, the min-k-cut problem asks for a set of edges with minimum total weight whose removal breaks the graph G into at least k connected components. It is well-known that the greedy algorithm can find a (2 – 2/k)-approximation of the min-k-cut in polynomial time. Assuming the Small Set Expansion Hypothesis (SSEH), no polynomial time algorithm can achieve an approximation ratio better than two [9]. Recently, Gupta, Lee and Li [5] gave a 1.9997-approximation FPT algorithm for the min-k-cut parameterized by k. They also improved this approximation ratio to 1.81 [4]. We generalize their proof techniques and show that the min-k-cut has a nearly 5/3-approximation FPT algorithm. Our proof is self-contained and much shorter than that of Gupta, Lee and Li.

We present improved results for approximating maximum-weight independent set (MaxIS) in the CONGEST and LOCAL models of distributed computing. Given an input graph, let n and Δ be the number of nodes and maximum degree, respectively, and let MIS(n,Δ) be the running time of finding a maximal independent set (MIS) in the CONGEST model. Bar-Yehuda et al. [PODC 2017] showed that there is an algorithm in the CONGEST model that finds a Δ-approximation for MaxIS in O(MIS(n,Δ)log W) rounds, where W is the maximum weight of a node in the graph, which can be as large as poly (n). Whether their algorithm is deterministic or randomized that succeeds with high probability depends on the MIS algorithm that is used as a black-box. Our results: 1) A deterministic O(MIS(n,Δ)/ε)-round algorithm that finds a (1+ε)Δ-approximation for MaxIS in the CONGEST model. 2) A randomized (poly(log log n)/ε)-round algorithm that finds, with high probability, a (1+ε)Δ-approximation for MaxIS in the CONGEST model. That is, by sacrificing only a tiny fraction of the approximation guarantee, we achieve an exponential speed-up in the running time over the previous best known result. 3) A randomized O(log n⋅ poly(log log n)/ε)-round algorithm that finds, with high probability, a 8(1+ε)α-approximation for MaxIS in the CONGEST model, where α is the arboricity of the graph. For graphs of arboricity α < Δ/(8(1+ε)), this result improves upon the previous best known result in both the approximation factor and the running time. One may wonder whether it is possible to approximate MaxIS with high probability in fewer than poly(log log n) rounds. Interestingly, a folklore randomized ranking algorithm by Boppana implies a single round algorithm that gives an expected Δ-approximation in the CONGEST model. However, it is unclear how to convert this algorithm to one that succeeds with high probability without sacrificing a large number of rounds. For unweighted graphs of maximum degree Δ ≤ n/log n, we show a new analysis of the randomized ranking algorithm, which we combine with the local-ratio technique, to provide a O(1/ε)-round algorithm in the CONGEST model that, with high probability, finds an independent set of size at least n/((1+ε)(Δ+1)). This result cannot be extended to very high degree graphs, as we show a lower bound of Ω(log^*n) rounds for any randomized algorithm that with probability at least 1-1/log n finds an independent set of size Ω(n/Δ). This lower bound holds even for the LOCAL model. The hard instances that we use to prove our lower bound are graphs of maximum degree Δ = Ω(n/log^*n).

The minimum violation problem asks for a vertex map from a digraph to a pattern digraph that minimizes violation, the total weight of the edges not mapped to an edge. We are interested in surjective mappings. We characterize all patterns where a minimum violation map that fixes some vertices can be computed in polynomial time. We also make progress in the case where we do not fix any vertex in the mapping, including when the digraph is disconnected, when the graph is in the variety of finite paths. Moreover, we obtain a dichotomy result for trees. We apply the result to some cut problems, including $k$-cut with size lower bounds and length bounded $k$-cuts.

We study the model-checking problem for first- and monadic second-order logic on finite relational structures. The problem of verifying whether a formula of these logics is true on a given structure is considered intractable in general, but it does become tractable on interesting classes of structures, such as on classes whose Gaifman graphs have bounded treewidth. In this article, we continue this line of research and study model-checking for first- and monadic second-order logic in the presence of an ordering on the input structure. We do so in two settings: the general ordered case, where the input structures are equipped with a fixed order or successor relation, and the order-invariant case, where the formulas may resort to an ordering, but their truth must be independent of the particular choice of order. In the first setting we show very strong intractability results for most interesting classes of structures. In contrast, in the order-invariant case we obtain tractability results for order-invariant monadic second-order formulas on the same classes of graphs as in the unordered case. For first-order logic, we obtain tractability of successor-invariant formulas on classes whose Gaifman graphs have bounded expansion. Furthermore, we show that model-checking for order-invariant first-order formulas is tractable on coloured posets of bounded width.

We formulate a new stochastic submodular maximization problem by introducing the performance-dependent costs of items. In this problem, we consider selecting items for the case where the performance of each item (i.e., how much an item contributes to the objective function) is decided randomly, and the cost of an item depends on its performance. The goal of the problem is to maximize the objective function subject to a budget constraint on the costs of the selected items. We present an adaptive algorithm for this problem with a theoretical guaran-√ tee that its expected objective value is at least (1−1/ 4 e)/2 times the maximum value attained by any adaptive algorithms. We verify the performance of the algorithm through numerical experiments.

Cross-lingual word embeddings (CLWE) underlie many multilingual natural language processing systems, often through orthogonal transformations of pre-trained monolingual embeddings.However, orthogonal mapping only works on language pairs whose embeddings are naturally isomorphic.For nonisomorphic pairs, our method (Iterative Normalization) transforms monolingual embeddings to make orthogonal alignment easier by simultaneously enforcing that (1) individual word vectors are unit length, and (2) each language's average vector is zero.Iterative Normalization consistently improves word translation accuracy of three CLWE methods, with the largest improvement observed on English-Japanese (from 2% to 44% test accuracy).

We propose computationally efficient algorithms for \textit{online linear optimization with bandit feedback}, in which a player chooses an \textit{action vector} from a given (possibly infinite) set $\mathcal{A} \subseteq \mathbb{R}^d$, and then suffers a loss that can be expressed as a linear function in action vectors. Although existing algorithms achieve an optimal regret bound of $\tilde{O}(\sqrt{T})$ for $T$ rounds (ignoring factors of $\mathrm{poly} (d, \log T)$), computationally efficient ways of implementing them have not yet been specified, in particular when $|\mathcal{A}|$ is not bounded by a polynomial size in $d$. A standard way to pursue computational efficiency is to assume that we have an efficient algorithm referred to as \textit{oracle} that solves (offline) linear optimization problems over $\mathcal{A}$. Under this assumption, the computational efficiency of a bandit algorithm can then be measured in terms of \textit{oracle complexity}, i.e., the number of oracle calls. Our contribution is to propose algorithms that offer optimal regret bounds of $\tilde{O}(\sqrt{T})$ as well as low oracle complexity for both \textit{non-stochastic settings} and \textit{stochastic settings}. Our algorithm for non-stochastic settings has an oracle complexity of $\tilde{O}( T )$ and is the first algorithm that achieves both a regret bound of $\tilde{O}( \sqrt{T} )$ and an oracle complexity of $\tilde{O} ( \mathrm{poly} ( T ) )$, given only linear optimization oracles. Our algorithm for stochastic settings calls the oracle only $O( \mathrm{poly} (d, \log T))$ times, which is smaller than the current best oracle complexity of $O( T )$ if $T$ is sufficiently large.

\textit{Bandit combinatorial optimization} is a bandit framework in which a player chooses an action within a given finite set $\mathcal{A} \subseteq \{ 0, 1 \}^d$ and incurs a loss that is the inner product of the chosen action and an unobservable loss vector in $\mathbb{R} ^ d$ in each round. In this paper, we aim to reveal the property, which makes the bandit combinatorial optimization hard. Recently, Cohen et al.~\citep{cohen2017tight} obtained a lower bound $\Omega(\sqrt{d k^3 T / \log T})$ of the regret, where $k$ is the maximum $\ell_1$-norm of action vectors, and $T$ is the number of rounds. This lower bound was achieved by considering a continuous strongly-correlated distribution of losses. Our main contribution is that we managed to improve this bound by $\Omega( \sqrt{d k ^3 T} )$ through applying a factor of $\sqrt{\log T}$, which can be done by means of strongly-correlated losses with \textit{binary} values. The bound derives better regret bounds for three specific examples of the bandit combinatorial optimization: the multitask bandit, the bandit ranking and the multiple-play bandit. In particular, the bound obtained for the bandit ranking in the present study addresses an open problem raised in \citep{cohen2017tight}. In addition, we demonstrate that the problem becomes easier without considering correlations among entries of loss vectors. In fact, if each entry of loss vectors is an independent random variable, then, one can achieve a regret of $\tilde{O}(\sqrt{d k^2 T})$, which is $\sqrt{k}$ times smaller than the lower bound shown above. The observed results indicated that correlation among losses is the reason for observing a large regret.

We present a time-optimal deterministic distributed algorithm for approximating a minimum weight vertex cover in hypergraphs of rank ƒ. This problem is equivalent to the Minimum Weight Set Cover problem in which the frequency of every element is bounded by ƒ. The approximation factor of our algorithm is (ƒ + ε). Let Δ denote the maximum degree in the hypergraph. Our algorithm runs in the CONGEST model and requires O(log Δ/log log Δ) rounds, for constants ε ∈ (0,1] and ƒ ∈ N+. This is the first distributed algorithm for this problem whose running time does not depend on the vertex weights nor the number of vertices. Thus adding another member to the exclusive family of emphprovably optimal distributed algorithms.

Accurate estimation of Intrinsic Dimensionality (ID) is of crucial importance in many data mining and machine learning tasks, including dimensionality reduction, outlier detection, similarity search and subspace clustering. However, since their convergence generally requires sample sizes (that is, neighborhood sizes) on the order of hundreds of points, existing ID estimation methods may have only limited usefulness for applications in which the data consists of many natural groups of small size. In this paper, we propose a local ID estimation strategy stable even for ‘tight’ localities consisting of as few as 20 sample points. The estimator applies MLE techniques over all available pairwise distances among the members of the sample, based on a recent extreme-value-theoretic model of intrinsic dimensionality, the Local Intrinsic Dimension (LID). Our experimental results show that our proposed estimation technique can achieve notably smaller variance, while maintaining comparable levels of bias, at much smaller sample sizes than state-of-the-art estimators.

The grid theorem, originally proved by Robertson and Seymour in 1986 [RS10, Graph Minors V], is one of the most central results in the study of graph minors and has found many algorithmic applications, especially in the analysis of routing problems. The relation between treewidth and grid minors is particularly tight for planar graphs, as every planar graph of treewidth at least 6k contains a grid of order k as a minor [RST94]. This polynomial, in fact linear, bound on the size of grid minors has enabled many important consequences, such as sublinear separators and subexponential algorithms for many NP-hard problems on planar graphs. In the mid-90s, Reed and Johnson, Robertson, Seymour and Thomas proposed a notion of directed treewidth and conjectured an excluded grid theorem for directed graphs. This theorem was proved in 2015 [KK15] by the latter two authors but the function relating directed treewidth and grid minors is very big, even in the planar case. Directed grids have found several algorithmic applications such as low-congestion routing. See e.g. [CE15, CEP16, KKK14, EMW16, AKKW16]. However, in the undirected case the polynomial, in fact linear, bound on the size of grid minors in planar graphs have made this tool so extremely successful. Consequently, the lack of polynomial bounds for directed grid minors in planar digraphs has so far prevented further applications of this technique in the directed setting. The main result of this paper is to close this gap and to establish a polynomial bound for the directed grid theorem on planar digraphs. We are optimistic that this will enable further applications of directed treewidth and its dual notion of directed grids in the context of planar digraphs. Towards the end, we also give “treewidth sparsifier” for directed graphs, which has been already considered in undirected graphs. This result allows us to obtain an Eulerian subgraph of bounded degree in D that still has high directed treewidth. We believe this result is of independent interest for structural graph theory.

Computing the Euler genus of a graph is a fundamental problem in algorithmic graph theory. It has been shown to be NP-hard by [Thomassen ’89, Thomassen ’97], even for cubic graphs, and a linear-time fixed-parameter algorithm has been obtained by [Mohar ’99]. Despite extensive study, the approximability of the Euler genus remains wide open. While the existence of an O(1)-approximation is not ruled out, the currently best-known upper bound is a O(n1−α)-approximation, for some universal constant α>0 [Kawarabayashi and Sidiropoulos 2017].

In this work, we initiate a thorough study of parameterized graph optimization problems in the distributed setting. In a parameterized problem, an algorithm decides whether a solution of size bounded by a \emph{parameter} $k$ exists and if so, it finds one. We study fundamental problems, including Minimum Vertex Cover (MVC), Maximum Independent Set (MaxIS), Maximum Matching (MaxM), and many others, in both the LOCAL and CONGEST distributed computation models. We present lower bounds for the round complexity of solving parameterized problems in both models, together with optimal and near-optimal upper bounds. Our results extend beyond the scope of parameterized problems. We show that any LOCAL $(1+ε)$-approximation algorithm for the above problems must take $Ω(ε^{-1})$ rounds. Joined with the algorithm of [GKM17] and the $Ω(\sqrt{\frac{\log n}{\log\log n}})$ lower bound of [KMW16], this settles the complexity of $(1+ε)$-approximating MVC, MaxM and MaxIS at $(ε^{-1}\log n)^{Θ(1)}$. We also show that our parameterized approach reduces the runtime of exact and approximate CONGEST algorithms for MVC and MaxM if the optimal solution is small, without knowing its size beforehand. Finally, we propose the first deterministic $o(n^2)$ rounds CONGEST algorithms that approximate MVC and MaxM within a factor strictly smaller than $2$.

We present a deterministic algorithm that computes the edge-connectivity of a graph in near-linear time. This is for a simple undirected unweighted graph G with n vertices and m edges. This is the first o ( mn ) time deterministic algorithm for the problem. Our algorithm is easily extended to find a concrete minimum edge-cut. In fact, we can construct the classic cactus representation of all minimum cuts in near-linear time. The previous fastest deterministic algorithm by Gabow from STOC '91 took Õ( m +λ 2 n ), where λ is the edge connectivity, but λ can be as big as n −1. Karger presented a randomized near-linear time Monte Carlo algorithm for the minimum cut problem at STOC’96, but the returned cut is only minimum with high probability. Our main technical contribution is a near-linear time algorithm that contracts vertex sets of a simple input graph G with minimum degree Δ, producing a multigraph Ḡ with Õ( m /Δ) edges, which preserves all minimum cuts of G with at least two vertices on each side. In our deterministic near-linear time algorithm, we will decompose the problem via low-conductance cuts found using PageRank a la Brin and Page (1998), as analyzed by Andersson, Chung, and Lang at FOCS’06. Normally, such algorithms for low-conductance cuts are randomized Monte Carlo algorithms, because they rely on guessing a good start vertex. However, in our case, we have so much structure that no guessing is needed.

Co-occurrences between two words provide useful insights into the semantics of those words.Consequently, numerous prior work on word embedding learning has used co-occurrences between two wordsas the training signal for learning word embeddings.However, in natural language texts it is common for multiple words to be related and co-occurring in the same context.We extend the notion of co-occurrences to cover k(≥2)-way co-occurrences among a set of k-words.Specifically, we prove a theoretical relationship between the joint probability of k(≥2) words, and the sum of l_2 norms of their embeddings. Next, we propose a learning objective motivated by our theoretical resultthat utilises k-way co-occurrences for learning word embeddings.Our experimental results show that the derived theoretical relationship does indeed hold empirically, anddespite data sparsity, for some smaller k(≤5) values, k-way embeddings perform comparably or better than 2-way embeddings in a range of tasks.

We investigate an online regression problem in which the learner makes predictions sequentially while only the limited information on features is observable. In this paper, we propose a general setting for the limitation of the available information, where the observed information is determined by a function chosen from a given set of observation functions. Our problem setting is a generalization of the online sparse linear regression problem, which has been actively studied. For our general problem, we present an algorithm by combining multi-armed bandit algorithms and online learning methods. This algorithm admits a sublinear regret bound when the number of observation functions is constant. We also show that the dependency on the number of observation functions is inevitable unless additional assumptions are adopted. To mitigate this inefficiency, we focus on a special case of practical importance, in which the observed information is expressed through linear combinations of the original features. We propose efficient algorithms for this special case. Finally, we also demonstrate the efficiency of the proposed algorithms by simulation studies using both artificial and real data.

Recent deep learning approaches for representation learning on graphs follow a neighborhood aggregation procedure. We analyze some important properties of these models, and propose a strategy to overcome those. In particular, the range of "neighboring" nodes that a node’s representation draws from strongly depends on the graph structure, analogous to the spread of a random walk. To adapt to local neighborhood properties and tasks, we explore an architecture – jumping knowledge (JK) networks – that flexibly leverages, for each node, different neighborhood ranges to enable better structure-aware representation. In a number of experiments on social, bioinformatics and citation networks, we demonstrate that our model achieves state-of-the-art performance. Furthermore, combining the JK framework with models like Graph Convolutional Networks, GraphSAGE and Graph Attention Networks consistently improves those models’ performance.

Bandit is a framework for designing sequential experiments, where a learner selects an arm $A \in \mathcal{A}$ and obtains an observation corresponding to $A$ in each experiment. Theoretically, the tight regret lower-bound for the general bandit is polynomial with respect to the number of arms $|\mathcal{A}|$, and thus, to overcome this bound, the bandit problem with side-information is often considered. Recently, a bandit framework over a causal graph was introduced, where the structure of the causal graph is available as side-information and the arms are identified with interventions on the causal graph. Existing algorithms for causal bandit overcame the $\Omega(\sqrt{|\mathcal{A}|/T})$ simple-regret lower-bound; however, their algorithms work only when the interventions $\mathcal{A}$ are localized around a single node (i.e., an intervention propagates only to its neighbors). We then propose a novel causal bandit algorithm for an arbitrary set of interventions, which can propagate throughout the causal graph. We also show that it achieves $O(\sqrt{ \gamma^*\log(|\mathcal{A}|T) / T})$ regret bound, where $\gamma^*$ is determined by using a causal graph structure. In particular, if the maximum in-degree of the causal graph is a constant, then $\gamma^* = O(N^2)$, where $N$ is the number of nodes.

Distributed word embeddings have shown superior performances in numerous Natural Language Processing (NLP) tasks. However, their performances vary significantly across different tasks, implying that the word embeddings learnt by those methods capture complementary aspects of lexical semantics. Therefore, we believe that it is important to combine the existing word embeddings to produce more accurate and complete meta-embeddings of words. For this purpose, we propose an unsupervised locally linear meta-embedding learning method that takes pre-trained word embeddings as the input, and produces more accurate meta embeddings. Unlike previously proposed meta-embedding learning methods that learn a global projection over all words in a vocabulary, our proposed method is sensitive to the differences in local neighbourhoods of the individual source word embeddings. Moreover, we show that vector concatenation, a previously proposed highly competitive baseline approach for integrating word embeddings, can be derived as a special case of the proposed method. Experimental results on semantic similarity, word analogy, relation classification, and short-text classification tasks show that our meta-embeddings to significantly outperform prior methods in several benchmark datasets, establishing a new state of the art for meta-embeddings.

Online portfolio selection is a sequential decision-making problem in which a learner repetitively selects a portfolio over a set of assets, aiming to maximize long-term return. In this paper, we study the problem with the cardinality constraint that the number of assets in a portfolio is restricted to be at most k, and consider two scenarios: (i) in the full-feedback setting, the learner can observe price relatives (rates of return to cost) for all assets, and (ii) in the bandit-feedback setting, the learner can observe price relatives only for invested assets. We propose efficient algorithms for these scenarios that achieve sublinear regrets. We also provide regret (statistical) lower bounds for both scenarios which nearly match the upper bounds when k is a constant. In addition, we give a computational lower bound which implies that no algorithm maintains both computational efficiency, as well as a small regret upper bound.

Treedepth is a well-studied graph invariant in the family of “width measures” that includes treewidth and pathwidth. Understanding these invariants in terms of excluded minors has been an active area of research. The recent Grid Minor Theorem of Chekuri and Chuzhoy [12] establishes that treewidth is polynomially approximated by the largest k × k grid minor. In this paper, we give a similar polynomial excluded-minor approximation for treedepth in terms of three basic obstructions: grids, tree, and paths. Specifically, we show that there is a constant c such that every graph of treedepth ≥ kc contains one of the following minors (each of treedepth ≥ k): the k × k grid, the complete binary tree of height k, the path of order 2k. Let us point out that we cannot drop any of the above graphs for our purpose. Moreover, given a graph G we can, in randomized polynomial time, find either an embedding of one of these minors or conclude that treedepth of G is at most kc. This result has potential applications in a variety of settings where bounded treedepth plays a role. In addition to some graph structural applications, we describe a surprising application in circuit complexity and finite model theory from recent work of the second author [28].

Algorithmic problems of computing influence estimation and influence maximization have been actively researched for decades. We developed a novel algorithm, NoSingles, based on the Reverse Influence Sampling method proposed by Borgs et al. in 2013. NoSingles solves the problem of influence maximization in large graphs using much smaller space than the existing state-of-the-art algorithms while preserving the theoretical guarantee of the approximation of (1 - 1/e - ϵ) of the optimum, for any ϵ > 0. The NoSingles data structure is saved on the hard drive of the machine, and can be used repeatedly for playing out "what if" scenarios (e.g. trying different combination of seeds and calculating the influence spread). We also introduce a variation of NoSingles algorithm, which further decreases the running time, while preserving the approximation guarantee. We support our claims with extensive experiments on large real-world graphs. Savings in required space allow to successfully run NoSingles on a consumer-grade laptop for graphs with tens of millions of vertices and hundreds of millions of edges.

It is a well known fact that sequential algorithms which exhibit a strong "local" nature can be adapted to the distributed setting given a legal graph coloring. The running time of the distributed algorithm will then be at least the number of colors. Surprisingly, this well known idea was never formally stated as a unified framework. In this paper we aim to define a robust family of local sequential algorithms which can be easily adapted to the distributed setting. We then develop new tools to further enhance these algorithms, achieving state of the art results for fundamental problems. We define a simple class of greedy-like algorithms which we call \emph{orderless-local} algorithms. We show that given a legal $c$-coloring of the graph, every algorithm in this family can be converted into a distributed algorithm running in $O(c)$ communication rounds in the CONGEST model. We show that this family is indeed robust as both the method of conditional expectations and the unconstrained submodular maximization algorithm of Buchbinder \etal \cite{BuchbinderFNS15} can be expressed as orderless-local algorithms for \emph{local utility functions} --- Utility functions which have a strong local nature to them. We use the above algorithms as a base for new distributed approximation algorithms for the weighted variants of some fundamental problems: Max $k$-Cut, Max-DiCut, Max 2-SAT and correlation clustering. We develop algorithms which have the same approximation guarantees as their sequential counterparts, up to a constant additive $ε$ factor, while achieving an $O(\log^* n)$ running time for deterministic algorithms and $O(ε^{-1})$ running time for randomized ones. This improves exponentially upon the currently best known algorithms.

We study the following all-or-nothing multicommodity flow problem in planar graphs: Input: A graph $G$ with $n$ vertices and $k$ pairs of vertices $(s_1,t_1),(s_2,t_2),\dots, (s_k,t_k)$ in $G$. Find: A largest subset $W$ of $\{1,\dots,k\}$ such that for every $i$ in $W$, we can send one unit of flow between $s_i$ and $t_i$. This problem is different from the well-known maximum edge-disjoint paths problem in that we do not require integral flows for the pairs. This problem is APX-hard even for trees, and a 2-approximation algorithm is known for trees. For general graphs, Chekuri, Khanna, and Shepherd [ SIAM J. Comput., 42 (2013), pp. 1467--1493] give a polylogarithmic factor approximation algorithm and show that a natural LP-relaxation has a polylogarithmic integrality gap. This result is in contrast with the integrality gap $\Omega(\sqrt{n})$ for the maximum edge-disjoint paths problem. Our main result considerably strengthens this result when an input graph is planar. Namely, for the all-or-nothing multicommodity flow problem in planar graphs, we give an $O(1)$-approximation algorithm and show that the integrality gap is $O(1)$. In particular, in polynomial time, we can find an index set $W$ with $|W| = \Omega({OPT})$ and eight $s_i$-$t_i$ paths for each $i \in W$ such that each edge is used at most eight times in these paths (with multiplicity), where OPT is the optimal value of the LP-relaxation of the all-or-nothing multicommodity flow problem. Our result can be compared to the result by Séguin-Charbonneau and Shepherd [ Proceedings of FOCS, 2011, pp. 200--209], who give an $O(1)$-approximation algorithm for the maximum edge-disjoint paths problem in planar graphs with congestion 2 (but not implied by this result).

Short and sparse texts such as tweets, search engine snippets, product reviews, and chat messages are abundant on the Web. Classifying such short-texts into a pre-defined set of categories is a common problem that arises in various contexts, such as sentiment classification, spam detection, and information recommendation. The fundamental problem in short-text classification is feature sparseness -- the lack of feature overlap between a trained model and a test instance to be classified. We propose ClassiNet -- a network of classifiers trained for predicting missing features in a given instance, to overcome the feature sparseness problem. Using a set of unlabeled training instances, we first learn binary classifiers as feature predictors for predicting whether a particular feature occurs in a given instance. Next, each feature predictor is represented as a vertex v i in the ClassiNet, where a one-to-one correspondence exists between feature predictors and vertices. The weight of the directed edge e ij connecting a vertex v i to a vertex v j represents the conditional probability that given v i exists in an instance, v j also exists in the same instance. We show that ClassiNets generalize word co-occurrence graphs by considering implicit co-occurrences between features. We extract numerous features from the trained ClassiNet to overcome feature sparseness. In particular, for a given instance x , we find similar features from ClassiNet that did not appear in x , and append those features in the representation of x . Moreover, we propose a method based on graph propagation to find features that are indirectly related to a given short-text. We evaluate ClassiNets on several benchmark datasets for short-text classification. Our experimental results show that by using ClassiNet, we can statistically significantly improve the accuracy in short-text classification tasks, without having to use any external resources such as thesauri for finding related features.

We propose a scalable and efficient algorithm for coclustering a higher-order tensor. Viewing tensors with hypergraphs, we propose formulating the co-clustering of a tensor as a problem of partitioning the corresponding hypergraph. Our algorithm is based on the random sampling technique, which has been successfully applied to graph cut problems. We extend a random sampling algorithm for the graph multiwaycut problem to hypergraphs, and design a co-clustering algorithm based on it. Each iteration of our algorithm runs in polynomial on the size of hypergraphs, and thus it performs well even for higher-order tensors, which are difficult to deal with for state-of-the-art algorithm.

The optimal pricing problem is a fundamental problem that arises in combinatorial auctions. Suppose that there is one seller who has indivisible items and multiple buyers who want to purchase a combination of the items. The seller wants to sell his items for the highest possible prices, and each buyer wants to maximize his utility (i.e., valuation minus payment) as long as his payment does not exceed his budget. The optimal pricing problem seeks a price of each item and an assignment of items to buyers such that every buyer achieves the maximum utility under the prices. The goal of the problem is to maximize the total payment from buyers. In this paper, we consider the case that the valuations are submodular. We show that the problem is computationally hard even if there exists only one buyer. Then we propose approximation algorithms for the unlimited budget case. We also extend the algorithm for the limited budget case when there exists one buyer and multiple buyers collaborate with each other.

In the minimum planarization problem, given some n-vertex graph, the goal is to find a set of vertices of minimum cardinality whose removal leaves a planar graph. This is a fundamental problem in topological graph theory. We present a logO(1)n-approximation algorithm for this problem on general graphs with running time nO(log n/log log n). We also obtain a O(nε)-approximation with running time nO(1/ε)for any arbitrarily small constant ε > 0. Prior to our work, no non-trivial algorithm was known for this problem on general graphs, and the best known result even on graphs of bounded degree was a nΩ(1)-approximation [1]. As an immediate corollary, we also obtain improved approximation algorithms for the crossing number problem on graphs of bounded degree. Specifically, we obtain O(n1/2+ε)approximation and n1/2 logO(1)n-approximation algorithms in time nO(1/ε)and nO(log n/log log n)respectively. The previously best-known result was a polynomial-time n9/10logO(1)n-approximation algorithm [2]. Our algorithm introduces several new tools including an efficient grid-minor construction for apex graphs, and a new method for computing irrelevant vertices. Analogues of these tools were previously available only for exact algorithms. Our work gives efficient implementations of these ideas in the setting of approximation algorithms, which could be of independent interest.

This paper focuses on a generalization of the traveling salesman problem (TSP), called the subpath planning problem (SPP). Given 2n vertices and n independent edges on a metric space, we aim to find a shortest tour that contains all the edges. SPP is one of the fundamental problems in both artificial intelligence and robotics. Our main result is to design a 1.5-approximation algorithm that runs in polynomial time, improving the currently best approximation algorithm. The idea is direct use of techniques developed for TSP. In addition, we propose a generalization of SPP called the subgroup planning problem (SGPP). In this problem, we are given a set of disjoint groups of vertices, and we aim to find a shortest tour such that all the vertices in each group are traversed sequentially. We propose a 3-approximation algorithm for SGPP. We also conduct numerical experiments. Compared with previous algorithms, our algorithms improve the solution quality by more than 10% for large instances with more than 10,000 vertices.

Online sparse linear regression is the task of applying linear regression analysis to examples arriving sequentially subject to a resource constraint that a limited number of features of examples can be observed. Despite its importance in many practical applications, it has been recently shown that there is no polynomial-time sublinear-regret algorithm unless NP$\subseteq$BPP, and only an exponential-time sublinear-regret algorithm has been found. In this paper, we introduce mild assumptions to solve the problem. Under these assumptions, we present polynomial-time sublinear-regret algorithms for the online sparse linear regression. In addition, thorough experiments with publicly available data demonstrate that our algorithms outperform other known algorithms.

Fueled by the increasing popularity of online social networks, social influence analysis has attracted a great deal of research attention in the past decade. The diffusion process is often modeled using influence graphs, and there has been a line of research that involves algorithmic problems in influence graphs. However, the vast size of today's real-world networks raises a serious issue with regard to computational efficiency.

We consider the problem of coloring a 3-colorable graph in polynomial time using as few colors as possible. We first present a new combinatorial algorithm using Õ ( n 4/11 ) colors. This is the first combinatorial improvement since Blum’s Õ ( n 3/8 ) bound from FOCS’90. Like Blum’s algorithm, our new algorithm composes immediately with recent semi-definite programming approaches, and improves the best bound for the polynomial time algorithm for the coloring of 3-colorable graphs from O ( n 0.2072 ) colors by Chlamtac from FOCS’07 to O ( n 0.2049 ) colors. Next, we develop a new recursion tailored for combination with semi-definite approaches, bringing us further down to O ( n 0.19996 ) colors.

In this paper, we show the Erdös--Pósa property for edge-disjoint packing of $S$-closed walks with parity constraints in 4-edge-connected graphs. More precisely, we prove that for any 4-edge-connected graph $G$ and any vertex subset $S$, either $G$ has $k$ edge-disjoint elementary closed odd walks, each of which has at least one vertex of $S$, or $G$ has an edge set $F$ with $|F| \leq f(k)$ such that $G-F$ has no such walks. The 4-edge-connectivity is the best possible in the sense that 3-edge-connected graphs do not satisfy the statement. Since the proof is constructive, we can design a fixed-parameter algorithm for finding $k$ edge-disjoint walks satisfying the conditions in a 4-edge-connected graph for a parameter $k$. In addition, this gives a simple fixed-parameter algorithm for the parity edge-disjoint walks problem with $k$ terminal pairs.

Methods for learning word representations using large text corpora have received much attention lately due to their impressive performancein numerous natural language processing (NLP) tasks such as, semantic similarity measurement, and word analogy detection.Despite their success, these data-driven word representation learning methods do not considerthe rich semantic relational structure between words in a co-occurring context. On the other hand, already much manual effort has gone into the construction of semantic lexicons such as the WordNetthat represent the meanings of words by defining the various relationships that exist among the words in a language.We consider the question, can we improve the word representations learnt using a corpora by integrating theknowledge from semantic lexicons?. For this purpose, we propose a joint word representation learning method that simultaneously predictsthe co-occurrences of two words in a sentence subject to the relational constrains given by the semantic lexicon.We use relations that exist between words in the lexicon to regularize the word representations learnt from the corpus.Our proposed method statistically significantly outperforms previously proposed methods for incorporating semantic lexicons into wordrepresentations on several benchmark datasets for semantic similarity and word analogy.

In this study, we investigate expected CP decomposition — a special case of CP decomposition in which a tensor to be decomposed is given as the sum or average of tensor samples X(t) for t = 1,...,T. To determine this decomposition, we develope stochastic-gradient-descent-type algorithms with four appealing features: efficient memory use, ability to work in an online setting, robustness of parameter tuning, and simplicity. Our theoretical analysis show that the solutions do not diverge to infinity for any initial value or step size. Experimental results confirm that our algorithms significantly outperform all existing methods in terms of accuracy. We also show that they can successfully decompose a large tensor, containing billion-scale nonzero elements.

The distance between vertices is one of the most fundamental measures for representing relations between them, and it is the basis of other classic measures of vertices, such as similarity, centrality, and influence. The 2-hop labeling methods are known as the fastest exact point-to-point distance algorithms on million-scale networks. However, they cannot handle billion-scale networks because of the large space requirement and long preprocessing time. In this paper, we present the first algorithm that can process exact distance queries on fully dynamic billion-scale networks besides trivial non-indexing algorithms, which combines an online bidirectional breadth-first search (BFS) and an offline indexing method for handling billion-scale networks in memory. First, we accelerate bidirectional BFSs by using heuristics that exploit the small-world property of complex networks. Then, we construct bit-parallel shortest-path trees to maintain sets of shortest paths passing through high-degree vertices of networks in compact form, the information of which enables us to avoid visiting vertices with high degrees during bidirectional BFSs. Thus, the searches achieve considerable speedup. In addition, our index size reduction technique enables us to handle billion-scale networks in memory. Furthermore, we introduce dynamic update procedures of our data structure to handle fully dynamic networks. We evaluated the performance of the proposed method on real-world networks. In particular, on large-scale social networks with over 1B edges, the proposed method enables us to answer distance queries in around 1 ms, on average.

We show that the model-checking problem for successor-invariant first-order logic is fixed-parameter tractable on graphs with excluded topological subgraphs when parameterised by both the size of the input formula and the size of the exluded topological subgraph. Furthermore, we show that model-checking for order-invariant first-order logic is tractable on coloured posets of bounded width, parameterised by both the size of the input formula and the width of the poset. Our result for successor-invariant FO extends previous results for this logic on planar graphs (Engelmann et al., LICS 2012) and graphs with excluded minors (Eickmeyer et al., LICS 2013), further narrowing the gap between what is known for FO and what is known for successor-invariant FO. The proof uses Grohe and Marx's structure theorem for graphs with excluded topological subgraphs. For order-invariant FO we show that Gajarský et al.'s recent result for FO carries over to order-invariant FO.

We propose the first real-time fully-dynamic index data structure designed for influence analysis on evolving networks. With this aim, we carefully redesign the data structure of the state-of-the-art sketching method introduced by Borgs et al. , and construct corresponding update algorithms. Using this index, we present algorithms for two kinds of queries, influence estimation and influence maximization , which are strongly motivated by practical applications, such as viral marketing. We provide a thorough theoretical analysis, which guarantees the non-degeneracy of the solution accuracy after an arbitrary number of updates. Furthermore, we introduce a reachability-tree-based technique and a skipping method , which greatly reduce the time consumption required for edge/vertex deletions and vertex additions, respectively, and counter-based random number generators , which improve the space efficiency. Experimental evaluations using real dynamic networks with tens of millions of edges demonstrate the efficiency, scalability, and accuracy of our proposed indexing scheme. Specifically, it can reflect a graph modification within a time of several orders of magnitude smaller than that required to reconstruct an index from scratch, estimate the influence spread of a vertex set accurately within a millisecond, and select highly influential vertices at least ten times faster than state-of-the-art static algorithms.

The problem on the Hamiltonicity of graphs is well studied in discrete algorithm and graph theory because of its relation to the traveling salesman problem. Starting with Tutte's result, stating that every 4-connected planar graph is Hamiltonian, several researchers have studied the Hamiltonicity of graphs on surfaces. Extending Tutte's technique, Thomassen proved that every 4-connected planar graph is in fact Hamiltonian-connected, i.e., there is a Hamiltonian path connecting any two prescribed vertices. For graphs on the torus, Thomas and Yu showed that every 5-connected graph on the torus has a Hamiltonian cycle. In this paper, we prove the following result which generalizes Thomas and Yu's result. Every 5-connected graph on the torus is Hamiltonian-connected. Our result is best possible in the sense that we cannot lower the connectivity 5 (i.e., there is a 4-connected graph on the torus which is not Hamiltonian-connected). Moreover, our proof is constructive in a sense that it gives rise to a polynomial time (indeed $O(n^2)$-time) algorithm to construct a Hamiltonian path between any two specified vertices, if an input graph is a 5-connected graph on the torus.

In the maximum edge-disjoint paths problem, we are given a graph and a collection of pairs of vertices, and the objective is to find the maximum number of pairs that can be routed by edge-disjoint paths. An r -approximation algorithm for this problem is a polynomial-time algorithm that finds at least OPT/ r edge-disjoint paths, where OPT denotes the maximum possible number of pairs that can be routed in a given instance. For a long time, an O ( n 1/2 -approximation algorithm has been best known for this problem even if a congestion of two is allowed, that is, each edge is allowed to be used in at most two of the paths. In this article, we give a randomized O ( n 3/7 ċ poly(log n ))-approximation algorithm with congestion two. This is the first result that breaks the O ( n 1/2 )-approximation algorithm. In particular, we prove the following: (1) If we have a (randomized) polynomial-time algorithm for finding Ω(OPT1/p /polylog( n )) edge-disjoint paths for some p > 1, then we can give a randomized O ( n 1/2 -α)-approximation algorithm for the edge-disjoint paths problem by using Rao-Zhou’s algorithm for some α > 0. (2) Based on the Chekuri-Khanna-Shepherd well-linked decomposition, we show that there is a randomized algorithm for finding Ω(OPT 1/4 /(log n ) 3/2 ) edge-disjoint paths connecting given terminal pairs with congestion two. Our framework for this algorithm is more general in the following sense. Indeed, the above two ingredients also work for the maximum edge-disjoint paths problem (with congestion one) if there is a (randomized) polynomial-time algorithm for finding Ω(OPT1/p) edge-disjoint paths connecting given terminal pairs for some p > 1.

Attributes of words and relations between two words are central to numerous tasks in Artificial Intelligence such as knowledge representation, similarity measurement, and analogy detection. Often when two words share one or more attributes in common, they are con- nected by some semantic relations. On the other hand, if there are numerous semantic relations between two words, we can expect some of the attributes of one of the words to be inherited by the other. Motivated by this close connection between attributes and relations, given a relational graph in which words are inter-connected via numerous semantic relations, we propose a method to learn a latent representation for the individual words. The proposed method considers not only the co-occurrences of words as done by existing approaches for word representation learning, but also the semantic relations in which two words co-occur. To evaluate the accuracy of the word representations learnt using the proposed method, we use the learnt word representa- tions to solve semantic word analogy problems. Our experimental results show that it is possible to learn better word representations by using semantic semantics between words.

In this paper, we formulate a new problem related to the well-known influence maximization in the context of computational advertising. Our new problem considers allocating marketing channels (e.g., TV, newspaper, and websites) to advertisers from the view point of a match maker, which was not taken into account in previous studies on the influence maximization. The objective of the problem is to find an allocation such that each advertiser can influence some given number of customers while the slots of marketing channels are limited. We propose an algorithm based on the Lagrangian decomposition. We empirically show that our algorithm computes better quality solutions than existing algorithms, scales up to graphs of 10M vertices, and performs well particularly in a parallel environment.

Danushka Bollegala, Takanori Maehara, Ken-ichi Kawarabayashi. Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long Papers). 2015.

Similarity join finds all pairs of objects (i, j) with similarity score s(i, j) greater than some specified threshold θ. This is a fundamental query problem in the database research community, and is used in many practical applications, such as duplicate detection, merge/purge, record linkage, object matching, and reference conciliation. In this paper, we propose a scalable approximation algorithm with an arbitrary accuracy for the similarity join problem with the SimRank similarity measure. The algorithm consists of two phases: filter and verification. The filter phase enumerates similar pair candidates, and the similarity of each candidate is then assessed in the verification phase. The scalability of the proposed algorithm is experimentally verified for large real networks. The complexity depends only on the number of similar pairs, but does not depend on all pairs O(n2). The proposed algorithm scales up to the network of 5M vertices and 70M edges. By comparing the state-of-the-art algorithms, it is about 10 times faster and it requires about 10 times smaller memory.

In marketing planning, advertisers seek to maximize the number of customers by allocating given budgets to each media channel effectively. The budget allocation problem with a bipartite influence model captures this scenario; however, the model is problematic because it assumes there is only one advertiser in the market. In reality, there are many advertisers which are in conflict of advertisement; thus we must extend the model for such a case. By extending the budget allocation problem with a bipartite influence model, we propose a game-theoretic model problem that considers many advertisers. By simulating our model, we can analyze the behavior of a media channel market, e.g., we can estimate which media channels are allocated by an advertiser, and which customers are influenced by an advertiser. Our model has many attractive features. First, our model is a potential game; therefore, it has a pure Nash equilibrium. Second, any Nash equilibrium of our game has 2-optimal social utility, i.e., the price of anarchy is 2. Finally, the proposed model can be simulated very efficiently; thus it can be used to analyze large markets.

This paper is concerned with the estimation of a local measure of intrinsic dimensionality (ID) recently proposed by Houle. The local model can be regarded as an extension of Karger and Ruhl's expansion dimension to a statistical setting in which the distribution of distances to a query point is modeled in terms of a continuous random variable. This form of intrinsic dimensionality can be particularly useful in search, classification, outlier detection, and other contexts in machine learning, databases, and data mining, as it has been shown to be equivalent to a measure of the discriminative power of similarity functions. Several estimators of local ID are proposed and analyzed based on extreme value theory, using maximum likelihood estimation (MLE), the method of moments (MoM), probability weighted moments (PWM), and regularly varying functions (RV). An experimental evaluation is also provided, using both real and artificial data.

Twitter is a "what's-happening-right-now" tool that enables interested parties to follow thoughts and commentary of individual users in nearly real-time. While it is a valuable source of information for real-time topic detection and tracking, Twitter data are not clean because of noisy messages and users, which significantly diminish the reliability of obtained results.

Real-world networks, such as the World Wide Web and online social networks, are very large and are evolving rapidly. Thus tracking personalized PageRank in such evolving networks is an important challenge in network analysis and graph mining.

We consider a wireless sensor network localization problem, with range-free and anchor-free settings, i.e., each sensor can only detect which sensors are in the neighbor. We observe issues with existing algorithms that cause inaccurate localization, and propose a new decomposition-based algorithm for resolving these issues. The proposed algorithm consists of three parts: (1) decomposition of a sensor network into small networks that may have large overlap with other small networks by a randomized ball-decomposition algorithm; (2) localization of each network by MDS-MAP and physical simulation-based local refinement; (3) gluing of small networks by a divide-and-conquer algorithm. Intuitively, our algorithm finds a good localization because it finds almost optimal localization for each small graph, and moreover, it glues them together optimally. We conduct computational experiments in both synthetic and realistic setting. The proposed algorithm is more accurate, efficient, and memory-saving than existing algorithms. In fact, it accurately localizes 200,000 sensors on European region in 3 hours, whereas other existing algorithms scale only up to 10,000 sensors. Thus, the algorithm can handle problem sizes several dozen times as large as existing algorithms can.

The grid theorem, originally proved in 1986 by Robertson and Seymour in Graph Minors V, is one of the most central results in the study of graph minors. It has found numerous applications in algorithmic graph structure theory, for instance in bidimensionality theory, and it is the basis for several other structure theorems developed in the graph minors project.

Computing the Euler genus of a graph is a fundamental problem in graph theory and topology. It has been shown to be NP-hard by Thomassen [27] and a linear-time fixed-parameter algorithm has been obtained by Mohar [20]. Despite extensive study, the approximability of the Euler genus remains wide open. While the existence of a constant factor approximation is not ruled out, the currently best-known upper bound is a trivial O(n/g)-approximation that follows from bounds on the Euler characteristic.

We present a deterministic near-linear time algorithm that computes the edge-connectivity and finds a minimum cut for a simple undirected unweighted graph G with n vertices and m edges. This is the first o(mn) time deterministic algorithm for the problem. In near-linear time we can also construct the classic cactus representation of all minimum cuts.

The Traveling Tournament Problem (TTP) is a complex problem in sports scheduling whose solution is a schedule of home and away games meeting specific feasibility requirements, while minimizing the total distance traveled by all the teams. A recently-developed "hybrid" algorithm, combining local search and integer programming, has resulted in best-known solutions for many TTP instances. In this paper, we tackle the TTP from a graph-theoretic perspective, by generating a new "canonical" schedule in which each team's three-game road trips match up with the underlying graph's minimum-weight P_3-packing. By using this new schedule as the initial input for the hybrid algorithm, we develop tournament schedules for five benchmark TTP instances that beat all previously-known solutions.

Influence maximization is a problem to find small sets of highly influential individuals in a social network to maximize the spread of influence under stochastic cascade models of propagation. Although the problem has been well-studied, it is still highly challenging to find solutions of high quality in large-scale networks of the day. While Monte-Carlo-simulation-based methods produce near-optimal solutions with a theoretical guarantee, they are prohibitively slow for large graphs. As a result, many heuristic methods without any theoretical guarantee have been developed, but all of them substantially compromise solution quality. To address this issue, we propose a new method for the influence maximization problem. Unlike other recent heuristic methods, the proposed method is a Monte-Carlo-simulation-based method, and thus it consistently produces solutions of high quality with the theoretical guarantee. On the other hand, unlike other previous Monte-Carlo-simulation-based methods, it runs as fast as other state-of-the-art methods, and can be applied to large networks of the day. Through our extensive experiments, we demonstrate the scalability and the solution quality of the proposed method.

We propose a new labeling method for shortest-path and distance queries on road networks. We present a new framework (i.e. data structure and query algorithm) referred to as highway-based labelings and a preprocessing algorithm for it named pruned highway labeling. Our proposed method has several appealing features from different aspects in the literature. Indeed, we take advantages of theoretical analysis of the seminal result by Thorup for distance oracles, more detailed structures of real road networks, and the pruned labeling algorithm that conducts pruned Dijkstra's algorithm. The experimental results show that the proposed method is comparable to the previous state-of-the-art labeling method in both query time and in data size, while our main improvement is that the preprocessing time is much faster.

We consider the budget allocation problem over bipartite influence model proposed by Alon et al. This problem can be viewed as the well-known influence maximization problem with budget constraints. We first show that this problem and its much more general form fall into a general setting; namely the monotone submodular function maximization over integer lattice subject to a knapsack constraint. Our framework includes Alon et al.’s model, even with a competitor and with cost. We then give a (1-1/e)-approximation algorithm for this more general problem. Furthermore, when influence probabilities are nonincreasing, we obtain a faster (1-1/e)-approximation algorithm, which runs essentially in linear time in the number of nodes. This allows us to implement our algorithm up to almost 10M edges (indeed, our experiments tell us that we can implement our algorithm up to 1 billion edges. It would approximately take us only 500 seconds.).

SimRank, proposed by Jeh and Widom, provides a good similarity measure that has been successfully used in numerous applications.While there are many algorithms proposed for computing SimRank, their computational costs are very high.In this paper, we propose a new computational technique, "SimRank linearization," for computing SimRank, which converts the SimRank problem to a linear equation problem.By using this technique, we can solve many SimRank problems, such as single-pair compuation, single-source computation, all-pairs computation, top k searching, and similarity join problems, efficiently.

SimRank, proposed by Jeh and Widom, provides a good similarity score and has been successfully used in many of the above mentioned applications. While there are many algorithms proposed so far to compute SimRank, but unfortunately, none of them are scalable up to graphs of billions size. Motivated by this fact, we consider the following SimRank-based similarity search problem: given a query vertex u, find top-k vertices v with the k highest SimRank scores s(u,v) with respect to u.

The excluded grid theorem, originally proved by Robertson and Seymour in Graph Minors V, is one of the most central results in the study of graph minors. It has found numerous applications in algorithmic graph structure theory, for instance as the basis for bidimensionality theory on graph classes excluding a fixed minor. In 1997, Reed [22] and later Johnson, Robertson, Seymour and Thomas [16] conjectured an analogous theorem for directed graphs, i.e. the existence of a function f : ℕ → ℕ such that every digraph of directed tree-width at least f(k) contains a directed grid of order k. In an unpublished manuscript from 2001, Johnson, Robertson, Seymour and Thomas gave a proof of this conjecture for planar digraphs but no result beyond planar graphs is known to date. In this paper we prove the conjecture for the case of digraphs excluding a fixed undirected graph as a minor. For algorithmic applications our theorem is particularly interesting as it covers those classes of digraphs to which, on undirected graphs, theories based on the excluded grid theorem such as bidimensionality theory apply. We expect similar applications for directed graphs in particular to algorithmic versions of Erdős-Pósa type results and the directed disjoint paths problem.

Recognizing 3-colorable graphs is one of the most famous NP-complete problems [Garey, Johnson, and Stockmeyer, STOC'74]. The problem of coloring 3-colorable graphs in polynomial time with as few colors as possible has been intensively studied: O(n^{1/2}) colors [Wigderson, STOC'82], O(n^{2/5}) colors [Blum, STOC'89], O(n^{3/8}) colors [Blum, FOCS'90], O(n^{1/4}) colors [Karger, Motwani and Sudan, FOCS'94], O(n^{3/14})=O(n^0.2142) colors [Blum and Karger, IPL'97], O(n^{0.2111}) colors [Arora, Chlamtac, and Charikar, STOC'06], and O(n^{0.2072}) colors [Chlamtac, FOCS'07]. Recently the authors got down to O(n^{0.2049}) colors [FOCS'12]. In this paper we get down to O(n^{0.19996})=o(n^{1/5}) colors. Since 1994, the best bounds have all been obtained balancing between combinatorial and semi-definite approaches. We present a new combinatorial recursion that only makes sense in collaboration with semi-definite programming. We specifically target the worst-case for semi-definite programming: high degrees. By focusing on the interplay, we obtained the biggest improvement in the exponent since 1997.

Graph embeddings of bounded Euler genus (that means, embeddings with bounded orientable or nonorientable genus) help to design time-efficient algorithms for many graph problems. Since linear-time algorithms are known to compute embeddings of any bounded Euler genus, one can always assume to work with embedded graphs and, thus, obtain fast algorithms for many problems on any class of graphs of bounded Euler genus.

The excluded grid theorem, originally proved by Robertson and Seymour in Graph Minors V, is one of the most central results in the study of graph minors. It has found numerous applications in algorithmic graph structure theory, for instance as the basis for bidimensionality theory on graph classes excluding a fixed minor.

We propose a new scalable algorithm that can compute Personalized PageRank (PPR) very quickly. The Power method is a state-of-the-art algorithm for computing exact PPR; however, it requires many iterations. Thus reducing the number of iterations is the main challenge. We achieve this by exploiting graph structures of web graphs and social networks. The convergence of our algorithm is very fast. In fact, it requires up to 7.5 times fewer iterations than the Power method and is up to five times faster in actual computation time. To the best of our knowledge, this is the first time to use graph structures explicitly to solve PPR quickly. Our contributions can be summarized as follows. 1. We provide an algorithm for computing a tree decomposition, which is more efficient and scalable than any previous algorithm. 2. Using the above algorithm, we can obtain a core-tree decomposition of any web graph and social network. This allows us to decompose a web graph and a social network into (1) the core , which behaves like an expander graph, and (2) a small tree-width graph, which behaves like a tree in an algorithmic sense. 3. We apply a direct method to the small tree-width graph to construct an LU decomposition. 4. Building on the LU decomposition and using it as pre-conditoner , we apply GMRES method (a state-of-the-art advanced iterative method) to compute PPR for whole web graphs and social networks.

We study the following all-or-nothing multicommodity flow problem in planar graphs. Input: A graph G with n vertices and k pairs of vertices (s1, t1), (s2, t2),..., (sk, tk) in G. Find: A largest subset W of {1, ...., k such that for every i in W, we can send one unit of flow between siand ti. This problem is different from the well-known maximum edge-disjoint paths problem in that we do not require integral flows for the pairs. This problem is APX-hard even for trees, and a 2-approximation algorithm is known for trees. For general graphs, Chekuri et al. (STOC'04) give a poly-logarithmic factor approximation algorithm and show that a natural LP-relaxation has a poly-logarithmic integrality gap. This result is in contrast with the integrality gap Ω(√n) for the maximum edge-disjoint paths problem. Our main result considerably strengthens this result when an input graph is planar. Namely, for the all-or-nothing multicommodity flow problem in planar graphs, we give an O(1)-approximation algorithm and show that the integrality gap is O(1). In particular, in polynomial time, we can find an index set W with |W| = Ω(OPT) and eight si-tipaths for each i in W such that each edge is used at most eight times in these paths (with multiplicity), where OPT is the optimal value of the LP-relaxation of the all-or-nothing multicommodity flow problem. Our result can be compared to the recent result by S'eguin-Charbonneau and Shepherd (FOCS'11) who give an O(1)-approximation algorithm for the maximum edge-disjoint paths problem in planar graphs with congestion 2 (but not implied by this result).

The Traveling Tournament Problem (TTP) is a well-known NP-complete problem in sports scheduling that was inspired by the application of optimizing schedules for Major League Baseball to reduce total team travel. The techniques and heuristics from the n-team TTP can be extended to optimize the scheduling of other sports leagues, such as the Nippon Professional Baseball (NPB) league in Japan. In this paper, we describe the additional scheduling constraints required by the NPB league, such as the requirement that each team play the same number of weekend home games, weekday home games, weekend road games, and weekday road games. We fully solve this TTP-variant for the case n = 6, and conclude the paper by presenting the official 2013 NPB Central League Schedule, where we helped this Japanese baseball league reduce total team travel by over six thousand kilometres.

Model checking problems for first- and monadic second-order logic on graphs have received considerable attention in the past, not the least due to their connections to problems in algorithmic graph structure theory. While the model checking problem for these logics on general graphs is computationally intractable, it becomes tractable on important classes of graphs such as those of bounded tree-width, planar graphs or more generally, classes of graphs excluding a fixed minor. It is well known that allowing an order relation or successor function can greatly increase the expressive power of the respective logics. This remains true even in cases where we require the formulas to be order- or successor-invariant, that is, while they can use an order relation, their truth in a given graph must not depend on the particular ordering or successor function chosen. Naturally, the question arises whether this increase in expressive power comes at a cost in terms of tractability on specific classes of graphs. In LICS 2012, Engelmann et al. studied this problem and showed that order-invariant monadic second-order logic (MSO) remains tractable on the same classes of graphs than MSO without an ordering. That is, adding order-invariance to MSO essentially comes at no extra cost in terms of model checking complexity. For successor-invariant first-order logic something similar should be true. However, they only managed to show that successor-invariant first-order logic is tractable on the class of planar graphs which is very far from the best tractability results currently known for first-order logic. In this paper we significantly improve the latter result and show that successor-invariant first-order logic is tractable on any class of graphs excluding a fixed minor. This is much closer to the best results known for FO without an ordering. The proof relies on the construction of k-walks in suitable supergraphs of the input graphs, i.e., walks which visit every vertex at least once and at most k times, for some k depending on the excluded minor H. The supergraphs may in general contain H minors, but they still exclude some possible larger minor H', so by results of Flum and Grohe [20] model checking on these graphs is still fixed-parameter tractable.

For any fixed surface σ of genus g, we give an algorithm to decide whether a graph G of girth at least five embedded in σ is colorable from an assignment of lists of size three in time O(|V(G)|). Furthermore, we can allow a subgraph (of any size) with at most s components to be precolored, at the expense of increasing the time complexity of the algorithm to O(|V(G)|K(g+s)+1) for some absolute constant K; in both cases, the multiplicative constant hidden in the O-notation depends on g and s. This also enables us to find such a coloring when it exists. The idea of the algorithm can be applied to other similar problems, e.g., 5-list-coloring of graphs on surfaces.

A key result of Robertson and Seymour's graph minor theory is a structure theorem stating that all graphs excluding some fixed graph as a minor have a tree decomposition into pieces that are almost embeddable in a fixed surface. Most algorithmic applications of graph minor theory rely on an algorithmic version of this result. However, the known algorithms for computing such graph minor decompositions heavily rely on the very long and complicated proofs of the existence of such decompositions, essentially they retrace these proofs and show that all steps are algorithmic. In this paper, we give a simple quadratic time algorithm for computing graph minor decompositions. The best previously known algorithm due to Kawarabayashi and Wollan runs in cubic time and is far more complicated. Our algorithm combines techniques from logic and structural graph theory, or more precisely, a variant of Courcelle's Theorem stating that monadic second-order logic formulas can be evaluated in linear time on graphs of bounded tree width and Robertson and Seymour's so called Weak Structure Theorem.

A seminal result of Thomassen [40] says that there are only finitely many 6-color-critical graphs for the bounded genus graphs. This result is no longer true if we consider K3,k-minor-free graphs. K3,k-minor-free graphs are a significant generalization of bounded-genus graphs. They also contain infinitely many t-color-critical graphs for all t with k + 2 ≥ t ≥ 4.

A totally odd H-subdivision means a subdivision of a graph H in which each edge of H corresponds to a path of odd length. Thus this concept is a generalization of a subdivision of H. In this paper, we give a structure theorem for graphs without a fixed graph H as a totally odd subdivision. Namely, every graph with no totally odd H-subdivision has a tree-decomposition such that each piece is either 1. after deleting bounded number of vertices, an “almost” embedded graph into a bounded-genus surface, or 2. after deleting bounded number of vertices, a bipartite graph, or 3. after deleting bounded number of vertices, a graph with maximum degree at most f(|H|) for some function f of |H| (or a 6|H|-degenerate graph). Moreover, we can obtain either a totally odd Kk-subdivision or such a tree-decomposition in polynomial time. We note that for minor-free graphs, we just need the first structure [37], while for odd-minor-free graphs, we need the first two structures [10]. For subdivision-free graphs, we need the first and the third structures [17, 29]. So our result can be viewed as a combination of odd-minor-free graphs and subdivision-free graphs. The same conclusion of the structure theorem is true if we replace “totally odd” by “parity”. Hence this generalizes the structure theorem for subdivision-free graphs [17, 29]. We also consider coloring of graphs with no totally odd Kk-subdivision. We prove that any graph with no totally odd Kk-subdivision is 79k2/4-colorable. The bound on the chromatic number is essentially best possible since the correct order of the magnitude of the chromatic number even for graphs with no Kk-subdivision is Θ(k2). Our result improves the bound given by Thomassen [44]. Furthermore, it also generalizes the result by Bollobás and Thomason, and Komlós and Szemerédi, [6, 30] for graphs without Kk-subdivisions. Finally we consider of coloring graphs with no totally odd Kk-subdivision in terms of an algorithmic view. Using our structure theorem, we give an approximation algorithm for coloring of a graph G without a fixed graph H as a totally odd subdivision, using 2χ(G) + 6(|H| − 1) colors, where χ(G) is chromatic number of G. The same conclusion is true if we replace “totally odd” by “parity”. We point out that it is Unique-Game hard to obtain an O(k/ log2 k)-approximation algorithm for graph-coloring of graphs with maximum degree at most k − 2 [2], and hence it is also Unique-Game hard to obtain an O(k/ log2 k)-approximation algorithm for graph-coloring of graphs even without a Kk-subdivision (i.e, without the parity constraint). Thus our additive error Θ(k) is most likely best possible up to constant.

A seminal result of Reed et al. [15] in 1996 states that the Erdős-Pósa property holds for directed cycles, i.e. for every integer n there is an integer t such that every directed graph G has n pairwise vertex disjoint directed cycles or contains a set T ⊆ V (G) of at most t vertices such that G -T contains no directed cycle.In this paper, we consider the Erdős-Pósa property for directed cycles through a vertex in a given vertex set S, i.e. the question if for every integer n there is an integer t such that if G is a directed graph G and S is a set of vertices then G has n pairwise vertex disjoint directed cycles each containing a vertex of S or contains a set T of at most t vertices such that G-T contains no such directed cycle.For undirected graphs, this property holds for cycles through a vertex in a vertex set S (see Kakimura, Kawarabayashi and Marx [9], and Pontecorvi and Wollan [12]).In this paper, we show the following: The Erdős-Pósa does hold for half-integral packings of directed cycles each containing a vertex from S, i.e.where every vertex of the graph is contained in at most 2 cycles.On the other hand, an example shows that the Erdős-Pósa property does not hold without this relaxation.

We generalize the following two seminal results. 1. Thomassen's result [19] in 1983, which says that every 4-connected planar graph is hamiltonian-connected (which generalizes the old result of Tutte [20] in 1956, which says that every 4-connected planar graph is hamiltonian). 2. Thomas and Yu's result [16] in 1994, which says that every 4-connected projective planar graph is hamiltonian. Here, hamiltonian-connected means that for any two vertices u, v, there is a hamiltonian path between u and v (and hence this generalizes the existence of hamiltonian cycles). Specifically, we prove the following; Every 4-connected projective planar graph is hamiltonian-connected. This proves a conjecture of Dean [3] in 1990. Our result is best possible in many senses. First, we cannot lower the connectivity 4. Secondly, we cannot generalize our result to a surface with higher genus (i.e, there is a 4-connected graph on the torus which is not hamiltonian-connected). Our proof is constructive in the sense that there is a polynomial time (in fact, O(n2) time) algorithm to find, given two vertices in a 4-connected projective planar graph, a hamiltonian path between these two vertices.

Distance oracles are data structures that provide fast (possibly approximate) answers to shortest-path and distance queries in graphs. The tradeoff between the space requirements and the query time of distance oracles is of particular interest and the main focus of this paper. Unless stated otherwise, we assume all graphs to be planar and undirected. In FOCS 2001 (J. ACM 2004), Thorup introduced approximate distance oracles for planar graphs (concurrent with Klein, SODA 2002). Thorup proved that, for any ε > 0 and for any undirected planar graph G = (V, E) on n = |V| nodes, there exists a (1 + ε)-approximate distance oracle using space O(nε−1 log n) such that approximate distance queries can be answered in time O(ε−1). In this paper, we aim at reducing the polynomial dependency on ε−1 and log n, getting the first improvement in the query time-space tradeoff. To simplify the statement of our bounds, we define Ō(·) to hide log log n and log(1/ε) factors. We provide the first oracle with a time-space product that is subquadratic in ε−1. We obtain an oracle with space Ō(n log n) and query time Ō(ε−1). For unweighted graphs we show how the logarithmic dependency on n can be removed. We obtain an oracle with space Ō(n) and query time Ō(ε−1). This bound also holds for graphs with polylogarithmic average edge length, which may be a quite reasonable assumption, e.g., for road networks.

Testing a property P of graphs in the bounded-degree model deals with the following problem: given a graph G of bounded degree d, we should distinguish (with probability 2/3, say) between the case that G satisfies P and the case that one should add/remove at least ε dn edges of $G$ to make it satisfy P. In sharp contrast to property testing of dense graphs, which is relatively well understood, only few properties are known to be testable with a constant number of queries in the bounded-degree model. In particular, no global monotone (i.e,~closed under edge deletions) property that expander graphs can satisfy has been shown to be testable in constant time so far.

In this article, we study an approximation algorithm for the maximum edge-disjoint paths problem. In this problem, we are given a graph and a collection of pairs of vertices, and the objective is to find the maximum number of pairs that can be connected by edge-disjoint paths. We give an O (log n )-approximation algorithm for the maximum edge-disjoint paths problem when an input graph is either 4-edge-connected planar or Eulerian planar. This improves an O (log 2 n )-approximation algorithm given by Kleinberg [2005] for Eulerian planar graphs. Our result also generalizes the result by Chekuri et al. [2004, 2005] who gave an O (log n )-approximation algorithm for the maximum edge-disjoint paths problem with congestion two when an input graph is planar.

We introduce a linear distance relaxation of the n-team Traveling Tournament Problem (TTP), a simple yet powerful heuristic that temporarily "assumes"' the n teams are located on a straight line, thereby reducing the n(n–1)/2 pairwise distance parameters to just n–1 variables. The modified problem then becomes easier to analyze, from which we determine an approximate solution for the actual instance on n teams. We present combinatorial techniques to solve the Linear Distance TTP (LD-TTP) for n = 4 and n = 6, without any use of computing, generating the complete set of optimal distances regardless of where the n teams are located. We show that there are only 295 non-isomorphic schedules that can be a solution to the 6-team LD-TTP, and demonstrate that in all previously-solved benchmark TTP instances on 6 teams, the distance-optimal schedule appears in this list of 295, even when the six teams are arranged in a circle or located in three-dimensional space. We then extend the LD-TTP to multiple rounds, and apply our theory to produce a nearly-optimal regular-season schedule for the Nippon Pro Baseball league in Japan. We conclude the paper by generalizing our theory to the n-team LD-TTP, producing a feasible schedule whose total distance is guaranteed to be no worse than 4/3 times the optimal solution.

We present new and improved methods for efficient shortest-path query processing. Our methods are tailored to work for two specific classes of graphs: graphs with small tree-width and complex networks. Seemingly unrelated at first glance, these two classes of graphs have some commonalities: complex networks are known to have a core--fringe structure with a dense core and a tree-like fringe.

We consider the problem of coloring a 3-colorable graph in polynomial time using as few colors as possible. We present a combinatorial algorithm getting down to Õ(n4/11) colors. This is the first combinatorial improvement of Blum's Õ(n3/8) bound from FOCS'90. Like Blum's algorithm, our new algorithm composes nicely with recent semi-definite programming approaches. The current best bound is Õ(n0.2072) colors by Chlamtac from FOCS'07. We now bring it down to Õ(n0. 2049) colors.

The well-known Erdős-Pósa theorem says that for any integer k and any graph G, either G contains k vertex-disjoint cycles or a vertex set X of order at most c · k log k (for some constant c) such that G – X is a forest. Thomassen [39] extended this result to the even cycles, but on the other hand, it is well-known that this theorem is no longer true for the odd cycles. However, Reed [31] proved that this theorem still holds if we relax k vertex-disjoint odd cycles to k odd cycles with each vertex in at most two of them. These theorems initiate many researches in both graph theory and theoretical computer science. In the graph theory side, our problem setting is that we are given a graph and a vertex set S, and we want to extend all the above results to cycles that are required to go through a subset of S, i.e., each cycle contains at least one vertex in S (such a cycle is called an S-cycle). It was shown in [20] that the above Erdős-Pósa theorem still holds for this subset version. In this paper, we extend both Thomassen's result and Reed's result in this way. In the theoretical computer science side, we investigate generalizations of the following well-known problems in the framework of parameterized complexity: the feedback set problem and the cycle packing problem. Our purpose here is to consider the following problems: the feedback set problem with respect to the S-cycles, and the S-cycle packing problem. We give the first fixed parameter algorithms for the two problems. Namely; 1. For fixed k, we can either find a vertex set X of size k such that G − X has no S-cycle, or conclude that such a vertex set does not exist in O(n2m) time (independently obtained in [7]). 2. For fixed k, we can either find k vertex-disjoint S-cycles, or conclude that such k disjoint cycles do not exist in O(n2m) time. We also extend the above results to those with the parity constraints as follows; 1. For a parameter k, there exists a fixed parameter algorithm that either finds a vertex set X of size k such that G − X has no even S-cycle, or concludes that such a vertex set does not exist. 2. For a parameter k, there exists a fixed parameter algorithm that either finds a vertex set X of size k such that G − X has no odd S-cycle, or concludes that such a vertex set does not exist. 3. For a parameter k, there exists a fixed parameter algorithm that either finds k vertex-disjoint even S-cycles, or concludes that such k disjoint cycles do not exist. 4. For a parameter k, there exists a fixed parameter algorithm that either finds k odd S-cycles with each vertex in at most two of them, or concludes that such k cycles do not exist.

A graph G contains a subdivision of H if G contains a subgraph which is isomorphic to a graph that can be obtained from H by subdividing some edges. A graph H is immersed in a graph G if the vertices of H are mapped to (distinct) vertices of G, and the edges of H are mapped to paths joining the corresponding pairs of vertices of G, in such a way that the paths are pairwise edge-disjoint. Although the well-known Kuratowski's theorem can be stated in terms of both a subdivision and a minor, we know that the notions of a subdivision and a minor do not seem to be similar. The notions of an immersion and a minor seem to be quite similar, and structural approach concerning graph minors has been extremely successful. In fact, Robertson and Seymour extended their proof of the famous Wanger's conjecture to prove that graphs are well-quasi-ordered by the immersion relation. We give additive approximation algorithms for list-coloring within 3.5(k + 1) of the list-chromatic number for graphs without Kk as a subdivision, and within 1.5(k − 1) of the list-chromatic number for graphs without Kk as an immersion. Clearly our results give rise to additive approximation algorithms for graph-coloring of graphs without Kk as a subdivision (in fact, we shall give an additive approximation algorithm within 2.5(k + 1) of the chromatic number) and Kk as an immersion, too. These are the first results in this direction (in fact, these are the first results concerning list-coloring graphs without fixed graph as a subdivision or as an immersion, except for the known upper bound results) and extend the result by Kawarabayashi, Demaine and Hajiaghayi (SODA'09) concerning the additive approximation algorithm for list-coloring graphs without Kk as a minor. We also discuss how our results are related to the famous Hájos’ conjecture and Hadwiger's conjecture. We point out that it is Unique-Game hard to obtain an O(k/ log2 k)-approximation algorithm for graph-coloring of graphs with maximum degree at most k − 2 [6], and hence it is also Unique-Game hard to obtain an O(k/ log2 k)-approximation algorithm for graph-coloring of graphs without a Kk-subdivision or without a Kk-immersion. Therefore it really makes sense to consider an additive approximation algorithm for graph coloring of these family of graphs (which is in contrast to a 2-approximation algorithm for graph-coloring of H-minor-free graphs [13]).

We consider the following problem which is motivated by two different contexts independently, namely graph theory and combinatorial optimization. Given a 3-connected planar graph G with n vertices, is there a spanning closed walk W with at most 4n/3 edges? In graph theory, the above question is motivated by the famous hamiltonian result by Tutte in 1956 which says that every 4-connected planar graph is hamiltonian (a simpler proof is given by Thomassen in 1983). What happens if we relax the 4-connectivity? There is a 3-connected planar graph that is not hamiltonian, but how about a spanning close walk (which is exactly a traveling salesman tour. Sometimes such a walk is called hamiltonian walk)? How many edges are necessary to cover all the vertices of a 3-connected planar graph by a closed walk? This is exactly the above question. In combinatorial optimization, the famous traveling salesman problem in metric graphs is one of most fundamental NP-hard optimization problems. In spite of a vast amount of research several important questions remain open. In particular, the best known upper bound is not believed to be best possible. A promising direction to improve this approximation guarantee, has long been to understand the power of a linear program known as the Held-Karp relaxation [11]. On the one hand, the best lower bound on its integrality gap (for the symmetric case) is 4/3 and indeed the famous (so called 4/3-)conjecture said that this lower bound would be tight [10]. Goemans pointed out that there is a planar graph that achieves this bound. So he brought attention to the above question, i.e, the famous 4/3-conjecture is always true for 3-connected planar graphs. We prove the above problem in the following strong form; Given a circuit graph (which is obtained from a 3-connected planar graph by deleting one vertex) with n vertices, there is a spanning closed walk with at most 4(n − 1)/3 edges such that each edge is used at most twice. Moreover, our proof is constructive (and purely combinatorial) in a sense that there is an O(n2) algorithm to construct, given a 3-connected planar graph, such a walk. We shall construct an example that shows that the bound 4(n − 1)/3 is essentially tight. We also point out that 2-connected planar graphs may not have such a walk, as K2,n − 2 shows.

Finding edge-disjoint odd cycles is one of the most important problems in graph theory, graph algorithm and combinatorial optimization. In fact, it is closely related to the well-known max-cut problem. One of the difficulties of this problem is that the Erdös-Pósa property does not hold for odd cycles in general. Motivated by this fact, we prove that for any positive integer k, there exists an integer f(k) satisfying the following: For any 4-edge-connected graph G=(V,E), either G has edge-disjoint k odd cycles or there exists an edge set F subseteq E with |F| <= f(k) such that G-F is bipartite. We note that the 4-edge-connectivity is best possible in this statement. Similar approach can be applied to an algorithmic question. Suppose that the input graph G is a 4-edge-connected graph with n vertices. We show that, for any epsilon > 0, if k = O ((log log log n)^{1/2-epsilon}), then the edge-disjoint k odd cycle packing in G can be solved in polynomial time of n.

A key theorem in algorithmic graph-minor theory is a min-max relation between the treewidth of a graph and its largest grid minor. This min-max relation is a keystone of the Graph Minor Theory of Robertson and Seymour, which ultimately proves Wagner's Conjecture about the structure of minor-closed graph properties. In 2008, Demaine and Hajiaghayi proved a remarkable linear min-max relation for graphs excluding any fixed minor H: every H-minor-free graph of treewidth at least c_H r has an r times r-grid minor for some constant c_H. However, as they pointed out, there is still a major problem left in this theorem. The problem is that their proof heavily depends on Graph Minor Theory, most of which lacks explicit bounds and is believed to have very large bounds. Hence c_H is not explicitly given in the paper and therefore this result is usually not strong enough to derive efficient algorithms. Motivated by this problem, we give another (relatively short and simple) proof of this result without using big machinery of Graph Minor Theory. Hence we can give an explicit bound for c_H (an exponential function of a polynomial of |H|). Furthermore, our result gives a constant w=2^O(r^2 log r) such that every graph of treewidth at least w has an r times r-grid minor, which improves the previously known best bound 2^Theta(r^5)$ given by Robertson, Seymour, and Thomas in 1994.

In some domestic professional sports leagues, the home stadiums are located in cities connected by a common train line running in one direction. For these instances, we can incorporate this geographical information to determine optimal or nearly-optimal solutions to the n-team Traveling Tournament Problem (TTP), an NP-hard sports scheduling problem whose solution is a double round-robin tournament schedule that minimizes the sum total of distances traveled by all n teams. We introduce the Linear Distance Traveling Tournament Problem (LD-TTP), and solve it for n=4 and n=6, generating the complete set of possible solutions through elementary combinatorial techniques. For larger n, we propose a novel "expander construction" that generates an approximate solution to the LD-TTP. For n congruent to 4 modulo 6, we show that our expander construction produces a feasible double round-robin tournament schedule whose total distance is guaranteed to be no worse than 4/3 times the optimal solution, regardless of where the n teams are located. This 4/3-approximation for the LD-TTP is stronger than the currently best-known ratio of 5/3 + epsilon for the general TTP. We conclude the paper by applying this linear distance relaxation to general (non-linear) n-team TTP instances, where we develop fast approximate solutions by simply "assuming" the n teams lie on a straight line and solving the modified problem. We show that this technique surprisingly generates the distance-optimal tournament on all benchmark sets on 6 teams, as well as close-to-optimal schedules for larger n, even when the teams are located around a circle or positioned in three-dimensional space.

A seminal result of Reed et al. [Combinatorica, 16 (1996), pp. 535--554] says that a directed graph has either $k$ vertex-disjoint directed circuits or a set of at most $f(k)$ vertices meeting all directed circuits. This paper aims at generalizing their result to packing directed circuits through a prescribed set $S$ of vertices. Such a circuit is called an $S$-circuit. Even et al. [Algorithmica, 20 (1998), pp. 151--174] showed a fractional version of packing $S$-circuits. In this paper, we show that the fractionality can be bounded by at most one-fifth: Given an integer $k$ and a vertex subset $S$, whose size may not depend on $k$, we prove that either $G$ has a $1/5$-integral packing of $k$ disjoint $S$-circuits, i.e., each vertex appears in at most five of these $S$-circuits, or $G$ has a vertex set $X$ of order at most $f(k)$ (for some function $f$ of $k$) such that $G-X$ has no such circuit. We also give a fixed-parameter tractable approximation algorithm for finding a $1/5$-integral packing of $S$-circuits. This algorithm finds a $1/5$-integral packing of size approximately $k$ in polynomial time if it has a $1/5$-integral packing of size $k$ for a given directed graph and an integer $k$.

With the recent inclusion of inter-league games to professional sports leagues, a natural question is to determine the "best possible" inter-league schedule that retains all of the league's scheduling constraints to ensure competitive balance and fairness, while minimizing the total travel distance for both economic and environmental efficiency. To answer that question, this paper introduces the Bipartite Traveling Tournament Problem (BTTP), the inter-league extension of the well-studied Traveling Tournament Problem. We prove that the 2n-team BTTP is NP-complete, but for small values of n, a distance-optimal inter-league schedule can be generated from an algorithm based on minimum-weight 4-cycle-covers. We apply our algorithm to the 12-team Nippon Professional Baseball (NPB) league in Japan, creating an inter-league tournament that reduces total team travel by 16% compared to the actual schedule played by these teams during the 2010 NPB season. We also analyze the problem of inter-league scheduling for the 30-team National Basketball Association (NBA), and develop a tournament schedule whose total inter-league travel distance is just 3.8% higher than the trivial theoretical lower bound.

We generalize the seminal Graph Minor algorithm of Robertson and Seymour to the parity version. We give polynomial time algorithms for the following problems: 1) the parity H-minor (Odd Kk-minor) containment problem, and 2) the disjoint paths problem with k terminals and the parity condition for each path, as well as several other related problems. We present an O(ma(m, n)n) time algorithm for these problems for any fixed k, where n, m are the number of vertices and the number of edges, respectively, and the function a(m,n) is the inverse of the Ackermann function (see Tarjan [69]). Note that the first problem includes the problem of testing whether or not a given graph contains k disjoint odd cycles (which was recently solved in [24], [34]), if we fix H to be equal to the graph of k disjoint triangles. The algorithm for the second problem generalizes the Robertson Seymour algorithm for the k-disjoint paths problem. As with the Robertson-Seymour algorithm for the k-disjoint paths problem for any fixed k, in each iteration, we would like to either use the presence of a huge clique minor, or alternatively exploit the structure of graphs in which we cannot find such a minor. Here, however, we must maintain the parity of the paths and can only use an "odd clique minor". This requires new techniques to describe the structure of the graph when we cannot find such a minor. We emphasize that our proof for the correctness of the above algorithms does not depend on the full power of the Graph Minor structure theorem [56]. Although the original Graph Minor algorithm of Robertson and Seymour does depend on it and our proof does have similarities to their arguments, we can avoid the structure theorem by building on the shorter proof for the correctness of the graph minor algorithm in [35]. This work was done as a part of an INRIA-NII collaboration under MOU grant, and partially supported by MEXT Grant-in-Aid for Scientific Research on Priority Areas "New Horizons in Computing" Research partly supported by Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research, by C & C Foundation, by Kayamori Foundation and by Inoue Research Award for Young Scientists. Consequently, we are able to avoid the much of the heavy machinery of the Graph Minor structure theory. Utilizing some results of [35] and [62], [63], our proof is less than 50 pages.

We consider the minimum k-way cut problem for unweighted undirected graphs with a size bound s on the number of cut edges allowed. Thus we seek to remove as few edges as possible so as to split a graph into k components, or report that this requires cutting more than s edges. We show that this problem is fixed-parameter tractable (FPT) with the standard parameterization in terms of the solution size s. More precisely, for s=O(1), we present a quadratic time algorithm. Moreover, we present a much easier linear time algorithm for planar graphs and bounded genus graphs. Our tractability result stands in contrast to known W[1] hardness of related problems. Without the size bound, Downey et al. [2003] proved that the minimum k-way cut problem is W[1] hard with parameter k, and this is even for simple unweighted graphs. Downey et al. asked about the status for planar graphs. We get linear time with fixed parameter k for simple planar graphs since the minimum k-way cut of a planar graph is of size at most 6k. More generally, we get FPT with parameter k for any graph class with bounded average degree. A simple reduction shows that vertex cuts are at least as hard as edge cuts, so the minimum k-way vertex cut is also W[1] hard with parameter k. Marx [2004] proved that finding a minimum k-way vertex cut of size s is also W[1] hard with parameter s. Marx asked about the FPT status with edge cuts, which we prove tractable here. We are not aware of any other cut problem where the vertex version is W[1] hard but the edge version is FPT, e.g., Marx [2004] proved that the k-terminal cut problem is FPT parameterized by the cut size, both for edge and vertex cuts.

We prove that any graph excluding a fixed minor can have its edges partitioned into a desired number k of color classes such that contracting the edges in any one color class results in a graph of treewidth linear in k. This result is a natural finale to research in contraction decomposition, generalizing previous such decompositions for planar and bounded-genus graphs, and solving the main open problem in this area (posed at SODA 2007). Our decomposition can be computed in polynomial time, resulting in a general framework for approximation algorithms, particularly PTASs (with k ∼ 1/ε), and fixed-parameter algorithms, for problems closed under contractions in graphs excluding a fixed minor. For example, our approximation framework gives the first PTAS for TSP in weighted H-minor-free graphs, solving a decade-old open problem of Grohe; and gives another fixed-parameter algorithm for k-cut in H-minor-free graphs, which was an open problem of Downey et al. even for planar graphs.

We prove that for every fixed undirected graph H, there is an O(|V(G)|3) time algorithm that, given a graph G, tests if G contains H as a topological subgraph (that is, a subdivision of H is subgraph of G). This shows that topological subgraph testing is fixed-parameter tractable, resolving a longstanding open question of Downey and Fellows from 1992. As a corollary, for every H we obtain an O(|V(G)|3) time algorithm that tests if there is an immersion of H into a given graph G. This answers another open question raised by Downey and Fellows in 1992.

In the maximum edge-disjoint paths problem, we are given a graph and a collection of pairs of vertices, and the objective is to find the maximum number of pairs that can be routed by edge-disjoint paths. An r-approximation algorithm for this problem is a polynomial time algorithm that finds at least OPT / r edge-disjoint paths, where OPT is the maximum possible. Currently, an O(n1/2)-approximation algorithm is best known for this problem even if a congestion of two is allowed, i.e., each edge is allowed to be used in at most two of the paths.

At the core of the Robertson-Seymour theory of graph minors lies a powerful decomposition theorem which captures, for any fixed graph H, the common structural features of all the graphs which do not contain H as a minor. Robertson and Seymour used this result to prove Wagner's Conjecture that finite graphs are well-quasi-ordered under the graph minor relation, as well as give a polynomial time algorithm for the disjoint paths problem when the number of the terminals is fixed. The theorem has since found numerous applications, both in graph theory and theoretical computer science. The original proof runs more than 400 pages and the techniques used are highly non-trivial.

In this paper, we consider the half-integral disjoint paths packing. For a graph [Formula: see text] and [Formula: see text] pairs of vertices [Formula: see text] in [Formula: see text], the objective is to find paths [Formula: see text] in [Formula: see text] such that [Formula: see text] joins [Formula: see text] and [Formula: see text] for [Formula: see text], and in addition, each vertex is on at most two of these paths. We give a polynomial-time algorithm to decide the feasibility of this problem with [Formula: see text]. This improves a result by Kleinberg [Proceedings of the 30th ACM Symposium on Theory of Computing, 1998, pp 530–539] who proved the same conclusion when [Formula: see text]. Our algorithm still works for several problems related to the bounded unsplittable flow. These results can all carry over to problems involving edge capacities. Our main technical contribution is to give a “crossbar” of a polynomial size of the tree width of the graph.

Grötzsch's theorem states that every triangle-free planar graph is 3-colorable, and several relatively simple proofs of this fact were provided by Thomassen and other authors. It is easy to convert these proofs into quadratic-time algorithms to find a 3-coloring, but it is not clear how to find such a coloring in linear time (Kowalik used a nontrivial data structure to construct anO(nlogn) algorithm). We design a linear-time algorithm to find a 3-coloring of a given triangle-free planar graph. The algorithm avoids using any complex data structures, which makes it easy to implement. As a by-product, we give a yet simpler proof of Grötzsch's theorem.

We consider piecewise linear embeddings of graphs in 3-space ℜ3. Such an embbeding is linkless if every pair of disjoint cycles forms a trivial link (in the sense of knot theory). Robertson, Seymour and Thomas [47] showed that a graph has a linkless embedding in ℜ3 if, and only if, it does not contain as a minor any of seven graphs in Petersen's family (graphs obtained from K6 by a series of YΔ and ΔY operations). They also showed that a graph is linklessly embeddable in ℜ3 if, and only if, it admits a flat embedding into ℜ3, i.e. an embedding such that for every cycle C of G there exists a closed 2-disk D ⊆ ℜ3 with D ∩ G = ∂D = C. Clearly, every flat embeddings is linkless, but the converse is not true. We first consider the following algorithmic problem associated with embeddings in ℜ3:

It is shown that for each t, there is a separator of size O(t√n) in any n-vertex graph G with no Kt-minor. This settles a conjecture of Alon, Seymour and Thomas (J. Amer. Math. Soc, 1990 and STOC'90), and generalizes a result of Djidjev (1981), and Gilbert, Hutchinson and Tarjan (J. Algorithm, 1984), independently, who proved that every graph with n vertices and genus g has a separator of order O(√gn), because Kthas genus Ω(t2). The bound O(t√n) is best possible because every 3-regular expander graph with n vertices is a graph with no Kt-minor for t = cn1/2, and with no separator of size dn for appropriately chosen positive constants c, d. In addition, we give an O(n2) time algorithm to obtain such a separator, and then give a sketch how to obtain such a separator in O(n1+ε) time for any ε > 0. Finally, we discuss several algorithm aspects of our separator theorem, including a possibility to obtain a separator of order g(t)√n, for some function g of t, in an n-vertex graph G with no Kt-minor in O(n) time.

In this paper we study the problem of message duplication in dissemination of dynamic content such as news or traffic information over a Dense Mobile Social Network (MSN). In MSNs mobile devices disseminate content only to the nodes whose subscribed interest match it. MSNs are used to improve the coverage and increase capacity as we assume that people in an intermittently connected MSNs are socially-related and tend to co-locate quite regularly. MSNs are similar to Disruption Tolerant Networks (DTNs) expect that in MSNs the assumption is that individuals follow predictable working day movement model and the users exchange profile and disseminate content only to the users in their social network. The analysis of three independent experiments conducted, shows that the current message forwarding protocols for dense MSNs can experience up-to 94% of duplicate messages in the worst-case because the messages are replicated to be routed over multiple delivery paths in-order to optimize the probability of successful message delivery. Although these approaches do (statistically) guarantee delivery probability but impose overheads on bandwidth, energy and memory. Therefore, in this paper we propose a message duplication reduction algorithm by exploiting the mobility predictability property of the users in MSNs. We model our problem as an on-line graph and solve the problem of message duplication by an algorithm on the well-known spanning tree problem. Furthermore, we divide our problem into three optimization problems and priorities them as minimize message delivery time, minimize message duplication and minimize message storage space. The study presented in this paper achieve message duplication reduction of 71.8% in the best-case (i.e. domination set of most influential users and many to many data delivery) and 14.8% in the worst case (i.e. selecting random users and one to one data delivery) while guaranteeing a given delay or delivery probability and lowering system wide traffic flooding.

We prove two structural decomposition theorems about graphs excluding a fixed odd minor H, and show how these theorems can be used to obtain approximation algorithms for several algorithmic problems in such graphs. Our decomposition results provide new structural insights into odd-H-minor-free graphs, on the one hand generalizing the central structural result from Graph Minor Theory, and on the other hand providing an algorithmic decomposition into two bounded-treewidth graphs, generalizing a similar result for minors. As one example of how these structural results conquer difficult problems, we obtain a polynomial-time 2-approximation for vertex coloring in odd-H-minor-free graphs, improving on the previous O(|V(H)|)-approximation for such graphs and generalizing the previous 2-approximation for H-minor-free graphs. The class of odd-H-minor-free graphs is a vast generalization of the well-studied H-minor-free graph families and includes, for example, all bipartite graphs plus a bounded number of apices. Odd-H-minor-free graphs are particularly interesting from a structural graph theory perspective because they break away from the sparsity of H-minor-free graphs, permitting a quadratic number of edges.

We consider the following well-known problem, which is called the edge-disjoint paths problem. Input: A graph G with n vertices and m edges, k pairs of vertices (s1, t1), (s2, t2), …, (sk, tk) in G. Output: Edge-disjoint paths P1, P2, …, Pk in G such that Pi joins si and ti for i = 1, 2, …, k. Robertson and Seymour's graph minor project gives rise to an O(m3) algorithm for this problem for any fixed k, but their proof of the correctness needs the whole Graph Minor project, spanning 23 papers and at least 500 pages proof. We give a faster algorithm and a simpler proof of the correctness for the edge-disjoint paths problem for any fixed k. Our results can be summarized as follows: 1. If an input graph G is either 4-edge-connected or Eulerian, then our algorithm only needs to look for the following three simple reductions: (i) Excluding vertices of high degree. (ii) Excluding ≤ 3-edge-cuts. (iii) Excluding large clique minors. 2. When an input graph G is either 4-edge-connected or Eulerian, the number of terminals k is allowed to be non-trivially superconstant number, up to k = O((log log log n)½–ε) for any ε > 0. Thus our hidden constant in this case is dramatically smaller than Robertson-Seymour's. In addition, if an input graph G is either 4-edge-connected planar or Eulerian planar, k is allowed to be O((log n)½–ε) for any ε > 0. The same thing holds for bounded genus graphs. Moreover, if an input graph is either 4-edge-connected H-minor-free or Eulerian H-minor-free for fixed graph H, k is allowed to be O((log log n)½–ε) for any ε > 0. 3. We also give our own algorithm for the edge-disjoint paths problem in general graphs. We basically follow Robertson-Seymour's algorithm, but we cut half of the proof of the correctness for their algorithm. In addition, the time complexity of our algorithm is O(n2), which is faster than Robertson and Seymour's.

A totally odd K4-subdivision is a subdivision of K4 where each subdivided edge has odd length. The recognition of a totally odd K4-subdivision plays an important role in both graph theory and combinatorial optimization. Sewell and Trotter [53], Zang [63] and Thomassen [60] independently conjectured the existence of a polynomial time recognition algorithm. In this paper, we give the first polynomial time algorithm for solving this problem. We also study the the parity two disjoint rooted paths problem where we determine if there exists two vertex disjoint paths of a specified parity between two pairs of terminals. Using a similar technique, we give an O(|E(G)||V(G)|α(|E(G)|,|V(G)|)) algorithm for the parity two disjoint rooted paths problem on an input graph G, where α(|E(G)|,|V(G)|) is the inverse of the Ackermann function. We note that this clearly gives an algorithm for the well-known non-parity version of the two disjoint rooted paths problem [19, 50, 52, 55, 58]. We then extend our approach to give a polynomial time algorithm which determines, for any fixed k, whether there exists a cycle of a given parity through k independent input edges. This generalizes the non-parity version of the algorithm in [22]. Thomassen [61] gave a polynomial algorithm for the case k = 2 and hoped to use this algorithm to recognize a totally odd K4-subdivision. Our algorithm runs in O(|E(G)||V(G)|α(|E(G)|, |V(G)|)) for any fixed k. Finally, we give an O(|V(G)|2 + |E(G)|α(|E(G)|,|V(G)|log|V(G)|)) algorithm to decide whether a graph contains k disjoint paths from A to B (with |A| = |B| = k) that are not all of the same parity. This answers a conjecture of Thomassen [60]. This problem arises from the study of totally odd-K4-subdivisions in 3-connected graphs [60].

We consider the following problem, which is called the odd cycles transversal problem. Input: A graph G and an integer k. Output: A vertex set X ∊ V(G) with |X| ≤ k such that G – X is bipartite. We present an O(mα(m, n)) time algorithm for this problem for any fixed k, where n, m are the number of vertices and the number of edges, respectively, and the function α(m, n) is the inverse of the Ackermann function (see by Tarjan [38]). This improves the time complexity of the algorithm by Reed, Smith and Vetta [29] who gave an O(nm) time algorithm for this problem. Our algorithm also implies the edge version of the problem, i.e, there is an edge set X′ ∊ E(G) such that G – X′ is bipartite. Using this algorithm and the recent result in [16], we give an O(mα(m, n) + n log n) algorithm for the following problem for any fixed k: Input: A graph G and an integer k. Output: Determine whether or not there is a half-integral k disjoint odd cycles packing, i.e, k odd cycles C1, …, Ck in G such that each vertex is on at most two of these odd cycles. This improves the time complexity of the algorithm by Reed, Smith and Vetta [29] who gave an O(n3) time algorithm for this problem. We also give a much simpler and much shorter proof for the following result by Reed [28]. The Erdős-Pósa property holds for the half-integral disjoint odd cycles packing problem. I.e. either G has a half-integral k disjoint odd cycles packing or G has a vertex set X of order at most f(k) such that G – X is bipartite for some function f of k. Note that the Erdős-Pósa property does not hold for odd cycles in general.

We consider the following problem, which is called the odd cycle packing problem. Input: A graph $G$ with n vertices and m edges, and an integer k. Output: k vertex disjoint odd cycles. We also consider the edge disjoint case, and the node- and arc-disjoint directed case. This problem is known to be NP-hard, even for planar graphs, if k is part of input. In this paper, we first present the integrality gap and hardness results for these problems. We prove that the integrality gap of the standard LP-relaxation of the odd cycle packing problem is Θ (√n). This result is obtained by giving an algorithm to compute an odd cycle packing, which gives rise to an O(√n) approximating algorithm for the fractional odd cycle packing problem (this gives rise to an upper bound), and by showing that there is a graph G such that there is an O(√n) half-integral odd cycle packing in G, but there are no two disjoint odd cycle in G (this gives rise to a lower bound). For the hardness result, we prove that for any ε, the node-disjoint directed odd cycle packing problem is NP-hard to approximate within m1/2-ε, where m is the number of arcs of a given digraph G. This is true not only for the node-disjoint directed odd cycle packing problem but also for the arc-disjoint directed odd cycle packing problem. In addition, we prove that there is an O(m1/2)-approximation algorithm for the node- and arc- directed odd cycle packing problems. Thus this approximation algorithm almost matches the hardness result. For the positive side, we consider the case when the number of odd cycles, k, is fixed. This is a natural direction, for example, the seminal result of Robertson and Seymour for the disjoint paths problem in the graph minors project. We present an O(m α(m,n) n) algorithm for any fixed k, where the function α(m,n) is the inverse of the Ackermann function (see by Tarjan [72]). This is the first polynomial time algorithm for this problem (and in fact, it is the first fixed parameter tractable algorithm). This proves a conjecture by Lovasz and Schrijver in early 1980's, who gave a polynomial time algorithm for the case k=2. Our algorithm can be applied to decide whether or not G has k edge disjoint odd cycle with the same time complexity for any fixed k. We also show that our algorithm gives rise to the Graph Minor Algorithm for the k vertex-disjoint paths problem by Robertson and Seymour for any fixed k. Thus our algorithm is beyond the framework of the Graph Minor Theory. Our algorithm has several appealing features: We use the odd S-path theorem, which is a generalization of the well-known S-paths theorem by Mader. We also introduce an odd clique minor, which can be viewed as a clique minor with some parity condition. As with the Robertson-Seymour algorithm to solve the k disjoint paths problem for any fixed k, in each iteration, we would like to either use a huge clique minor as a "crossbar", or exploit the structure of graphs in which we cannot find such a minor. Here, however, we must maintain the parity of the cycles and can only use an "odd clique minor". We must also describe the structure of those graphs in which we cannot find such a minor and discuss how to exploit it. This part needs the seminal result of Robertson and Seymour for the graph minor decomposition theorem for H-minor-free graphs. We also use some deep results of Robertson and Seymour that are needed to prove the correctness of their algorithm for the disjoint paths problem.

At the core of the seminal Graph Minor Theory of Robertson and Seymour is a powerful theorem which describes the structure of graphs excluding a fixed minor. This result is used to prove Wagner's conjecture and provide a polynomial time algorithm for the disjoint paths problem when the number of the terminals is fixed (i.e, the Graph Minor Algorithm). However, both results require the full power of the Graph Minor Theory, i.e, the structure theorem.

It is proved that every graph embedded in a fixed surface with sufficiently large edge-width is acyclically 7-colorable and that its star chromatic number is at most $2s_0^*+3$, where $s_0^*\leq20$ is the maximum star chromatic number for the class of all planar graphs.

We show that for every fixed k, there is a linear time algorithm that decides whether or not a given graph has a vertex set X of order at most k such that G-X is planar (we call this class of graphs k-apex), and if this is the case, computes a drawing of the graph in the plane after deleting at most k vertices. In fact, in this case, we shall determine the minimum value l ? k such that after deleting some l vertices, the resulting graph is planar. If this is not the case, then the algorithm gives rise to a minor which is not k-apex and is minimal with this property. This answers the question posed by Cabello and Mohar in 2005, and by Kawarabayashi and Reed (STOC'07), respectively. Note that the case k = 0 is the planarity case. Thus our algorithm can be viewed as a generalization of the seminal result by Hopcroft and Tarjan (J. ACM 1974), which determines if a given graph is planar in linear time. Our algorithm can be also compared to the algorithms by Mohar (STOC'96 and Siam J. Discrete Math 2001) for testing the embeddability of an input graph in a fixed surface in linear time, by Kawarabayashi and Mohar (STOC'08) for testing polyhedral embeddability of an input graph in a fixed surface in linear time, and by Kawarabayashi and Reed (STOC'07) for testing the fixed crossing number in linear time. Note that deciding the genus of k-apex graphs is NP-complete, even for k = 1, as shown by Mohar. Thus k-apex graphs are very different from bounded genus graphs in a sense. In addition, for any fixed c, k, we apply our algorithm to obtain a linear time approximation scheme for weighted TSP, and for minimum weighted c-edge-connected submultigraph, respectively, for k-apex graphs. (In this case, an embedding of a k-apex graph is not given in the input). The first result generalizes the recent planar result by Klein (FOCS'05), while the second result generalizes Czumaj et al. (SODA'04). We also extend several optimization results for planar graphs by Baker (J. ACM. 1994) and others to k-apex graphs.

Grötzsch's theorem states that every triangle-free planar graph is 3-colorable, and several relatively simple proofs of this fact were provided by Thomassen and other authors. It is easy to convert these proofs into quadratic-time algorithms to find a 3-coloring, but it is not clear how to find such a coloring in linear time (Kowalik used a nontrivial data structure to construct an O(n log n) algorithm). We design a linear-time algorithm to find a 3-coloring of a given triangle-free planar graph. The algorithm avoids using any complex data structures, which makes it easy to implement. As a by-product we give a yet simpler proof of Grötzsch's theorem.

It is known that computing the list chromatic number is harder than computing the chromatic number (assuming NP ≠ coNP). In fact, the problem of deciding whether a given graph is f-list-colorable for a function f : V → {c − 1, c} for c ≥ 3 is -complete. In general, it is believed that approximating list coloring is hard for dense graphs. In this paper, we are interested in sparse graphs. More specifically, we deal with nontrivial minor-closed classes of graphs, i.e., graphs excluding some Kk minor. We refine the seminal structure theorem of Robertson and Seymour, and then give an additive approximation for list-coloring within k − 2 of the list chromatic number. This improves the previous multiplicative O(k)-approximation algorithm [20]. Clearly our result also yields an additive approximation algorithm for graph coloring in a minor-closed graph class. This result may give better graph colorings than the previous multiplicative 2-approximation algorithm for graph coloring in a minor-closed graph class [6]. Our structure theorem is of independent interest in the sense that it gives rise to a new insight on well-connected H-minor-free graphs. In particular, this class of graphs can be easily decomposed into two parts so that one part has bounded treewidth and the other part is a disjoint union of bounded-genus graphs. Moreover, we can control the number of edges between the two parts. The proof method itself tells us how knowledge of a local structure can be used to gain a global structure, which gives new insight on how to decompose a graph with the help of local-structure information.

A k-list-assignment for a graph G assigns to each vertex v of G a list L(v) of admissible colors, where |L(v)| ≥ k. A graph is k-list-colorable (or k-choosable) if it can be properly colored from the lists for every k-list-assignment. We prove the following conjecture posed by Thomassen in 1994: “There are only finitely many list-color-critical graphs with all lists of cardinality at least 5 on any fixed surface.” This generalizes the well-known result of Thomassen on the usual graph coloring case. We use this theorem and specific parts of its proof to resolve the complexity status of the following problem about k-list-coloring graphs on a fixed surface S, where k is a fixed positive integer. Input: A graph G embedded in the surface S. Question: Is G k-choosable? If not, provide a certificate (a list-color-critical subgraph and the corresponding k-list-assignment). The cases k = 3, 4 are known to be NP-hard (actually even -complete), and the cases k = 1, 2 are easy. Our main results imply that the problem is tractable for every k ≥ 5. In fact, together with our recent algorithmic result, we are able to solve it in linear time when k ≥ 5. Our proof yields even more: if the input graph is k-list-colorable, then for any k-listassignment L, we can construct an L-coloring of G in linear time. This generalizes the well-known linear-time algorithms for planar graphs by Nishizeki and Chiba (for 5-coloring), and Thomassen (for 5-list-coloring). We also give a polynomial-time algorithm to resolve the following question: Input: A graph G in the surface S, and a k-listassignment L, where k = 5. Question: Does G admit an L-coloring? If not, provide a certificate for this. If yes, then return an L-coloring. If the graph G is k-list-colorable, then our first result gives a linear time solution. However, the second problem is more general, since it provides a coloring (or a small obstruction) for an arbitrary graph in S. We also use our main theorem to prove another conjecture that was proposed recently by Thomassen: “For every fixed surface S, there exists a positive constant c such that every 5-list-colorable graph with n vertices embedded on S, has at least c·2n distinct 5-listcolorings for every 5-list-assignment for G.” Thomassen himself proved that this conjecture holds for usual 5-colorings. In addition to all these results, we also made partial progress towards a conjecture of Albertson concerning coloring extensions and a progress on similar questions for triangle-free graphs and graphs of larger girth.

We consider the following problem, which is called the half integral parity disjoint paths packing problem. Input: A graph G, k pair of vertices (s1, t1), (s2, t2), …, (sk, tk) in G (which are sometimes called terminals), and a parity li for each i with 1 ≤ i ≤ k, where li = 0 or 1. Output : Paths P1, …, Pk in G such that Pi joins si and ti for i = 1, 2, …, k and parity of length of the path Pi is li, i.e, if li = 0, then length of Pi is even, and if li = 1, then length of Pi is odd for i = 1, 2, …, k. In addition, each vertex is on at most two of these paths. We present an O(mα(m, n) log n) algorithm for fixed k, where n, m are the number of vertices and the number of edges, respectively, and the function α(m, n) is the inverse of the Ackermann function (see by Tarjan [43]). This is the first polynomial time algorithm for this problem, and generalizes polynomial time algorithms by Kleinberg [23] and Kawarabayashi and Reed [20], respectively, for the half integral disjoint paths packing problem, i.e., without the parity requirement. As with the Robertson-Seymour algorithm to solve the k disjoint paths problem, in each iteration, we would like to either use a huge clique minor as a “crossbar”, or exploit the structure of graphs in which we cannot find such a minor. Here, however, we must maintain the parity of the paths and can only use an “odd clique minor”. We must also describe the structure of those graphs in which we cannot find such a minor and discuss how to exploit it. We also have algorithms running in O(m(1+∊)) time for any ∊ > 0 for this problem, if k is up to o(log log log n) for general graphs, up to o(log log n) for planar graphs, and up to o(log log n/g) for graphs on the surface, where g is Euler genus. Furthermore, if k is fixed, then we have linear time algorithms for the planar case and for the bounded genus case.

In this paper, we consider the problem of finding an induced cycle passing through k given vertices, which we call the induced cycle problem. The significance of finding induced cycles stems from the fact that precise characterization of perfect graphs would require structures of graphs without an odd induced cycle, and its complement. There has been huge progress in the recent years, especially, the Strong Perfect Graph Conjecture was solved in [6]. Concerning recognition of perfect graphs, there had been a long-standing open problem for detecting an odd hole and its complement, and finally this was solved in [4]. Unfortunately, the problem of finding an induced cycle passing through two given vertices is NP-complete in a general graph [2]. However, if the input graph is constrained to be planar and k is fixed, then the induced cycle problem can be solved in polynomial time [13, 14, 16]. In particular, an O(n2) time algorithm is given for the case k = 2 by McDiarmid, Reed, Schrijver and Shepherd [18], where n is the number of vertices of the input graph. Our main results in this paper are to improve their result in the following sense. 1. The number of vertices k is allowed to be non-trivially super constant number, up to . More precisely, when , then the ICP in planar graphs can be solved in O(n2+∊) time for any ∊ > 0. 2. The time complexity is linear if the given graph is planar and k is fixed. 3. The above results are extended to graphs embedded in a fixed surface. We note that the linear time algorithm (the second result) is independent from the first result. Let us point out that we give the first polynomial time algorithm for the problem for the bounded genus case. In fact, our proof gives a short proof of a result announced in [20] (without complete proof) which gives a linear time algorithm for the disjoint paths problem for fixed k for the bounded genus case. We also extend this result to the induced disjoint paths problem. Let us observe that if k is as a part of the input, then the problem is still NP-complete, and so we need to impose some condition on k.

The famous Hadwiger's conjecture asserts that every graph with no Kt-minor is (t-1)-colorable. The case t=5 is known to be equivalent to the Four Color Theorem by Wagner, and the case t=6 is settled by Robertson, Seymour and Thomas. So far the cases t ≥ 7 are wide open. In this paper, we prove the following two theorems: There is an O(n2) algorithm to decide whether or not a given graph G satisfies Hadwiger's conjecture for the case t. Every minimal counterexample to Hadwiger's conjecture for the case t has at most f(t) vertices for some explicit bound f(t). The bound f(t) is at most pppt, where p=101010t. Our proofs for both results use the well-known result by Thomassen [46] for 5-list-coloring planar graphs, together with some results (but not the decomposition theorem) of Graph Minors in [36]. Concerning the first result, we prove the following stronger theorem: For a given graph G and any fixed t, there is an O(n2) algorithm to output one of the following: a (t-1)-coloring of G, or a Kt-minor of G, or a minor H of G of order at most f(t) such that H does not have a Kt-minor nor is (t-1)-colorable. The last conclusion implies that H is a counterexample to Hadwiger's conjecture with at most f(t) vertices for the case t. The time complexity of the algorithm matches the best known algorithms for 4-coloring planar graphs (the Four Color Theorem), due to Appel and Hakken, and Robertson, Sanders, Seymour and Thomas, respectively. Let us observe that when t=5, the algorithm gives rise to an algorithm for the Four Color Theorem. The second theorem follows from our structure theorem, which has the following corollary: Every minimal counterexample G to Hadwiger's conjecture for the case t either has at most f(t) vertices, or has a vertex set Z of order at most t-5 such that G-Z is planar. It follows from the Four Color Theorem that the second assertion does not happen to any minimal counterexample to Hadwiger's conjecture for the case t. Thus in constant time, we can decide Hadwiger's conjecture for the case t.

We provide a complete list of 6-critical graphs that can be embedded on the Klein bottle settling a problem of Thomassen [J. Combin. Theory Ser. B, 70 (1997), pp. 67–100, Problem 3]. The list consists of nine nonisomorphic graphs which have altogether 18 nonisomorphic 2-cell embeddings and one embedding that is not 2-cell.

The crossing number of a graph is the minimum number of crossings in a drawing of the graph in the plane. Our main result is that every graph G that does not contain a fixed graph as a minor has crossing number O(Δn), where G has n vertices and maximum degree Δ. This dependence on n and Ø is best possible. This result answers an open question of Wood and Telle [New York J. Mathematics, 2007], who proved the best previous bound of O(Ø2n).

For every fixed surface S, orientable or non-orientable, and a given graph G, Mohar (STOC'96 and Siam J. Discrete Math. (1999)) described a linear time algorithm which yields either an embedding of G in S or a minor of G which is not embeddable in S and is minimal with this property. That algorithm, however, needs a lot of lemmas which spanned six additional papers. In this paper, we give a new linear time algorithm for the same problem. The advantages of our algorithm are the following: 1. The proof is considerably simpler: it needs only about 10 pages, and some results (with rather accessible proofs) from graph minors theory, while Mohar's original algorithm and its proof occupy more than 100 pages in total. 2. The hidden constant (depending on the genus g of the surface S) is much smaller. It is singly exponential in g, while it is doubly exponential in Mohar's algorithm. As a spinoff of our main result, we give another linear time algorithm, which is of independent interest. This algorithm computes the genus and constructs minimum genus embeddings of graphs of bounded tree-width. This resolves a conjecture by Neil Robertson and solves one of the most annoying long standing open question about complexity of algorithms on graphs of bounded tree-width.

For every surface S (orientable or non-orientable), we give a linear time algorithm to test the graph isomorphism of two graphs, one of which admits an embedding of face-width at least 3 into S. This improves a previously known algorithm whose time complexity is nO(g), where g is the genus of S. This is the first algorithm for which the degree of polynomial in the time complexity does not depend on g. The above result is based on two linear time algorithms, each of which solves a problem that is of independent interest. The first of these problems is the following one. Let S be a fixed surface. Given a graph G and an integer k ≥ 3, we want to find an embedding of G in S of face-width at least k, or conclude that such an embedding does not exist. It is known that this problem is NP-hard when the surface is not fixed. Moreover, if there is an embedding, the algorithm can give all embeddings of face-width at least k, up to Whitney equivalence. Here, the face-width of an embedded graph G is the minimum number of points of G in which some non-contractible closed curve in the surface intersects the graph. In the proof of the above algorithm, we give a simpler proof and a better bound for the theorem by Mohar and Robertson concerning the number of polyhedral embeddings of 3-connected graphs. The second ingredient is a linear time algorithm for map isomorphism and Whitney equivalence. This part generalizes the seminal result of Hopcroft and Wong that graph isomorphism can be decided in linear time for planar graphs.

Egawa and Saito proved that every k-connected graph with girth at least 4 has an induced cycle C such that $G-V(C)$ is $(k-3)$-connected, and every edge of C is contractible. This means that we can find not only a nonseparating cycle C but also one that consists of contractible edges. Motivated by this result, we prove that if G is a k-connected graph which does not contain $K_4^{-}$, then G has an induced cycle C such that $G - V(C)$ is $(k-2)$-connected and either every edge of C is k-contractible or C is a triangle. As a corollary of this result, we get the following result: Every k-connected graph with girth at least 4 has an induced cycle C such that $G-V(C)$ is $(k-2)$-connected, and every edge of C is contractible. This theorem is a generalization of some known theorems. In particular, this generalizes the above-mentioned result proved by Egawa and Saito and the result of Egawa which says that a k-connected graph with girth at least 4 has an induced cycle C such that $G-V(C)$ is $(k-2)$-connected.

In this paper, we shall characterize triangulations on the Klein bottle without $K_6$-minors. Our characterization implies that every 5-connected triangulation on the Klein bottle has a $K_6$-minor. The connectivity “5" is best possible in a sense that there is a 4-connected triangulation on the Klein bottle without $K_6$-minors.

We show that for every fixed k, there is a linear time algorithm that decides whether or not a given graph has crossing number at most k, and if this is the case, computes a drawing of the graph in the plane with at most k crossings. This answers the question posed by Grohe (STOC'01 and JCSS 2004). Our algorithm can be viewed as a generalization of the seminal result by Hopcroft and Tarjan lin1, which determines if a given graph is planar in linear time.

It is well-known (Feige and Kilian [24], Håstad [39]) that approximating the chromatic number within a factor of n1-ε cannot be done in polynomial time for ε>0, unless coRP = NP. Computing the list-chromatic number is much harder than determining the chromatic number. It is known that the problem of deciding if the list-chromatic number is k, where k ≥ 3, is Π2p-complete [37].In this paper, we focus on minor-closed and odd-minor-closed families of graphs. In doing that, we may as well consider only graphs without Kk-minors and graphs without odd Kk-minors for a fixed value of k, respectively. Our main results are that there is a polynomial time approximation algorithm for the list-chromatic number of graphs without Kk-minors and there is a polynomial time approximation algorithm for the chromatic number of graphs without odd-Kk-minors. Their time complexity is O(n3) and O(n4), respectively. The algorithms have multiplicative error O(√log k) and additive error O(k), and the multiplicative error occurs only for graphs whose list-chromatic number and chromatic number are Θ(k), respectively.Let us recall that H has an odd complete minor of order l if there are l vertex disjoint trees in H such that every two of them are joined by an edge, and in addition, all the vertices of trees are two-colored in such a way that the edges within the trees are bichromatic, but the edges between trees are monochromatic. Let us observe that the complete bipartite graph Kn/2,n/2 contains a Kk-minor for k ≤ n/2, but on the other hand, it does not contain an odd Kk-minor for any k ≥ 3. Odd K5-minor-free graphs are closely related to one field of discrete optimization which is finding conditions under which a given polyhedron has integer vertices, so that integer optimization problems can be solved as linear programs. See [33, 34, 64]. Also, the odd version of the well-known Hadwiger's conjecture has been considered, see [28].Our main idea involves precoloring extension. This idea is used in many results; one example is Thomassen's proof on his celebrated theorem on planar graphs [69].The best previously known approximation for the first result is a simple O(k √log k)-approximation following algorithm that guarantees a list-coloring with O(k √log k) colors for Kk-minor-free graphs. This follows from results of Kostochka [54, 53] and Thomason [67, 68].The best previous approximation for the second result comes from the recent result of Geelen et al. [28] who gave an O(k √log k)-approximation algorithm.We also relate our algorithm to the well-known conjecture of Hadwiger [38] and its odd version. In fact, we give an O(n3) algorithm to decide whether or not a weaker version of Hadwiger's conjecture is true. Here, by a weaker version of Hadwiger's conjecture, we mean a conjecture which says that any 27k-chromatic graph contains a Kk-minor. Also, we shall give an O(n2500k) algorithm for deciding whether or not any 2500k-chromatic graph contains an odd-Kk-minor.Let us mention that this presentation consists of two papers which are merged into this one. The first one consists of results concerning minor-closed classes of graphs by two current authors, and the other consists of results concerning odd-minor-closed classes of graphs by the first author.

At the core of the seminal graph minor theory of Robertson and Seymour is a powerful structural theorem capturing the structure of graphs excluding a fixed minor. This result is used throughout graph theory and graph algorithms, but is existential. We develop a polynomial-time algorithm using topological graph theory to decompose a graph into the structure guaranteed by the theorem: a clique-sum of pieces almost-embeddable into bounded-genus surfaces. This result has many applications. In particular we show applications to developing many approximation algorithms, including a 2-approximation to graph coloring, constant-factor approximations to treewidth and the largest grid minor, combinatorial polylogarithmic approximation to half-integral multicommodity flow, subexponential fixed-parameter algorithms, and PTASs for many minimization and maximization problems, on graphs excluding a fixed minor.

In this paper, we obtain three general reduction formulas to determine the orientable and nonorientable genera for complete tripartite graphs. As corollaries, we (1) reduce the determination of the orientable (nonorientable, respectively) genera of 75 percent (85 percent, respectively) of nonsymmetric (with respect to l,m, and n) K l,m,n to that of K m,m,n , and (2) determine the orientable and nonorientable genera for several classes of complete tripartite graphs.