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

Akira Suzuki

Akira Suzuki appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Data Structures and AlgorithmsDiscrete MathematicsComputational Complexitycond-mat.mes-hallcond-mat.stat-mechmath.COComputer Science and Game Theorycond-mat.mtrl-scicond-mat.othercond-mat.quant-gascond-mat.supr-conquant-phSocial and Information Networks

Catalog footprint

What is connected

16works
13topics
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

16 published item(s)

preprint2026arXiv

Computational Complexity of Swish

Swish is a card game in which players are given cards having symbols (hoops and balls), and find a valid superposition of cards, called a "swish." Dailly, Lafourcade, and Marcadet (FUN 2024) studied a generalized version of Swish and showed that the problem is solvable in polynomial time with one symbol per card, while it is NP-complete with three or more symbols per card. In this paper, we resolve the previously open case of two symbols per card, which corresponds to the original game. We show that Swish is NP-complete for this case. Specifically, we prove the NP-hardness when the allowed transformations of cards are restricted to a single (horizontal or vertical) flip or 180-degree rotation, and extend the results to the original setting allowing all three transformations. In contrast, when neither transformation is allowed, we present a polynomial-time algorithm. Combining known and our results, we establish a complete characterization of the computational complexity of Swish with respect to both the number of symbols per card and the allowed transformations.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Reconfiguration of Spanning Trees with Degree Constraint or Diameter Constraint

We investigate the complexity of finding a transformation from a given spanning tree in a graph to another given spanning tree in the same graph via a sequence of edge flips. The exchange property of the matroid bases immediately yields that such a transformation always exists if we have no constraints on spanning trees. In this paper, we wish to find a transformation which passes through only spanning trees satisfying some constraint. Our focus is bounding either the maximum degree or the diameter of spanning trees, and we give the following results. The problem with a lower bound on maximum degree is solvable in polynomial time, while the problem with an upper bound on maximum degree is PSPACE-complete. The problem with a lower bound on diameter is NP-hard, while the problem with an upper bound on diameter is solvable in polynomial time.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Reconfiguring k-path vertex covers

A vertex subset $I$ of a graph $G$ is called a $k$-path vertex cover if every path on $k$ vertices in $G$ contains at least one vertex from $I$. The \textsc{$k$-Path Vertex Cover Reconfiguration ($k$-PVCR)} problem asks if one can transform one $k$-path vertex cover into another via a sequence of $k$-path vertex covers where each intermediate member is obtained from its predecessor by applying a given reconfiguration rule exactly once. We investigate the computational complexity of \textsc{$k$-PVCR} from the viewpoint of graph classes under the well-known reconfiguration rules: $\mathsf{TS}$, $\mathsf{TJ}$, and $\mathsf{TAR}$. The problem for $k=2$, known as the \textsc{Vertex Cover Reconfiguration (VCR)} problem, has been well-studied in the literature. We show that certain known hardness results for \textsc{VCR} on different graph classes including planar graphs, bounded bandwidth graphs, chordal graphs, and bipartite graphs, can be extended for \textsc{$k$-PVCR}. In particular, we prove a complexity dichotomy for \textsc{$k$-PVCR} on general graphs: on those whose maximum degree is $3$ (and even planar), the problem is $\mathtt{PSPACE}$-complete, while on those whose maximum degree is $2$ (i.e., paths and cycles), the problem can be solved in polynomial time. Additionally, we also design polynomial-time algorithms for \textsc{$k$-PVCR} on trees under each of $\mathsf{TJ}$ and $\mathsf{TAR}$. Moreover, on paths, cycles, and trees, we describe how one can construct a reconfiguration sequence between two given $k$-path vertex covers in a yes-instance. In particular, on paths, our constructed reconfiguration sequence is shortest.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Decremental Optimization of Dominating Sets Under the Reconfiguration Framework

Given a dominating set, how much smaller a dominating set can we find through elementary operations? Here, we proceed by iterative vertex addition and removal while maintaining the property that the set forms a dominating set of bounded size. This can be seen as the optimization variant of the dominating set reconfiguration problem, where two dominating sets are given and the question is merely whether they can be reached one from another through elementary operations. We show that this problem is PSPACE-complete, even if the input graph is a bipartite graph, a split graph, or has bounded pathwidth. On the positive side, we give linear-time algorithms for cographs, trees and interval graphs. We also study the parameterized complexity of this problem. More precisely, we show that the problem is W[2]-hard when parameterized by the upper bound on the size of an intermediary dominating set. On the other hand, we give fixed-parameter algorithms with respect to the minimum size of a vertex cover, or $d+s$ where $d$ is the degeneracy and $s$ is the upper bound of output solution.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Reconfiguration of Spanning Trees with Many or Few Leaves

Let $G$ be a graph and $T_1,T_2$ be two spanning trees of $G$. We say that $T_1$ can be transformed into $T_2$ via an edge flip if there exist two edges $e \in T_1$ and $f$ in $T_2$ such that $T_2= (T_1 \setminus e) \cup f$. Since spanning trees form a matroid, one can indeed transform a spanning tree into any other via a sequence of edge flips, as observed by Ito et al. We investigate the problem of determining, given two spanning trees $T_1,T_2$ with an additional property $Π$, if there exists an edge flip transformation from $T_1$ to $T_2$ keeping property $Π$ all along. First we show that determining if there exists a transformation from $T_1$ to $T_2$ such that all the trees of the sequence have at most $k$ (for any fixed $k \ge 3$) leaves is PSPACE-complete. We then prove that determining if there exists a transformation from $T_1$ to $T_2$ such that all the trees of the sequence have at least $k$ leaves (where $k$ is part of the input) is PSPACE-complete even restricted to split, bipartite or planar graphs. We complete this result by showing that the problem becomes polynomial for cographs, interval graphs and when $k=n-2$.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

The Complexity of (List) Edge-Coloring Reconfiguration Problem

Let $G$ be a graph such that each edge has its list of available colors, and assume that each list is a subset of the common set consisting of $k$ colors. Suppose that we are given two list edge-colorings $f_0$ and $f_r$ of $G$, and asked whether there exists a sequence of list edge-colorings of $G$ between $f_0$ and $f_r$ such that each list edge-coloring can be obtained from the previous one by changing a color assignment of exactly one edge. This problem is known to be PSPACE-complete for every integer $k \ge 6$ and planar graphs of maximum degree three, but any complexity hardness was unknown for the non-list variant. In this paper, we first improve the known result by proving that, for every integer $k \ge 4$, the problem remains PSPACE-complete even if an input graph is planar, bounded bandwidth, and of maximum degree three. We then give the first complexity hardness result for the non-list variant: for every integer $k \ge 5$, we prove that the non-list variant is PSPACE-complete even if an input graph is planar, of bandwidth linear in $k$, and of maximum degree $k$.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Theory of the Room-Temperature QHE in Graphene

The unusual quantum Hall effect (QHE) in graphene is often discussed in terms of Dirac fermions moving with a linear dispersion relation. The same phenomenon will be explained in terms of the more traditional composite bosons, which move with a linear dispersion relation. The "electron" (wave packet) moves easier in the direction [1,1,0,c-axis] = [1,1,0] of the honeycomb lattice than perpendicular to it, while the "hole" moves easier in [0,0,1]. Since "electrons" and "holes" move in different channels, the number densities can be high especially when the Fermi surface has "necks". The strong QHE arises from the phonon exchange attraction in the neighborhood of the "neck" Fermi surfaces. The plateau observed for the Hall conductivity and the accompanied resistivity drop is due to the Bose-Einstein condensation of the c-bosons, each forming from a pair of one-electron--two-fluxons c-fermions by phonon-exchange attraction.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Identities for Entropy Change Associated with the Time-Evolution of an Open System

A general relation between entropy and an evolutionary superoperator is derived based on the theory of the real-time formulation. The formulation establishing the relation relies only on the framework of quantum statistical mechanics and the standard definition of the von Neumann entropy. Applying the theory of the imaginary-time formulation, a similar relation is obtained for the entropy change due to the change in reservoir temperatures. To show the usefulness of these formulas, we derived the expression for the entropy production induced by some dissipation in an open quantum system as the exemplary model system.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Computational Complexity of Competitive Diffusion on (Un)weighted Graphs

Consider an undirected graph modeling a social network, where the vertices represent users, and the edges do connections among them. In the competitive diffusion game, each of a number of players chooses a vertex as a seed to propagate his/her opinion, and then it spreads along the edges in the graphs. The objective of every player is to maximize the number of vertices the opinion infects. In this paper, we investigate a computational problem of asking whether a pure Nash equilibrium exists in the competitive diffusion game on unweighed and weighted graphs, and present several negative and positive results. We first prove that the problem is W[1]-hard when parameterized by the number of players even for unweighted graphs. We also show that the problem is NP-hard even for series-parallel graphs with positive integer weights, and is NP-hard even for forests with arbitrary integer weights. Furthermore, we show that the problem for forest of paths with arbitrary weights is solvable in pseudo-polynomial time; and it is solvable in quadratic time if a given graph is unweighted. We also prove that the problem for chain, cochain, and threshold graphs with arbitrary integer weights is solvable in polynomial time.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Reconfiguration of Dominating Sets

We explore a reconfiguration version of the dominating set problem, where a dominating set in a graph $G$ is a set $S$ of vertices such that each vertex is either in $S$ or has a neighbour in $S$. In a reconfiguration problem, the goal is to determine whether there exists a sequence of feasible solutions connecting given feasible solutions $s$ and $t$ such that each pair of consecutive solutions is adjacent according to a specified adjacency relation. Two dominating sets are adjacent if one can be formed from the other by the addition or deletion of a single vertex. For various values of $k$, we consider properties of $D_k(G)$, the graph consisting of a vertex for each dominating set of size at most $k$ and edges specified by the adjacency relation. Addressing an open question posed by Haas and Seyffarth, we demonstrate that $D_{Γ(G)+1}(G)$ is not necessarily connected, for $Γ(G)$ the maximum cardinality of a minimal dominating set in $G$. The result holds even when graphs are constrained to be planar, of bounded tree-width, or $b$-partite for $b \ge 3$. Moreover, we construct an infinite family of graphs such that $D_{γ(G)+1}(G)$ has exponential diameter, for $γ(G)$ the minimum size of a dominating set. On the positive side, we show that $D_{n-m}(G)$ is connected and of linear diameter for any graph $G$ on $n$ vertices having at least $m+1$ independent edges.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Composite-particles (Boson, Fermion) Theory of Fractional Quantum Hall Effect

A quantum statistical theory is developed for a fractional quantum Hall effects in terms of composite bosons (fermions) each of which contains a conduction electron and an odd (even) number of fluxons. The cause of the QHE is by assumption the phonon exchange attraction between the conduction electron ("electron", "hole") and fluxons (quanta of magnetic fluxes). We postulate that c-fermions with \emph{any} even number of fluxons have an effective charge (magnitude) equal to the electron charge $e$. The density of c-fermions with $m$ fluxons, $n_ϕ^{(m)}$, is connected with the electron density $n_{\mathrm e}$ by $n_ϕ^{(m)}=n_{\mathrm e}/m$, which implies a more difficult formation for higher $m$, generating correct values $me^2/h$ for the Hall conductivity $σ_{\mathrm H}\equiv j/E_{\mathrm H}$. For condensed c-bosons the density of c-bosons-with-$m$ fluxons, $n_ϕ^{(m)}$, is connected with the boson density $n_0$ by $n_ϕ^{(m)}=n_0/m$. This yields $σ_{\mathrm H}=m\,e^2/h$ for the magnetoconductivity, the value observed of the QHE at filling factor $ν=1/m$ ($m=$odd numbers). Laughlin's theory and results about the fractional charge are not borrowed in the present work.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

On the Parameterized Complexity of Reconfiguration Problems

We present the first results on the parameterized complexity of reconfiguration problems, where a reconfiguration version of an optimization problem $Q$ takes as input two feasible solutions $S$ and $T$ and determines if there is a sequence of {\em reconfiguration steps} that can be applied to transform $S$ into $T$ such that each step results in a feasible solution to $Q$. For most of the results in this paper, $S$ and $T$ are subsets of vertices of a given graph and a reconfiguration step adds or deletes a vertex. Our study is motivated by recent results establishing that for most NP-hard problems, the classical complexity of reconfiguration is PSPACE-complete. We address the question for several important graph properties under two natural parameterizations: $k$, the size of the solutions, and $\ell$, the length of the sequence of steps. Our first general result is an algorithmic paradigm, the {\em reconfiguration kernel}, used to obtain fixed-parameter algorithms for the reconfiguration versions of {\sc Vertex Cover} and, more generally, {\sc Bounded Hitting Set} and {\sc Feedback Vertex Set}, all parameterized by $k$. In contrast, we show that reconfiguring {\sc Unbounded Hitting Set} is $W[2]$-hard when parameterized by $k+\ell$. We also demonstrate the $W[1]$-hardness of the reconfiguration versions of a large class of maximization problems parameterized by $k+\ell$, and of their corresponding deletion problems parameterized by $\ell$; in doing so, we show that there exist problems in FPT when parameterized by $k$, but whose reconfiguration versions are $W[1]$-hard when parameterized by $k+\ell$.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Statistical mechanical expression of entropy production for an open quantum system

A quantum statistical expression for the entropy of a nonequilibrium system is defined so as to be consistent with Gibbs' relation, and is shown to corresponds to dynamical variable by introducing analogous to the Heisenberg picture in quantum mechanics. The general relation between system-reservoir interactions and an entropy change operator in an open quantum system, relying just on the framework of statistical mechanics and the definition of von Neumann entropy. By using this formula, we can obtain the correct entropy production in the linear response framework. The present derivation of entropy production is directly based on the first principle of microscopic time-evolution, while the previous standard argument is due to the thermodynamic energy balance.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

On the metal-insulator-transition in vanadium dioxide

Vanadium dioxide (VO$_2$) undergoes a metal-insulator transition (MIT) at 340 K with the structural change between tetragonal and monoclinic crystals as the temperature is lowered. The conductivity $σ$ drops at MIT by four orders of magnitude. The low-temperature monoclinic phase is known to have a lower ground-state energy. The existence of a $k$-vector ${\boldsymbol k}$ is prerequisite for the conduction since the ${\boldsymbol k}$ appears in the semiclassical equation of motion for the conduction electron (wave packet). Each wave packet is, by assumption, composed of the plane waves proceeding in the ${\boldsymbol k}$ direction perpendicular to the plane. The tetragonal (VO$_2$)$_3$ unit cells are periodic along the crystal's $x$-, $y$-, and z-axes, and hence there are three-dimensional $k$-vectors. The periodicity using the non-orthogonal bases does not legitimize the electron dynamics in solids. There are one-dimensional ${\boldsymbol k}$ along the c-axis for a monoclinic crystal. We believe this decrease in the dimensionality of the $k$-vectors is the cause of the conductivity drop. Triclinic and trigonal (rhombohedral) crystals have no $k$-vectors, and hence they must be insulators. The majority carriers in graphite are "electrons", which is shown by using an orthogonal unit cell for the hexagonal lattice.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

The two-atom energy spectrum in a harmonic trap near a Feshbach resonance at higher partial waves

Two atoms in an optical lattice may be made to interact strongly at higher partial waves near a Feshbach resonance. These atoms, under appropriate constraints, could be bosonic or fermionic. The universal $l=2$ energy spectrum for such a system, with a caveat, is presented in this paper, and checked with the spectrum obtained by direct numerical integration of the Schrödinger equation. The results reported here extend those of Yip for p-wave resonance (Phys. Rev. A {\bf 78}, 013612 (2008)), while exploring the limitations of a universal expression for the spectrum for the higher partial waves.

0 citations0 reviewsNo code linkedOpen access