Source author record

Hirotaka Ono

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Discrete Mathematics Information Theory math.CO math.IT math.PR

Catalog footprint

Research overview

10works

6topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Parameterized Complexity of $(A,\ell)$ -Path Packing

Given a graph $G = (V,E)$ , $A \subseteq V$ , and integers $k$ and $\ell$ , the \textsc{ $(A,\ell)$ -Path Packing} problem asks to find $k$ vertex-disjoint paths of length $\ell$ that have endpoints in $A$ and internal points in $V \setminus A$ . We study the parameterized complexity of this problem with parameters $|A|$ , $\ell$ , $k$ , treewidth, pathwidth, and their combinations. We present sharp complexity contrasts with respect to these parameters. Among other results, we show that the problem is polynomial-time solvable when $\ell \le 3$ , while it is NP-complete for constant $\ell \ge 4$ . We also show that the problem is W[1]-hard parameterized by pathwidth ${}+|A|$ , while it is fixed-parameter tractable parameterized by treewidth ${}+\ell$ .

preprint2016arXiv

Coalescing random walks and voting on connected graphs

In a coalescing random walk, a set of particles make independent random walks on a graph. Whenever one or more particles meet at a vertex, they unite to form a single particle, which then continues the random walk through the graph. Coalescing random walks can be used to achieve consensus in distributed networks, and is the basis of the self-stabilizing mutual exclusion algorithm of Israeli and Jalfon. Let G=(V,E), be an undirected, connected n vertex graph with m edges. Let C(n) be the expected time for all particles to coalesce, when initially one particle is located at each vertex of an n vertex graph. We study the problem of bounding the coalescence time C(n) for general classes of graphs. Our main result is that C(n)= O(1/(1-lambda_2))*((log n)^4 +n/A)), where lambda_2 is the absolute value of the second largest eigenvalue of the transition matrix of the random walk, A= (sum d^2(v))/(d^2 n), d(v) is the degree of vertex v, and d is the average node degree. The parameter A is an indicator of the variability of node degrees. Thus 1 <= A =O(n), with A=1 for regular graphs.

preprint2015arXiv

Fixed-Parameter Tractability of Token Jumping on Planar Graphs

Suppose that we are given two independent sets $I_0$ and $I_r$ of a graph such that $|I_0| = |I_r|$ , and imagine that a token is placed on each vertex in $I_0$ . The token jumping problem is to determine whether there exists a sequence of independent sets which transforms $I_0$ into $I_r$ so that each independent set in the sequence results from the previous one by moving exactly one token to another vertex. This problem is known to be PSPACE-complete even for planar graphs of maximum degree three, and W[1]-hard for general graphs when parameterized by the number of tokens. In this paper, we present a fixed-parameter algorithm for the token jumping problem on planar graphs, where the parameter is only the number of tokens. Furthermore, the algorithm can be modified so that it finds a shortest sequence for a yes-instance. The same scheme of the algorithms can be applied to a wider class of graphs, $K_{3,t}$ -free graphs for any fixed integer $t \ge 3$ , and it yields fixed-parameter algorithms.

preprint2015arXiv

Subgraph Domatic Problem and Writing Capacity of Memory Devises with Restricted State Transitions

A code design problem for memory devises with restricted state transitions is formulated as a combinatorial optimization problem that is called a subgraph domatic partition (subDP) problem. If any neighbor set of a given state transition graph contains all the colors, then the coloring is said to be valid. The goal of a subDP problem is to find a valid coloring with the largest number of colors for a subgraph of a given directed graph. The number of colors in an optimal valid coloring gives the writing capacity of a given state transition graph. The subDP problems are computationally hard; it is proved to be NP-complete in this paper. One of our main contributions in this paper is to show the asymptotic behavior of the writing capacity $C(G)$ for sequences of dense bidirectional graphs, that is given by C(G)=Omega(n/ln n) where n is the number of nodes. A probabilistic method called Lovasz local lemma (LLL) plays an essential role to derive the asymptotic expression.

preprint2015arXiv

The complexity of dominating set reconfiguration

Suppose that we are given two dominating sets $D_s$ and $D_t$ of a graph $G$ whose cardinalities are at most a given threshold $k$ . Then, we are asked whether there exists a sequence of dominating sets of $G$ between $D_s$ and $D_t$ such that each dominating set in the sequence is of cardinality at most $k$ and can be obtained from the previous one by either adding or deleting exactly one vertex. This problem is known to be PSPACE-complete in general. In this paper, we study the complexity of this decision problem from the viewpoint of graph classes. We first prove that the problem remains PSPACE-complete even for planar graphs, bounded bandwidth graphs, split graphs, and bipartite graphs. We then give a general scheme to construct linear-time algorithms and show that the problem can be solved in linear time for cographs, trees, and interval graphs. Furthermore, for these tractable cases, we can obtain a desired sequence such that the number of additions and deletions is bounded by $O(n)$ , where $n$ is the number of vertices in the input graph.

preprint2014arXiv

Linear-Time Algorithm for Sliding Tokens on Trees

Suppose that we are given two independent sets $I_b$ and $I_r$ of a graph such that $|I_b|=|I_r|$ , and imagine that a token is placed on each vertex in $I_b$ . Then, the sliding token problem is to determine whether there exists a sequence of independent sets which transforms $I_b$ into $I_r$ so that each independent set in the sequence results from the previous one by sliding exactly one token along an edge in the graph. This problem is known to be PSPACE-complete even for planar graphs, and also for bounded treewidth graphs. In this paper, we thus study the problem restricted to trees, and give the following three results: (1) the decision problem is solvable in linear time; (2) for a yes-instance, we can find in quadratic time an actual sequence of independent sets between $I_b$ and $I_r$ whose length (i.e., the number of token-slides) is quadratic; and (3) there exists an infinite family of instances on paths for which any sequence requires quadratic length.

preprint2014arXiv

Reconfiguration of Cliques in a Graph

We study reconfiguration problems for cliques in a graph, which determine whether there exists a sequence of cliques that transforms a given clique into another one in a step-by-step fashion. As one step of a transformation, we consider three different types of rules, which are defined and studied in reconfiguration problems for independent sets. We first prove that all the three rules are equivalent in cliques. We then show that the problems are PSPACE-complete for perfect graphs, while we give polynomial-time algorithms for several classes of graphs, such as even-hole-free graphs and cographs. In particular, the shortest variant, which computes the shortest length of a desired sequence, can be solved in polynomial time for chordal graphs, bipartite graphs, planar graphs, and bounded treewidth graphs.

preprint2013arXiv

(Total) Vector Domination for Graphs with Bounded Branchwidth

Given a graph $G=(V,E)$ of order $n$ and an $n$ -dimensional non-negative vector $d=(d(1),d(2),\ldots,d(n))$ , called demand vector, the vector domination (resp., total vector domination) is the problem of finding a minimum $S\subseteq V$ such that every vertex $v$ in $V\setminus S$ (resp., in $V$ ) has at least $d(v)$ neighbors in $S$ . The (total) vector domination is a generalization of many dominating set type problems, e.g., the dominating set problem, the $k$ -tuple dominating set problem (this $k$ is different from the solution size), and so on, and its approximability and inapproximability have been studied under this general framework. In this paper, we show that a (total) vector domination of graphs with bounded branchwidth can be solved in polynomial time. This implies that the problem is polynomially solvable also for graphs with bounded treewidth. Consequently, the (total) vector domination problem for a planar graph is subexponential fixed-parameter tractable with respectto $k$ , where $k$ is the size of solution.

preprint2011arXiv

Minimum Certificate Dispersal with Tree Structures

Given an n-vertex graph G=(V,E) and a set R \subseteq {{x,y} | x,y \in V} of requests, we consider to assign a set of edges to each vertex in G so that for every request {u, v} in R the union of the edge sets assigned to u and v contains a path from u to v. The Minimum Certificate Dispersal Problem (MCD) is defined as one to find an assignment that minimizes the sum of the cardinality of the edge set assigned to each vertex. This problem has been shown to be LOGAPX-complete for the most general setting, and APX-hard and 2-approximable in polynomial time for dense request sets, where R forms a clique. In this paper, we investigate the complexity of MCD with sparse (tree) structures. We first show that MCD is APX-hard when R is a tree, even a star. We then explore the problem from the viewpoint of the maximum degree Δof the tree: MCD for tree request set with constant Δis solvable in polynomial time, while that with Δ=Ω(n) is 2.56-approximable in polynomial time but hard to approximate within 1.01 unless P=NP. As for the structure of G itself, we show that the problem can be solved in polynomial time if G is a tree.

preprint2010arXiv

A linear time algorithm for L(2,1)-labeling of trees

An L(2,1)-labeling of a graph $G$ is an assignment $f$ from the vertex set $V(G)$ to the set of nonnegative integers such that $|f(x)-f(y)|\ge 2$ if $x$ and $y$ are adjacent and $|f(x)-f(y)|\ge 1$ if $x$ and $y$ are at distance 2, for all $x$ and $y$ in $V(G)$ . A $k$ -L(2,1)-labeling is an assignment $f:V(G)\to\{0,..., k\}$ , and the L(2,1)-labeling problem asks the minimum $k$ , which we denote by $λ(G)$ , among all possible assignments. It is known that this problem is NP-hard even for graphs of treewidth 2, and tree is one of a very few classes for which the problem is polynomially solvable. The running time of the best known algorithm for trees had been $\mO(Δ^{4.5} n)$ for more than a decade, however, an $\mO(n^{1.75})$-time algorithm has been proposed recently, which substantially improved the previous one, where $Δ$ is the maximum degree of $T$ and $n=|V(T)|$ . In this paper, we finally establish a linear time algorithm for L(2,1)-labeling of trees.

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.

Hirotaka Ono

Research overview

Is this your work?

10 publications

Parameterized Complexity of $(A,\ell)$ -Path Packing

Coalescing random walks and voting on connected graphs

Fixed-Parameter Tractability of Token Jumping on Planar Graphs

Subgraph Domatic Problem and Writing Capacity of Memory Devises with Restricted State Transitions

The complexity of dominating set reconfiguration

Linear-Time Algorithm for Sliding Tokens on Trees

Reconfiguration of Cliques in a Graph

(Total) Vector Domination for Graphs with Bounded Branchwidth

Minimum Certificate Dispersal with Tree Structures

A linear time algorithm for L(2,1)-labeling of trees

See the researcher in context

Building this map preview

Hirotaka Ono

Research overview

Is this your work?

10 publications

Parameterized Complexity of (A,ℓ)(A,\ell)(A,ℓ)-Path Packing

Coalescing random walks and voting on connected graphs

Fixed-Parameter Tractability of Token Jumping on Planar Graphs

Subgraph Domatic Problem and Writing Capacity of Memory Devises with Restricted State Transitions

The complexity of dominating set reconfiguration

Linear-Time Algorithm for Sliding Tokens on Trees

Reconfiguration of Cliques in a Graph

(Total) Vector Domination for Graphs with Bounded Branchwidth

Minimum Certificate Dispersal with Tree Structures

A linear time algorithm for L(2,1)-labeling of trees

See the researcher in context

Building this map preview

Parameterized Complexity of $(A,\ell)$ -Path Packing