Yoshio Okamoto

SoCS Conference 2024 Conference Paper

CoRe Challenge 2022/2023: Empirical Evaluations for Independent Set Reconfiguration Problems (Extended Abstract)

• Takehide Soh
• Tomoya Tanjo
• Yoshio Okamoto
• Takehiro Ito

In this extended abstract, we describe CoRe Challenge 2022/2023, an international competition series aiming to construct the technical foundation of practical research for Combinatorial Reconfiguration. This competition series targets one of the most well-studied reconfiguration problems, called the independent set reconfiguration problem under the token jumping model, which asks a step-by-step transformation between two given independent sets in a graph. Theoretically, the problem is PSPACE-complete, which implies that there exist instances such that even a shortest transformation requires super-polynomial steps with respect to the input size under the assumption of $NP \neq PSPACE$. The competition series consists of four tracks: three tracks take two independent sets of a graph as input, and ask the existence of a transformation, a shortest transformation, a longest transformation between them; and the last track takes only a number of vertices as input, and asks for an instance of the specified number of vertices that needs a longer shortest transformation steps. We describe the background of the competition series and highlight the results of the solver and graph tracks.

TCS Journal 2023 Journal Article

Graphs with large total angular resolution

• Oswin Aichholzer
• Matias Korman
• Yoshio Okamoto
• Irene Parada
• Daniel Perz
• André van Renssen
• Birgit Vogtenhuber

The total angular resolution of a straight-line drawing is the minimum angle between two edges of the drawing. It combines two properties contributing to the readability of a drawing: the angular resolution, which is the minimum angle between incident edges, and the crossing resolution, which is the minimum angle between crossing edges. We consider the total angular resolution of a graph, which is the maximum total angular resolution of a straight-line drawing of this graph. We prove tight bounds for the number of edges for graphs for some values of the total angular resolution up to a finite number of well specified exceptions of constant size. In addition, we show that deciding whether a graph has total angular resolution at least 60 ∘ is NP-hard. Further we present some special graphs and their total angular resolution.

TCS Journal 2023 Journal Article

On reachable assignments under dichotomous preferences

• Takehiro Ito
• Naonori Kakimura
• Naoyuki Kamiyama
• Yusuke Kobayashi
• Yuta Nozaki
• Yoshio Okamoto
• Kenta Ozeki

We consider the problem of determining whether a target item assignment can be reached from an initial item assignment by a sequence of pairwise exchanges of items between agents. In particular, we consider the situation where each agent has a dichotomous preference over the items, that is, each agent evaluates each item as acceptable or unacceptable. Furthermore, we assume that communication between agents is limited, and the relationship is represented by an undirected graph. Then, a pair of agents can exchange their items only if they are connected by an edge and the involved items are acceptable. We prove that this problem is PSPACE -complete even when the communication graph is complete (that is, every pair of agents can exchange their items), and this problem can be solved in polynomial time if an input graph is a tree.

SODA Conference 2022 Conference Paper

Monotone edge flips to an orientation of maximum edge-connectivity à la Nash-Williams

• Takehiro Ito
• Yuni Iwamasa
• Naonori Kakimura
• Naoyuki Kamiyama
• Yusuke Kobayashi 0001
• Shun-ichi Maezawa
• Yuta Nozaki
• Yoshio Okamoto

We initiate the study of k -edge-connected orientations of undirected graphs through edge flips for k ≥ 2. We prove that in every orientation of an undirected 2 k -edge-connected graph, there exists a sequence of edges such that flipping their directions one by one does not decrease the edge-connectivity, and the final orientation is k -edge-connected. This yields an “edge-flip based” new proof of Nash-Williams' theorem: an undirected graph G has a k -edge-connected orientation if and only if G is 2 k -edge-connected. As another consequence of the theorem, we prove that the edge-flip graph of k -edge-connected orientations of an undirected graph G is connected if G is (2 k + 2)-edge-connected. This has been known to be true only when k = 1.

AAAI Conference 2022 Conference Paper

Reforming an Envy-Free Matching

• Takehiro Ito
• Yuni Iwamasa
• Naonori Kakimura
• Naoyuki Kamiyama
• Yusuke Kobayashi
• Yuta Nozaki
• Yoshio Okamoto
• Kenta Ozeki

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.

TCS Journal 2021 Journal Article

Algorithms for gerrymandering over graphs

• Takehiro Ito
• Naoyuki Kamiyama
• Yusuke Kobayashi
• Yoshio Okamoto

We initiate the systematic algorithmic study for gerrymandering over graphs that was recently introduced by Cohen-Zemach, Lewenberg and Rosenschein. Namely, we study a strategic procedure for a political districting designer to draw electoral district boundaries so that a particular target candidate can win in an election. We focus on the existence of such a strategy under the plurality voting rule, and give interesting contrasts which classify easy and hard instances with respect to polynomial-time solvability. For example, we prove that the problem for trees is strongly NP-complete (thus unlikely to have a pseudo-polynomial-time algorithm), but has a pseudo-polynomial-time algorithm when the number of candidates is constant. Another example is to prove that the problem for complete graphs is NP-complete when the number of electoral districts is two, while is solvable in polynomial time when it is more than two.

AAMAS Conference 2019 Conference Paper

Algorithms for Gerrymandering over Graphs

• Takehiro Ito
• Naoyuki Kamiyama
• Yusuke Kobayashi
• Yoshio Okamoto

We initiate the systematic algorithmic study for gerrymandering over graphs that was recently introduced by Cohen-Zemach, Lewenberg and Rosenschein. Namely, we study a strategic procedure for a political districting designer to draw electoral district boundaries so that a particular target candidate can win in an election. We focus on the existence of such a strategy under the plurality voting rule, and give interesting contrasts which classify easy and hard instances with respect to polynomial-time solvability. For example, we prove that the problem for trees is strongly NP-complete (thus unlikely to have a pseudo-polynomial-time algorithm), but has a pseudo-polynomial-time algorithm when the number of candidates is constant. Another example is to prove that the problem for complete graphs is NP-complete when the number of electoral districts is two, while is solvable in polynomial time when it is more than two.

TCS Journal 2017 Journal Article

Efficient stabilization of cooperative matching games

• Takehiro Ito
• Naonori Kakimura
• Naoyuki Kamiyama
• Yusuke Kobayashi
• Yoshio Okamoto

Cooperative matching games have drawn much interest partly because of the connection with bargaining solutions in the networking environment. However, it is not always guaranteed that a network under investigation gives rise to a stable bargaining outcome. To address this issue, we consider a modification process, called stabilization, that yields a network with stable outcomes, where the modification should be as small as possible. Therefore, the problem is cast to a combinatorial-optimization problem in a graph. Recently, the stabilization by edge removal was shown to be NP-hard. On the contrary, in this paper, we show that other possible ways of stabilization, namely, edge addition, vertex removal and vertex addition, are all polynomial-time solvable. Thus, we obtain a complete complexity-theoretic classification of the natural four variants of the network stabilization problem. We further study weighted variants and prove that the variants for edge addition and vertex removal are NP-hard.

AAMAS Conference 2016 Conference Paper

Efficient Stabilization of Cooperative Matching Games

• Takehiro Ito
• Naonori Kakimura
• Naoyuki Kamiyama
• Yusuke Kobayashi
• Yoshio Okamoto

TCS Journal 2015 Journal Article

Swapping labeled tokens on graphs

• Katsuhisa Yamanaka
• Erik D. Demaine
• Takehiro Ito
• Jun Kawahara
• Masashi Kiyomi
• Yoshio Okamoto
• Toshiki Saitoh
• Akira Suzuki

Consider a puzzle consisting of n tokens on an n-vertex graph, where each token has a distinct starting vertex and a distinct target vertex it wants to reach, and the only allowed transformation is to swap the tokens on adjacent vertices. We prove that every such puzzle is solvable in O ( n 2 ) token swaps, and thus focus on the problem of minimizing the number of token swaps to reach the target token placement. We give a polynomial-time 2-approximation algorithm for trees, and using this, obtain a polynomial-time 2α-approximation algorithm for graphs whose tree α-spanners can be computed in polynomial time. Finally, we show that the problem can be solved exactly in polynomial time on complete bipartite graphs.

TCS Journal 2014 Journal Article

A 4.31-approximation for the geometric unique coverage problem on unit disks

• Takehiro Ito
• Shin-ichi Nakano
• Yoshio Okamoto
• Yota Otachi
• Ryuhei Uehara
• Takeaki Uno
• Yushi Uno

We give an improved approximation algorithm for the unique unit-disk coverage problem: Given a set of points and a set of unit disks, both in the plane, we wish to find a subset of disks that maximizes the number of points contained in exactly one disk in the subset. Erlebach and van Leeuwen (2008) introduced this problem as the geometric version of the unique coverage problem, and gave a polynomial-time 18-approximation algorithm. In this paper, we improve this approximation ratio 18 to 2 + 4 / 3 + ε ( < 4. 3095 + ε ) for any fixed constant ε > 0. Our algorithm runs in polynomial time which depends exponentially on 1 / ε. The algorithm can be generalized to the budgeted unique unit-disk coverage problem in which each point has a profit, each disk has a cost, and we wish to maximize the total profit of the uniquely covered points under the condition that the total cost is at most a given bound.

TCS Journal 2013 Journal Article

The complexity of the stamp folding problem

• Takuya Umesato
• Toshiki Saitoh
• Ryuhei Uehara
• Hiro Ito
• Yoshio Okamoto

There are many folded states consistent with a given mountain–valley pattern of equidistant creases on a long paper strip. We would like to fold a paper strip such that the number of paper layers between each pair of hinged paper segments, called the crease width at the crease point, is minimized. This problem is called the stamp folding problem and there are two variants of this problem: minimization of the maximum crease width, and minimization of the total crease width. This optimization problem was recently introduced and investigated from the viewpoint of the counting problem. However, its computational complexity is not known. In this paper, we first show that the minimization problem of the maximum crease width is strongly NP-complete. Hence we cannot solve the problem in polynomial time unless P=NP. We next propose an algorithm that solves the minimization problem. The algorithm itself is a straightforward one, but its analysis is not trivial. We show that this algorithm runs in O ( ( k + 1 ) k n ) time where n is the number of creases and k is the total crease width.

TCS Journal 2010 Journal Article

On listing, sampling, and counting the chordal graphs with edge constraints

• Shuji Kijima
• Masashi Kiyomi
• Yoshio Okamoto
• Takeaki Uno

We discuss the problems to list, sample, and count the chordal graphs with edge constraints. The objects we look at are chordal graphs sandwiched by a given pair of graphs where we assume that at least one of the input graphs is chordal. The setting is a natural generalization of chordal completions and deletions. For the listing problem, we give an efficient algorithm running in polynomial time per output with polynomial space. As for the sampling problem, we give two clues that indicate that a random sampling is not easy. The first clue is that we show #P-completeness results for counting problems. The second clue is that we give an instance for which a natural Markov chain suffers from an exponential mixing time. These results provide a unified viewpoint from algorithms’ theory to problems arising from various areas such as statistics, data mining, and numerical computation.