Computing maximum independent set on outerstring graphs and their relatives

Abstract A graph G with n vertices is called an outerstring graph if it has an intersection representation with a set of n curves inside a disk such that one endpoint of every curve is attached to the boundary of the disk. Given an outerstring graph representation of G with s segments, a Maximum Independent Set ( MIS ) of G can be computed in O ( s 3 ) time (Keil et al. (2017) [22] ). We examine the fine-grained complexity of the MIS problem on some well-known outerstring representations (e.g., line segments, L -shapes, etc.), where the strings are of constant size. We show that computing MIS on grounded segment and grounded square- L representations is at least as hard as computing MIS on circle graph representations. Note that no O ( n 2 − δ ) -time algorithm, δ > 0 , is known for computing MIS on circle graphs. For the grounded string representations, where the strings are y-monotone simple polygonal paths of constant length with segments at integral coordinates, we solve MIS in O ( n 2 ) time and show this to be the best possible under the Strong Exponential Time Hypothesis. For the intersection graph of n L -shapes in the plane, we give a ( 4 ⋅ log ⁡ OPT ) -approximation algorithm for MIS (where OPT denotes the size of an optimal solution), improving the previously best-known ( 4 ⋅ log ⁡ n ) -approximation algorithm of Biedl and Derka (WADS 2017).