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

Yuni Iwamasa

Yuni Iwamasa 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 IntelligenceComputational ComplexityComputer Science and Game Theorycond-mat.dis-nnecon.THmath.OCphysics.soc-phSocial and Information Networks

Catalog footprint

What is connected

6works
11topics
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

6 published item(s)

preprint2022arXiv

Independent set reconfiguration on directed graphs

\textsc{Directed Token Sliding} asks, given a directed graph and two sets of pairwise nonadjacent vertices, whether one can reach from one set to the other by repeatedly applying a local operation that exchanges a vertex in the current set with one of its out-neighbors, while keeping the nonadjacency. It can be seen as a reconfiguration process where a token is placed on each vertex in the current set, and the local operation slides a token along an arc respecting its direction. Previously, such a problem was extensively studied on undirected graphs, where the edges have no directions and thus the local operation is symmetric. \textsc{Directed Token Sliding} is a generalization of its undirected variant since an undirected edge can be simulated by two arcs of opposite directions. In this paper, we initiate the algorithmic study of \textsc{Directed Token Sliding}. We first observe that the problem is PSPACE-complete even if we forbid parallel arcs in opposite directions and that the problem on directed acyclic graphs is NP-complete and W[1]-hard parameterized by the size of the sets in consideration. We then show our main result: a linear-time algorithm for the problem on directed graphs whose underlying undirected graphs are trees, which are called polytrees. Such a result is also known for the undirected variant of the problem on trees~[Demaine et al.~TCS 2015], but the techniques used here are quite different because of the asymmetric nature of the directed problem. We present a characterization of yes-instances based on the existence of a certain set of directed paths, and then derive simple equivalent conditions from it by some observations, which admits an efficient algorithm. For the polytree case, we also present a quadratic-time algorithm that outputs, if the input is a yes-instance, one of the shortest reconfiguration sequences.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Reconstructing phylogenetic trees from multipartite quartet systems

A phylogenetic tree is a graphical representation of an evolutionary history of taxa in which the leaves correspond to the taxa and the non-leaves correspond to speciations. One of important problems in phylogenetic analysis is to assemble a global phylogenetic tree from small phylogenetic trees, particularly, quartet trees. {\sc Quartet Compatibility} is the problem of deciding whether there is a phylogenetic tree inducing a given collection of quartet trees, and to construct such a phylogenetic tree if it exists. It is known that {\sc Quartet Compatibility} is NP-hard and that there are only a few results known for polynomial-time solvable subclasses. In this paper, we introduce two novel classes of quartet systems, called complete multipartite quartet system and full multipartite quartet system, and present polynomial-time algorithms for {\sc Quartet Compatibility} for these systems.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Reforming an Envy-Free Matching

We consider the problem of reforming an envy-free matching when each agent is assigned a single item. Given an envy-free matching, we consider an operation to exchange the item of an agent with an unassigned item preferred by the agent that results in another envy-free matching. We repeat this operation as long as we can. We prove that the resulting envy-free matching is uniquely determined up to the choice of an initial envy-free matching, and can be found in polynomial time. We call the resulting matching a reformist envy-free matching, and then we study a shortest sequence to obtain the reformist envy-free matching from an initial envy-free matching. We prove that a shortest sequence is computationally hard to obtain even when each agent accepts at most four items and each item is accepted by at most three agents. On the other hand, we give polynomial-time algorithms when each agent accepts at most three items or each item is accepted by at most two agents. Inapproximability and fixed-parameter (in)tractability are also discussed.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Optimal matroid bases with intersection constraints: Valuated matroids, M-convex functions, and their applications

For two matroids $M_1$ and $M_2$ with the same ground set $V$ and two cost functions $w_1$ and $w_2$ on $2^V$, we consider the problem of finding bases $X_1$ of $M_1$ and $X_2$ of $M_2$ minimizing $w_1(X_1)+w_2(X_2)$ subject to a certain cardinality constraint on their intersection $X_1 \cap X_2$. For this problem, Lendl, Peis, and Timmermans (2019) discussed modular cost functions: they reduced the problem to weighted matroid intersection for the case where the cardinality constraint is $|X_1 \cap X_2|\le k$ or $|X_1 \cap X_2|\ge k$; and designed a new primal-dual algorithm for the case where the constraint is $|X_1 \cap X_2|=k$. The aim of this paper is to generalize the problems to have nonlinear convex cost functions, and to comprehend them from the viewpoint of discrete convex analysis. We prove that each generalized problem can be solved via valuated independent assignment, valuated matroid intersection, or $\mathrm{M}$-convex submodular flow, to offer a comprehensive understanding of weighted matroid intersection with intersection constraints. We also show the NP-hardness of some variants of these problems, which clarifies the coverage of discrete convex analysis for those problems. Finally, we present applications of our generalized problems in the recoverable robust matroid basis problem, combinatorial optimization problems with interaction costs, and matroid congestion games.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

On k-Submodular Relaxation

$k$-submodular functions, introduced by Huber and Kolmogorov, are functions defined on $\{0, 1, 2, \dots, k\}^n$ satisfying certain submodular-type inequalities. $k$-submodular functions typically arise as relaxations of NP-hard problems, and the relaxations by $k$-submodular functions play key roles in design of efficient, approximation, or fixed-parameter tractable algorithms. Motivated by this, we consider the following problem: Given a function $f : \{1, 2, \dots, k\}^n \rightarrow \mathbb{R} \cup \{\infty\}$, determine whether $f$ is extended to a $k$-submodular function $g : \{0, 1, 2, \dots, k\}^n \rightarrow \mathbb{R} \cup \{\infty\}$, where $g$ is called a $k$-submodular relaxation of $f$. We give a polymorphic characterization of those functions which admit a $k$-submodular relaxation, and also give a combinatorial $O((k^n)^2)$-time algorithm to find a $k$-submodular relaxation or establish that a $k$-submodular relaxation does not exist. Our algorithm has interesting properties: (1) If the input function is integer valued, then our algorithm outputs a half-integral relaxation, and (2) if the input function is binary, then our algorithm outputs the unique optimal relaxation. We present applications of our algorithm to valued constraint satisfaction problems.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Networks maximizing the consensus time of voter models

We explore the networks that yield the largest mean consensus time of voter models under different update rules. By analytical and numerical means, we show that the so-called lollipop graph, barbell graph, and double star graph maximise the mean consensus time under the update rules called the link dynamics, voter model, and invasion process, respectively. For each update rule, the largest mean consensus time scales as O(N^3), where N is the number of nodes in the network.

0 citations0 reviewsNo code linkedOpen access