14 citations · 59 across the 21 of their papers we have counts for
7 papers · 1 filter
Tight Inapproximability of Target Set Reconfiguration
Naoto Ohsaka
Given a graph with a vertex threshold function , consider a dynamic process in which any inactive vertex becomes activated whenever at least of its neighbors have…
On the Parameterized Intractability of Determinant Maximization
Naoto Ohsaka
In the Determinant Maximization problem, given an positive semi-definite matrix in and an integer , we are required to find a $k\ti…
Reconfiguration Problems on Submodular Functions
Naoto Ohsaka, Tatsuya Matsuoka
Reconfiguration problems require finding a step-by-step transformation between a pair of feasible solutions for a particular problem. The primary concern in Theoretical Computer Sc…
Some Inapproximability Results of MAP Inference and Exponentiated Determinantal Point Processes
Naoto Ohsaka
We study the computational complexity of two hard problems on determinantal point processes (DPPs). One is maximum a posteriori (MAP) inference, i.e., to find a principal submatrix…
On Reconfigurability of Target Sets
Naoto Ohsaka
We study the problem of deciding reconfigurability of target sets of a graph. Given a graph with vertex thresholds , consider a dynamic process in which vertex becomes a…
A Fully Polynomial Parameterized Algorithm for Counting the Number of Reachable Vertices in a Digraph
Naoto Ohsaka
We consider the problem of counting the number of vertices reachable from each vertex in a digraph , which is equal to computing all the out-degrees of the transitive closure of…
On the Power of Tree-Depth for Fully Polynomial FPT Algorithms
Yoichi Iwata, Tomoaki Ogasawara, Naoto Ohsaka
There are many classical problems in P whose time complexities have not been improved over the past decades. Recent studies of "Hardness in P" have revealed that, for several of su…