Kenta Ozeki

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.

SODA Conference 2013 Conference Paper

4-connected projective-planar graphs are hamiltonian-connected

• Ken-ichi Kawarabayashi
• Kenta Ozeki

SODA Conference 2012 Conference Paper

Spanning closed walks and TSP in 3-connected planar graphs

• Ken-ichi Kawarabayashi
• Kenta Ozeki

TCS Journal 2010 Journal Article

A simple algorithm for 4-coloring 3-colorable planar graphs

• Ken-ichi Kawarabayashi
• Kenta Ozeki

Graph coloring for 3-colorable graphs receives very much attention by many researchers in theoretical computer science. Deciding 3-colorability of a graph is a well-known NP-complete problem. So far, the best known polynomial approximation algorithm achieves a factor of O ( n 0. 2072 ), and there is a strong evidence that there would be no polynomial time algorithm to color 3-colorable graphs using at most c colors for an absolute constant c. In this paper, we consider 3-colorable PLANAR graphs. The Four Color Theorem (4CT) (Appel and Haken (1977) [1], Appel et al. (1977) [2], Robertson et al. (1997) [14]) gives an O ( n 2 ) time algorithm to 4-color any planar graph. However the current known proof for the 4CT is computer assisted. In addition, the correctness of the proof is still lengthy and complicated. We give a very simple O ( n 2 ) algorithm to 4-color 3-colorable planar graphs. The correctness needs only a 2-page proof.