Fine-grained complexity of coloring disks, balls, and segments.

Speaker(s)

Paweł Rzążewski

Affiliation

Politechnika Warszawska

Date

March 23, 2017, 12:15 p.m.

Room

room 5870

Seminar

Seminar Algorithms

---

On planar graphs, many classic algorithmic problems enjoy a certain ``square root phenomenon'' and can be solved significantly faster than what is known to be possible on general graphs: for example, Independent Set, 3-Coloring, Hamiltonian Cycle, Dominating Set can be solved in time 2^{O(sqrt{n})} on an n-vertex planar graph, while no 2^{o(n)} algorithms exist for general graphs, assuming the Exponential Time Hypothesis (ETH).  The square root in the exponent seems to be best possible for planar graphs: assuming the ETH, the running time for these problems cannot be improved to 2^{o(sqrt{n})}.  In some cases, a similar speedup can be obtained for 2-dimensional geometric problems, for example, there are 2^{O(sqrt{n} log n)} time algorithms for Independent Set on unit disk graphs or for TSP on 2-dimensional point sets.

In this talk, we explore whether such a speedup is possible for geometric coloring problems. On the one hand, geometric objects can behave similarly to planar graphs:  3-Coloring can be solved in time 2^{O(sqrt{n})} on the intersection graph of n disks in the plane and, assuming the ETH, there is no such algorithm with running time 2^{o(sqrt{n})}. On the other hand, if the number k of colors is part of the input, then no such speedup is possible: Coloring the intersection graph of n unit disks with k colors cannot be solved in time 2^{o(n)}, assuming the ETH. More precisely, we exhibit a smooth increase of complexity as the number k of colors increases: the problem of coloring the intersection graph of n unit disks with k colors
(i)  can be solved in time exp ( O(sqrt{nk} log n) ), and
(ii) cannot be solved in time exp ( o(sqrt{nk}) ), unless the ETH fails.

More generally, we consider the problem of coloring d-dimensional balls in the Euclidean space and obtain analogous results showing that the problem
(i) can be solved in time exp ( O(n^{1-1/d} k^{1/d} log n)), and
\item cannot be solved in time exp (O(n^{1-1/d-epsilon} k^{1/d})) for any epsilon>0, unless the ETH fails.

Finally, we prove that fatness is crucial to obtain subexponential algorithms for coloring.
We show that an existence of an algorithm for 4-Coloring an intersection graph of segments in time 2^{o(n)}, using a constant number of colors, already refutes the ETH. On the other hand, 3-Coloring can be solved in time 2^{O(n^{2/3} log n} in the class of string graphs.

The results are obtained as joint work with Csaba Biro, Edouard Bonnet, Daniel Marx, Tillmann Miltzow, and Stephan Thomasse.

---