BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Ken-ichi Kawarabayashi

Ken-ichi Kawarabayashi appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.COData Structures and AlgorithmsDiscrete MathematicsArtificial IntelligenceComputation and LanguageMachine LearningComputer VisionComputer Science and Game TheoryCryptography and SecurityDistributed, Parallel, and Cluster ComputingInformation RetrievalLogic in Computer ScienceNeural and Evolutionary Computingphysics.soc-phquant-phSocial and Information Networks

Catalog footprint

What is connected

42works
16topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

42 published item(s)

preprint2022arXiv

Online Task Assignment Problems with Reusable Resources

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)\geq 1/3$. We also evaluate our proposed algorithm with numerical experiments.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Query Obfuscation Semantic Decomposition

We propose a method to protect the privacy of search engine users by decomposing the queries using semantically \emph{related} and unrelated \emph{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 \emph{obfuscity} achieved through the proposed query anonymisation method and the \emph{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.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

The Directed Grid Theorem

The grid theorem, originally proved by Robertson and Seymour in Graph Minors V in 1986, 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. In the mid-90s, Reed and Johnson, Robertson, Seymour and Thomas (see [Reed 97, Johnson, Robertson, Seymour, Thomas 01]), independently, conjectured an analogous theorem for directed graphs, i.e. the existence of a function f : N -> N 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 give a proof of this conjecture for planar digraphs. But for over a decade, this was the most general case proved for the Reed, Johnson, Robertson, Seymour and Thomas conjecture. Only very recently, this result has been extended to all classes of digraphs excluding a fixed undirected graph as a minor (see [Kawarabayashi, Kreutzer 14]). In this paper, nearly two decades after the conjecture was made, we are finally able to confirm the Reed, Johnson, Robertson, Seymour and Thomas conjecture in full generality and to prove the directed grid theorem. As consequence of our results we are able to improve results in Reed et al. in 1996 [Reed, Robertson, Seymour, Thomas 96] (see also [Open Problem Garden]) on disjoint cycles of length at least l and in [Kawarabayashi, Kobayashi, Kreutzer 14] on quarter-integral disjoint paths. We expect many more algorithmic results to follow from the grid theorem.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

A unified half-integral Erdős-Pósa theorem for cycles in graphs labelled by multiple abelian groups

Erdős and Pósa proved in 1965 that there is a duality between the maximum size of a packing of cycles and the minimum size of a vertex set hitting all cycles. Such a duality does not hold if we restrict to odd cycles. However, in 1999, Reed proved an analogue for odd cycles by relaxing packing to half-integral packing. We prove a far-reaching generalisation of the theorem of Reed; if the edges of a graph are labelled by finitely many abelian groups, then there is a duality between the maximum size of a half-integral packing of cycles whose values avoid a fixed finite set for each abelian group and the minimum size of a vertex set hitting all such cycles. A multitude of natural properties of cycles can be encoded in this setting, for example cycles of length at least $\ell$, cycles of length $p$ modulo $q$, cycles intersecting a prescribed set of vertices at least $t$ times, and cycles contained in given $\mathbb{Z}_2$-homology classes in a graph embedded on a fixed surface. Our main result allows us to prove a duality theorem for cycles satisfying a fixed set of finitely many such properties.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Automorphism groups of maps in linear time

By a map we mean 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. 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.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks

We study how neural networks trained by gradient descent extrapolate, i.e., what they learn outside the support of the training distribution. Previous works report mixed empirical results when extrapolating with neural networks: while feedforward neural networks, a.k.a. multilayer perceptrons (MLPs), do not extrapolate well in certain simple tasks, Graph Neural Networks (GNNs) -- structured networks with MLP modules -- have shown some success in more complex tasks. Working towards a theoretical explanation, we identify conditions under which MLPs and GNNs extrapolate well. First, we quantify the observation that ReLU MLPs quickly converge to linear functions along any direction from the origin, which implies that ReLU MLPs do not extrapolate most nonlinear functions. But, they can provably learn a linear target function when the training distribution is sufficiently "diverse". Second, in connection to analyzing the successes and limitations of GNNs, these results suggest a hypothesis for which we provide theoretical and empirical evidence: the success of GNNs in extrapolating algorithmic tasks to new data (e.g., larger graphs or edge weights) relies on encoding task-specific non-linearities in the architecture or features. Our theoretical analysis builds on a connection of over-parameterized networks to the neural tangent kernel. Empirically, our theory holds across different training settings.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions

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 $\tilde{O}(\max(\sqrt{d}, \sqrt{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 $\tilde{O}(\cdot)$ 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 C${}^2$UCB algorithm proposed by Qin, Chen, and Zhu (2014) has the optimal regret bound $\tilde{O}(d\sqrt{kT} + dk)$ for the partition matroid constraints. For general constraints, we propose an algorithm that modifies the reward estimates of arms in the C${}^2$UCB 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.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Quickly excluding a non-planar graph

A cornerstone theorem in the Graph Minors series of Robertson and Seymour is the result that every graph $G$ with no minor isomorphic to a fixed graph $H$ has a certain structure. The structure can then be exploited to deduce far-reaching consequences. The exact statement requires some explanation, but roughly it says that there exist integers $k,n$ depending on $H$ only such that $0<k<n$ and for every $n\times n$ grid minor $J$ of $G$ the graph $G$ has a a $k$-near embedding in a surface $Σ$ that does not embed $H$ in such a way that a substantial part of $J$ is embedded in $Σ$. Here a $k$-near embedding means that after deleting at most $k$ vertices the graph can be drawn in $Σ$ without crossings, except for local areas of non-planarity, where crossings are permitted, but at most $k$ of these areas are attached to the rest of the graph by four or more vertices and inside those the graph is constrained in a different way, again depending on the parameter $k$. The original and only proof so far is quite long and uses many results developed in the Graph Minors series. We give a proof that uses only our earlier paper [A new proof of the flat wall theorem, {\it J.~Combin.\ Theory Ser.\ B \bf 129} (2018), 158--203] and results from graduate textbooks. Our proof is constructive and yields a polynomial time algorithm to construct such a structure. We also give explicit constants for the structure theorem, whereas the original proof only guarantees the existence of such constants.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

RelWalk A Latent Variable Model Approach to Knowledge Graph Embedding

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 log-likelihood 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.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Improved Distributed Approximations for Maximum Independent Set

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 the running time of finding a \emph{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 main result in this work is 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 \emph{exponential} speed-up in the running time over the previous best known result. Due to a lower bound of $Ω(\sqrt{\log n/\log \log n})$ that was given by Kuhn, Moscibroda and Wattenhofer [JACM, 2016] on the number of rounds for any (possibly randomized) algorithm that finds a maximal independent set (even in the LOCAL model) this result implies that finding a $(1+ε)Δ$-approximation for $\MaxIS$ is exponentially easier than $\MIS$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

What Can Neural Networks Reason About?

Neural networks have succeeded in many reasoning tasks. Empirically, these tasks require specialized network structures, e.g., Graph Neural Networks (GNNs) perform well on many such tasks, but less structured networks fail. Theoretically, there is limited understanding of why and when a network structure generalizes better than others, although they have equal expressive power. In this paper, we develop a framework to characterize which reasoning tasks a network can learn well, by studying how well its computation structure aligns with the algorithmic structure of the relevant reasoning process. We formally define this algorithmic alignment and derive a sample complexity bound that decreases with better alignment. This framework offers an explanation for the empirical success of popular reasoning models, and suggests their limitations. As an example, we unify seemingly different reasoning tasks, such as intuitive physics, visual question answering, and shortest paths, via the lens of a powerful algorithmic paradigm, dynamic programming (DP). We show that GNNs align with DP and thus are expected to solve these tasks. On several reasoning tasks, our theory is supported by empirical results.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

A coherent Ising machine for MAX-CUT problems : Performance evaluation against semidefinite programming relaxation and simulated annealing

Combinatorial optimization problems are computationally hard in general, but they are ubiquitous in our modern life. A coherent Ising machine (CIM) based on a multiple-pulse degenerate optical parametric oscillator (DOPO) is an alternative approach to solve these problems by a specialized physical computing system. To evaluate its potential performance, computational experiments are performed on maximum cut (MAX-CUT) problems against traditional algorithms such as semidefinite programming relaxation of Goemans-Williamson and simulated annealing by Kirkpatrick, et al. The numerical results empirically suggest that the almost constant computation time is required to obtain the reasonably accurate solutions of MAX-CUT problems on a CIM with the number of vertices up to $2 \times 10^4$ and the number of edges up to $10^8$.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

A New Proof of the Flat Wall Theorem

We give an elementary and self-contained proof, and a numerical improvement, of a weaker form of the excluded clique minor theorem of Robertson and Seymour, the following. Let t,r>0 be integers, and let R=49152t^{24}(40t^2+r). An r-wall is obtained from a (2r x r)-grid by deleting every odd vertical edge in every odd row and every even vertical edge in every even row, then deleting the two resulting vertices of degree one, and finally subdividing edges arbitrarily. The vertices of degree two that existed before the subdivision are called the pegs of the r-wall. Let G be a graph with no K_t minor, and let W be an R-wall in G. We prove that there exist a subset A of V(G) of size at most 12288t^{24} and an r-subwall W' of W such that V(W') is disjoint from A and W' is a flat wall in G-A in the following sense. There exists a separation (X,Y) of G-A such that X\cap Y is a subset of the vertex set of the cycle C' that bounds the outer face of W', V(W') is a subset of Y, every peg of W' belongs to X and the graph G[Y] can almost be drawn in the unit disk with the vertices X\cap Y drawn on the boundary of the disk in the order determined by C'. Here almost means that the assertion holds after repeatedly removing parts of the graph separated from X\cap Y by a cutset Z of size at most three, and adding all edges with both ends in Z. Our proof gives rise to an algorithm that runs in polynomial time even when r and t are part of the input instance. The proof is self-contained in the sense that it uses only results whose proofs can be found in textbooks.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Optimal Pricing for Submodular Valuations with Bounded Curvature

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.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Successor-Invariant First-Order Logic on Graphs with Excluded Topological Subgraphs

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.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

The Erdos-Posa Property for Directed Graphs

A classical result by Erdos and Posa states that there is a function $f: {\mathbb N} \rightarrow {\mathbb N}$ such that for every $k$, every graph $G$ contains $k$ pairwise vertex disjoint cycles or a set $T$ of at most $f(k)$ vertices such that $G-T$ is acyclic. The generalisation of this result to directed graphs is known as Younger's conjecture and was proved by Reed, Robertson, Seymour and Thomas in 1996. This so-called Erdos-Posa-property can naturally be generalised to arbitrary graphs and digraphs. Robertson and Seymour proved that a graph $H$ has the Erdos-Posa-property if, and only if, $H$ is planar. In this paper we study the corresponding problem for digraphs. We obtain a complete characterisation of the class of strongly connected digraphs which have the Erdos-Posa-property (both for topological and butterfly minors). We also generalise this result to classes of digraphs which are not strongly connected. In particular, we study the class of vertex-cyclic digraphs (digraphs without trivial strong components). For this natural class of digraphs we obtain a nearly complete characterisation of the digraphs within this class with the Erdos-Posa-property. In particular we give positive and algorithmic examples of digraphs with the Erdos-Posa-property by using directed tree decompositions in a novel way.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Connectivity Preserving Iterative Compaction and Finding 2 Disjoint Rooted Paths in Linear Time

In this paper we show how to combine two algorithmic techniques to obtain linear time algorithms for various optimization problems on graphs, and present a subroutine which will be useful in doing so. The first technique is iterative shrinking. In the first phase of an iterative shrinking algorithm, we construct a sequence of graphs of decreasing size $G_1,\ldots,G_\ell$ where $G_1$ is the initial input, $G_\ell$ is a graph on which the problem is easy, and $G_i$ is obtained from $G_{i+1}$ via some shrinking algorithm. In the second phase we work through the sequence in reverse, repeatedly constructing a solution for a graph from the solution for its successor. In an iterative compaction algorithm, we insist that the graphs decrease by a constant fraction of the entire graph. Another approach to solving optimization problems is to exploit the structural properties implied by the connectivity of the input graph. This approach can be used on graphs which are not highly connected by decomposing an input graph into its highly connected pieces, solving subproblems on these specially structured pieces and then combining their solutions. We combine these two techniques by developing compaction algorithms which when applied to the highly connected pieces preserve their connectivity properties. The structural properties this connectivity implies can be helpful both in finding further compactions in later iterations and when we are manipulating solutions in the second phase of an iterative compaction algorithm. To illustrate how this compaction algorithm can be used as a subroutine, we present a linear time algorithm that given four vertices $\{s_1,s_2,t_1,t_2\}$ of a graph $G$, either finds a pair of disjoint paths $P_1$ and $P_2$ of $G$ such that $P_i$ has endpoints $s_i$ and $t_i$, or returns a planar embedding of an auxiliary graph which shows that no such pair exists.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Embedding Semantic Relations into Word Representations

Learning representations for semantic relations is important for various tasks such as analogy detection, relational search, and relation classification. Although there have been several proposals for learning representations for individual words, learning word representations that explicitly capture the semantic relations between words remains under developed. We propose an unsupervised method for learning vector representations for words such that the learnt representations are sensitive to the semantic relations that exist between two words. First, we extract lexical patterns from the co-occurrence contexts of two words in a corpus to represent the semantic relations that exist between those two words. Second, we represent a lexical pattern as the weighted sum of the representations of the words that co-occur with that lexical pattern. Third, we train a binary classifier to detect relationally similar vs. non-similar lexical pattern pairs. The proposed method is unsupervised in the sense that the lexical pattern pairs we use as train data are automatically sampled from a corpus, without requiring any manual intervention. Our proposed method statistically significantly outperforms the current state-of-the-art word representations on three benchmark datasets for proportional analogy detection, demonstrating its ability to accurately capture the semantic relations among words.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Graph Isomorphism for Bounded Genus Graphs In Linear Time

For every integer $g$, isomorphism of graphs of Euler genus at most $g$ can be decided in linear time. This improves previously known algorithms whose time complexity is $n^{O(g)}$ (shown in early 1980's), and in fact, this is the first fixed-parameter tractable algorithm for the graph isomorphism problem for bounded genus graphs in terms of the Euler genus $g$. Our result also generalizes the seminal result of Hopcroft and Wong in 1974, which says that the graph isomorphism problem can be decided in linear time for planar graphs. Our proof is quite lengthly and complicated, but if we are satisfied with an $O(n^3)$ time algorithm for the same problem, the proof is shorter and easier.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Joint Word Representation Learning using a Corpus and a Semantic Lexicon

Methods for learning word representations using large text corpora have received much attention lately due to their impressive performance in 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 consider the 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 WordNet that 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 the knowledge from semantic lexicons?. For this purpose, we propose a joint word representation learning method that simultaneously predicts the 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 word representations on several benchmark datasets for semantic similarity and word analogy.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

The odd Hadwiger's conjecture is "almost'' decidable

The odd Hadwiger's conjecture, made by Gerads and Seymour in early 1990s, is an analogue of the famous Hadwiger's conjecture. It says that every graph with no odd $K_t$-minor is $(t-1)$-colorable. This conjecture is known to be true for $t \leq 5$, but the cases $t \geq 5$ are wide open. So far, the most general result says that every graph with no odd $K_t$-minor is $O(t \sqrt{\log t})$-colorable. In this paper, we tackle this conjecture from an algorithmic view, and show the following: For a given graph $G$ and any fixed $t$, there is a polynomial time algorithm to output one of the following: \begin{enumerate} \item a $(t-1)$-coloring of $G$, or \item an odd $K_{t}$-minor of $G$, or \item after making all "reductions" to $G$, the resulting graph $H$ (which is an odd minor of $G$ and which has no reductions) has a tree-decomposition $(T, Y)$ such that torso of each bag $Y_t$ is either \begin{itemize} \item of size at most $f_1(t) \log n$ for some function $f_1$ of $t$, or \item a graph that has a vertex $X$ of order at most $f_2(t)$ for some function $f_2$ of $t$ such that $Y_t-X$ is bipartite. Moreover, degree of $t$ in $T$ is at most $f_3(t)$ for some function $f_3$ of $t$. \end{itemize} \end{enumerate} Let us observe that the last odd minor $H$ is indeed a minimal counterexample to the odd Hadwiger's conjecture for the case $t$. So our result says that a minimal counterexample satisfies the lsat conclusion.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Unsupervised Cross-Domain Word Representation Learning

Meaning of a word varies from one domain to another. Despite this important domain dependence in word semantics, existing word representation learning methods are bound to a single domain. Given a pair of \emph{source}-\emph{target} domains, we propose an unsupervised method for learning domain-specific word representations that accurately capture the domain-specific aspects of word semantics. First, we select a subset of frequent words that occur in both domains as \emph{pivots}. Next, we optimize an objective function that enforces two constraints: (a) for both source and target domain documents, pivots that appear in a document must accurately predict the co-occurring non-pivots, and (b) word representations learnt for pivots must be similar in the two domains. Moreover, we propose a method to perform domain adaptation using the learnt word representations. Our proposed method significantly outperforms competitive baselines including the state-of-the-art domain-insensitive word representations, and reports best sentiment classification accuracies for all domain-pairs in a benchmark dataset.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Beyond the Euler characteristic: Approximating the genus of general graphs

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 '89] 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 trivial $O(n/g)$-approximation that follows from bounds on the Euler characteristic. In this paper, we give the first non-trivial approximation algorithm for this problem. Specifically, we present a polynomial-time algorithm which given a graph $G$ of Euler genus $g$ outputs an embedding of $G$ into a surface of Euler genus $g^{O(1)}$. Combined with the above $O(n/g)$-approximation, our result also implies a $O(n^{1-α})$-approximation, for some universal constant $α>0$. Our approximation algorithm also has implications for the design of algorithms on graphs of small genus. Several of these algorithms require that an embedding of the graph into a surface of small genus is given as part of the input. Our result implies that many of these algorithms can be implemented even when the embedding of the input graph is unknown.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Efficient SimRank Computation via Linearization

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.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Existence of outsiders as a characteristic of online communication networks

Online social networking services (SNSs) involve communication activities between large number of individuals over the public Internet and their crawled records are often regarded as proxies of real (i.e., offline) interaction structure. However, structure observed in these records might differ from real counterparts because individuals may behave differently online and non-human accounts may even participate. To understand the difference between online and real social networks, we investigate an empirical communication network between users on Twitter, which is perhaps one of the largest SNSs. We define a network of user pairs that send reciprocal messages. Based on the mixing pattern observed in this network, we argue that this network differs from conventional understandings in the sense that there is a small number of distinctive users that we call outsiders. Outsiders do not belong to any user groups but they are connected with different groups, while not being well connected with each other. We identify outsiders by maximizing the degree assortativity coefficient of the network via node removal, thereby confirming that local structural properties of outsiders identified are consistent with our hypothesis. Our findings suggest that the existence of outsiders should be considered when using Twitter communication networks for social network analysis.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Generating Approximate Solutions to the TTP using a Linear Distance Relaxation

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.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Learning Word Representations from Relational Graphs

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 connected 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 representations 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.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Scheduling Bipartite Tournaments to Minimize Total Travel Distance

In many professional sports leagues, teams from opposing leagues/conferences compete against one another, playing inter-league games. This is an example of a bipartite tournament. In this paper, we consider the problem of reducing the total travel distance of bipartite tournaments, by analyzing inter-league scheduling from the perspective of discrete optimization. This research has natural applications to sports scheduling, especially for leagues such as the National Basketball Association (NBA) where teams must travel long distances across North America to play all their games, thus consuming much time, money, and greenhouse gas emissions. We introduce the Bipartite Traveling Tournament Problem (BTTP), the inter-league variant 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 theoretical results to the 12-team Nippon Professional Baseball (NPB) league in Japan, producing a provably-optimal schedule requiring 42950 kilometres of total team travel, a 16% reduction compared to the actual distance traveled by these teams during the 2010 NPB season. We also develop a nearly-optimal inter-league tournament for the 30-team NBA league, just 3.8% higher than the trivial theoretical lower bound.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Three-coloring triangle-free planar graphs in linear time

Grotzsch's theorem states that every triangle-free planar graph is 3-colorable. 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 Grotzsch's theorem.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Cliques in Odd-Minor-Free Graphs

This paper is about: (1) bounds on the number of cliques in a graph in a particular class, and (2) algorithms for listing all cliques in a graph. We present a simple algorithm that lists all cliques in an $n$-vertex graph in O(n) time per clique. For O(1)-degenerate graphs, such as graphs excluding a fixed minor, we describe a O(n) time algorithm for listing all cliques. We prove that graphs excluding a fixed odd-minor have $O(n^2)$ cliques (which is tight), and conclude a $O(n^3)$ time algorithm for listing all cliques.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Combinatorial coloring of 3-colorable graphs

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 $\tO(n^{4/11})$ colors. This is the first combinatorial improvement of Blum's $\tO(n^{3/8})$ bound from FOCS'90. Like Blum's algorithm, our new algorithm composes nicely with recent semi-definite approaches. The current best bound is $O(n^{0.2072})$ colors by Chlamtac from FOCS'07. We now bring it down to $O(n^{0.2038})$ colors.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Edge-colouring seven-regular planar graphs

A conjecture due to the fourth author states that every $d$-regular planar multigraph can be $d$-edge-coloured, provided that for every odd set $X$ of vertices, there are at least $d$ edges between $X$ and its complement. For $d = 3$ this is the four-colour theorem, and the conjecture has been proved for all $d\le 8$, by various authors. In particular, two of us proved it when $d=7$; and then three of us proved it when $d=8$. The methods used for the latter give a proof in the $d=7$ case that is simpler than the original, and we present it here.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

List-coloring embedded graphs

For any fixed surface Sigma of genus g, we give an algorithm to decide whether a graph G of girth at least five embedded in Sigma 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.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Choosability of planar graphs of girth 5

Thomassen proved that any plane graph of girth 5 is list-colorable from any list assignment such that all vertices have lists of size two or three and the vertices with list of size two are all incident with the outer face and form an independent set. We present a strengthening of this result, relaxing the constraint on the vertices with list of size two. This result is used to bound the size of the 3-list-coloring critical plane graphs with one precolored face.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus, and Minor-Free Graphs

A (1 + eps)-approximate distance oracle for a graph is a data structure that supports approximate point-to-point shortest-path-distance queries. The most relevant measures for a distance-oracle construction are: space, query time, and preprocessing time. There are strong distance-oracle constructions known for planar graphs (Thorup, JACM'04) and, subsequently, minor-excluded graphs (Abraham and Gavoille, PODC'06). However, these require Omega(eps^{-1} n lg n) space for n-node graphs. We argue that a very low space requirement is essential. Since modern computer architectures involve hierarchical memory (caches, primary memory, secondary memory), a high memory requirement in effect may greatly increase the actual running time. Moreover, we would like data structures that can be deployed on small mobile devices, such as handhelds, which have relatively small primary memory. In this paper, for planar graphs, bounded-genus graphs, and minor-excluded graphs we give distance-oracle constructions that require only O(n) space. The big O hides only a fixed constant, independent of εand independent of genus or size of an excluded minor. The preprocessing times for our distance oracle are also faster than those for the previously known constructions. For planar graphs, the preprocessing time is O(n lg^2 n). However, our constructions have slower query times. For planar graphs, the query time is O(eps^{-2} lg^2 n). For our linear-space results, we can in fact ensure, for any delta > 0, that the space required is only 1 + delta times the space required just to represent the graph itself.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Minimum k-way cut of bounded size is fixed-parameter tractable

We consider a the minimum k-way cut problem for unweighted 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) in s. More precisely, for s=O(1), our algorithm runs in quadratic time while we have a different 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 in k even for simple unweighted graphs. Downey et al. asked about the status for planar graphs. Our result implies tractability in k for the planar graphs since the minimum k-way cut of a planar graph is of size at most 6k (more generally, we get tractability in k for any graph class with k-way cuts of size limited by is a function of k, e.g., bounded degree graphs, or simple graphs with an excluded minor). 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 in terms of k. Marx [2004] proved that finding a minimum k-way vertex cut of size s is also W[1] hard in 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.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Finding topological subgraphs is fixed-parameter tractable

We show that for every fixed undirected graph $H$, there is a $O(|V(G)|^3)$ time algorithm that tests, given a graph $G$, 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.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

The Erdös-Pósa property for clique minors in highly connected graphs

We prove the existence of a function f: N^2 -> N such that for all p,k in N every (k(p-3) + 14p+14) - connected graph either has k disjoint K_p minors or contains a set of at most f(p,k) vertices whose deletion kills all its K_p minors. For fixed p > 4, the connectivity bound of about k(p-3) is smallest possible, up to an additive constant: if we assume less connectivity in terms of k, there will be no such function f.

0 citations0 reviewsNo code linkedOpen access