An algorithm for the maximum weight independent set problem on outerstring graphs. (English) Zbl 1378.05154
Summary: Outerstring graphs are the intersection graphs of curves that lie inside a disk such that each curve intersects the boundary of the disk. Outerstring graphs are among the most general classes of intersection graphs studied. To date, no polynomial time algorithm is known for any of the classical graph optimization problems on outerstring graphs; in fact, most are NP-hard. It is known that there is an intersection model for any outerstring graph that consists of polygonal arcs attached to a circle. However, this representation may require an exponential number of segments relative to the size of the graph.
Given an outerstring graph and an intersection model consisting of polygonal arcs with a total of \(N\) segments, we develop an algorithm that solves the Maximum Weight Independent Set problem in \(O(N^3)\) time. If the polygonal arcs are restricted to single segments, then outersegment graphs result. For outersegment graphs, we solve the Maximum Weight Independent Set problem in \(O(n^3)\) time where \(n\) is the number of vertices in the graph.
Given an outerstring graph and an intersection model consisting of polygonal arcs with a total of \(N\) segments, we develop an algorithm that solves the Maximum Weight Independent Set problem in \(O(N^3)\) time. If the polygonal arcs are restricted to single segments, then outersegment graphs result. For outersegment graphs, we solve the Maximum Weight Independent Set problem in \(O(n^3)\) time where \(n\) is the number of vertices in the graph.
MSC:
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
| 05C35 | Extremal problems in graph theory |
| 68Q25 | Analysis of algorithms and problem complexity |
References:
| [1] | Agarwal, Pankaj; van Kreveld, Marc; Suri, Subhash, Label placement by maximum independent set in rectangles, Comput. Geom., 11, 3, 209-218 (1998) · Zbl 0921.68100 |
| [2] | AhmadiNejad, AmirMahdi; Zarrabi-Zadeh, Hamid, The maximum disjoint set of boundary rectangles, (Proceedings 26th Canadian Conference on Computational Geometry. Proceedings 26th Canadian Conference on Computational Geometry, CCCG (2014)), 302-307 |
| [3] | Assadi, Sepehr; Emamjomeh-Zadeh, Ehsan; Yazdanbod, Sadra; Zarrabi-Zadeh, Hamid, On the rectangle escape problem, (Proceedings 25th Canadian Conference on Computational Geometry. Proceedings 25th Canadian Conference on Computational Geometry, CCCG (2013)), 235-240 · Zbl 1372.68245 |
| [4] | Benzer, Seymour, On the topology of genetic fine structure, Proc. Natl. Acad. Sci., 47, 1607 (1959) |
| [5] | Cabello, Sergio; Cardinal, Jean; Langerman, Stefan, The clique problem in ray intersection graphs, Discrete Comput. Geom., 50, 3, 771-783 (2013) · Zbl 1275.05032 |
| [6] | Chalopin, Jérémie; Gonçalves, Daniel, Every planar graph is the intersection graph of segments in the plane, (Proceedings of STOC (2009)), 631-638 · Zbl 1304.05115 |
| [7] | Ehrlich, S.; Even, S.; Tarjan, R. E., Intersection graphs of curves in the plane, J. Comb. Theory, Ser. B, 21, 8-20 (1976) · Zbl 0348.05113 |
| [8] | Flier, Holger; Mihalák, Matúš; Schöbel, Anita; Widmayer, Peter; Zych, Anna, Vertex disjoint paths for dispatching in railways, (Proceedings of ATMOS (2010)), 61-73 · Zbl 1247.90044 |
| [9] | Flier, Holger; Mihalák, Matúš; Widmayer, Peter; Zych, Anna, Maximum independent set in 2-direction outersegment graphs, (Proceedings of WG (2011)), 155-166 · Zbl 1341.05186 |
| [10] | Fox, Jacob; Pach, János, Computing the independence number of intersection graphs, (Proceedings of 22nd Annual ACM-SIAM Symposium on Discrete Algorithms. Proceedings of 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA (2011)), 1161-1165 · Zbl 1377.68275 |
| [11] | Fox, Jacob; Pach, János, Coloring \(K_k\)-free intersection graphs of geometric objects in the plane, Eur. J. Comb., 33, 5, 853-866 (2012) · Zbl 1239.05065 |
| [12] | Fox, Jacob; Pach, János, String graphs and incomparability graphs, Adv. Math., 230, 1381-1401 (2012) · Zbl 1244.05073 |
| [13] | Fukuda, Takeshi; Morimoto, Yasuhiko; Morishita, Shinichi; Tokuyama, Takeshi, Data mining with optimized two-dimensional association rules, ACM Trans. Database Syst., 26, 2, 179-213 (2001) · Zbl 1136.68381 |
| [14] | Gavril, Fanica, Maximum weight independent sets and cliques in intersection graphs of filaments, Inf. Process. Lett., 73, 181-188 (2000) · Zbl 1339.05287 |
| [15] | Golumbic, Martin; Rotem, Doron; Urrutia, Jorge, Comparability graphs and intersection graphs, Discrete Math., 43, 37-46 (1983) · Zbl 0502.05050 |
| [16] | Kong, Hui; Ma, Qiang; Yan, Tan; Wong, Martin D. F., An optimal algorithm for finding disjoint rectangles and its applications to PCB routing, (Proceedings of DAC (2010)), 212-217 |
| [17] | Kratochvíl, Jan, String graphs I. The number of critical nonstring graphs is infinite, J. Comb. Theory, Ser. B, 52, 1, 53-66 (1991) · Zbl 0675.05058 |
| [18] | Kratochvíl, Jan, String graphs II. Recognizing string graphs is NP-hard, J. Comb. Theory, Ser. B, 52, 1, 67-78 (1991) · Zbl 0661.05054 |
| [19] | Kratochvíl, Jan; Goljan, Miroslav; Kučera, Petr, String Graphs (1986), Academia: Academia Prague · Zbl 0607.05031 |
| [20] | Kratochvíl, Jan; Lubiw, Anna; Nešetřil, Jaroslav, Noncrossing subgraphs in topological layouts, SIAM J. Discrete Math., 4, 2, 223-244 (1991) · Zbl 0731.68047 |
| [21] | Kratochvíl, Jan; Matoušek, Jiří, String graphs requiring exponential representations, J. Comb. Theory, Ser. B, 53, 1, 1-4 (1991) · Zbl 0675.05059 |
| [22] | Kratochvíl, Jan; Nešetřil, Jaroslav, Independent set and clique problems in intersection-defined classes of graphs, Comment. Math. Univ. Carol., 31, 85-93 (1990) · Zbl 0727.05056 |
| [23] | Middendorf, Matthias; Pfeiffer, Frank, The max clique problem in classes of string-graphs, Discrete Math., 108, 365-372 (1992) · Zbl 0764.68129 |
| [24] | Schaefer, Marcus; Sedgwick, Eric; Štefankovič, Daniel, Recognizing string graphs is in NP, J. Comput. Syst. Sci., 67, 2, 365-380 (2003) · Zbl 1072.68081 |
| [25] | Sinden, Frank W., Topology of thin film RC-circuits, Bell Syst. Tech. J., 45, 1639-1662 (1966) · Zbl 0144.45601 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
