Computing maximum independent set on outerstring graphs and their relatives

DOI10.1016/J.COMGEO.2021.101852MaRDI QIDQ5918655zbMATH OpenOpenAlexFDO

Authors Prosenjit Bose, Paz Carmi, J. Mark Keil, Anil Maheshwari, Saeed Mehrabi, Debajyoti Mondal, Michiel Smid

Publication date 8 April 2022

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1903.07024

zbMATH Keywords

maximum independent set problemcircle graphsouterstring graphsfine-grained complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Nonnumerical algorithms (68W05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: A graph $G$ with $n$ vertices is called an outerstring graph if it has an intersection representation of 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, the Maximum Independent Set (MIS) problem of the underlying graph can be computed in $O(s^3)$ time, where $s$ is the number of segments in the representation (Keil et al., Comput. Geom., 60:19--25, 2017). If the strings are of constant size (e.g., line segments, L-shapes, etc.), then the algorithm takes $O(n^3)$ time. In this paper, we examine the fine-grained complexity of the MIS problem on some well-known outerstring representations. We show that solving the MIS problem on grounded segment and grounded square-L representations is at least as hard as solving MIS on circle graph representations. Note that no $O(n^{2-delta})$-time algorithm, $delta>0$, is known for the MIS problem 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 (SETH). For the intersection graph of $n$ L-shapes in the plane, we give a $(4cdotlogOPT)$-approximation algorithm for MIS (where $OPT$ denotes the size of an optimal solution), improving the previously best-known $(4cdotlogn)$-approximation algorithm of Biedl and Derka (WADS 2017).

Recommendations

• Computing maximum independent set on outerstring graphs and their relatives
• An algorithm for the maximum weight independent set problem on outerstring graphs
• The complexity of some problems on maximal independent sets in graphs
• An optimal maximal independent set algorithm for bounded-independence graphs
• scientific article; zbMATH DE number 1305487
• On the number of maximum independent sets of graphs
• Maximum independent set in 2-direction outersegment graphs
• On the maximum independent set problem in graphs of bounded maximum degree
• Computing independent sets in graphs with large girth
• scientific article; zbMATH DE number 637355

Cites work

• scientific article; zbMATH DE number 4200260 (Why is no real title available?)
• scientific article; zbMATH DE number 3513839 (Why is no real title available?)
• scientific article; zbMATH DE number 6850320 (Why is no real title available?)
• Algorithmic graph theory and perfect graphs
• Algorithms and Computation
• Algorithms for a maximum clique and a maximum independent set of a circle graph
• An algorithm for the maximum weight independent set problem on outerstring graphs
• An output sensitive algorithm for computing a maximum independent set of a circle graph
• Approximating dominating set on intersection graphs of rectangles and L-frames
• Approximating domination on intersection graphs of paths on a grid
• Approximation algorithms for maximum independent set of pseudo-disks
• Bend-Bounded Path Intersection Graphs: Sausages, Noodles, and Waffles on a Grill
• Computing maximum independent set on outerstring graphs and their relatives
• Computing the independence number of intersection graphs
• Independent set of intersection graphs of convex objects in 2D
• Intersection graphs of L-shapes and segments in the plane
• Intersection graphs of rays and grounded segments
• Maximum independent set of rectangles
• Maximum independent set on \(B_1\)-VPG graphs
• New clique and independent set algorithms for circle graphs
• On grounded -graphs and their relatives
• Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
• Seidel minor, permutation graphs and combinatorial properties
• Splitting \(B_2\)-VPG graphs into outer-string and co-comparability graphs
• String graphs. I: The number of critical nonstring graphs is infinite
• Vertex Intersection Graphs of Paths on a Grid
• Weakly transitive orientations, Hasse diagrams and string graphs
• Which problems have strongly exponential complexity?

Cited in

(6)

• Maximum independent set in 2-direction outersegment graphs
• Computing independent sets in graphs with large girth
• Finding a Maximum Clique in a Grounded 1-Bend String Graph
• On the size of outer-string representations
• Recognizing geometric intersection graphs stabbed by a line
• An algorithm for the maximum weight independent set problem on outerstring graphs

This page was built for publication: Computing maximum independent set on outerstring graphs and their relatives

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5918655)