Author name cluster

Kenji Obata

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers

1 author row

STOC Conference 2004 Conference Paper

Approximate max-integral-flow/min-multicut theorems

Kenji Obata

We establish several approximate max- integral -flow / min-multicut theorems. While in general this ratio can be very large, we prove strong approximation ratios in the case where the min-multicut is a constant fraction ε of the total capacity of the graph. This setting is motivated by several combinatorial and algorithmic applications. Prior to this work, a general max-integral-flow / min-multicut bound was known only for the special case where the graph is a tree. We prove that, for arbitrary graphs, the max-integral-flow / min-multicut ratio is O (ε -1 log k ), where k is the number of commodites; for graphs excluding a fixed subgraph as a minor (for instance, planar graphs), O (1 / ε); and, for dense graphs, O (1√ε). Our proofs are constructive in the sense that we give efficient algorithms which compute either an integral flow achieving the claimed approximation ratios, or a witness that the precondition is violated.

Details

FOCS Conference 2002 Conference Paper

A Lower Bound for Testing 3-Colorability in Bounded-Degree Graphs

Andrej Bogdanov
Kenji Obata
Luca Trevisan 0001

We consider the problem of testing 3-colorability in the bounded-degree model. We show that, for small enough /spl epsiv/, every tester for 3-colorability must have query complexity /spl Omega/(n). This is the first linear lower bound for testing a natural graph property in the bounded-degree model. An /spl Omega/(/spl radic/n) lower bound was previously known. For one-sided error testers, we also show an /spl Omega/(n) lower bound for testers that distinguish 3-colorable graphs from graphs that are (1/3 - /spl alpha/)-far from 3-colorable, for arbitrarily small /spl alpha/. In contrast, a polynomial time algorithm by Frieze and Jerrum (1997) distinguishes 3-colorable graphs from graphs that are 1/5-far from 3-colorable. As a by-product of our techniques, we obtain tight unconditional lower bounds on the approximation ratios achievable by sublinear time algorithms for Max E3SAT, Max E3LIN-2 and other problems.

Details