Optimization problems in dotted interval graphs. (English) Zbl 1298.05172
Summary: The class of \(D\)-dotted interval (\(d\)-DI) graphs is the class of intersection graphs of arithmetic progressions with jump (common difference) at most \(d\). We consider various classical graph-theoretic optimization problems in \(d\)-DI graphs of arbitrarily, but fixed, \(d\). We show that maximum independent set, minimum vertex cover, and minimum dominating set can be solved in polynomial time in this graph class, answering an open question posed by M. Jiang [Inf. Process. Lett. 98, No. 1, 29–33 (2006; Zbl 1187.68710)].
We also show that minimum vertex cover can be approximated within a factor of \((1 + \varepsilon)\), for any \(\varepsilon > 0\), in linear time. This algorithm generalizes to a wide class of deletion problems including the classical minimum feedback vertex set and minimum planar deletion problems.
Our algorithms are based on classical results in algorithmic graph theory and new structural properties of \(d\)-DI graphs that may be of independent interest.
We also show that minimum vertex cover can be approximated within a factor of \((1 + \varepsilon)\), for any \(\varepsilon > 0\), in linear time. This algorithm generalizes to a wide class of deletion problems including the classical minimum feedback vertex set and minimum planar deletion problems.
Our algorithms are based on classical results in algorithmic graph theory and new structural properties of \(d\)-DI graphs that may be of independent interest.
MSC:
| 05C35 | Extremal problems in graph theory |
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
Citations:
Zbl 1187.68710References:
| [1] | Agarwal, P. K.; van Kreveld, M. J.; Suri, S., Label placement by maximum independent set in rectangles, Comput. Geom.: Theory Appl., 11, 3-4, 209-218 (1998) · Zbl 0921.68100 |
| [2] | Aumann, Y.; Lewenstein, M.; Melamud, O.; Pinter, R. Y.; Yakhini, Z., Dotted interval graphs, ACM Trans. Algorithms, 8, 2, 9 (2012) · Zbl 1295.05220 |
| [3] | Bar-Yehuda, R.; Even, S., A local-ratio theorem for approximating the weighted vertex cover problem, Ann. Discrete Math., 25, 27-46 (1985) · Zbl 0557.90072 |
| [4] | Bar-Yehuda, R.; Halldórsson, M. M.; Naor, J.; Shachnai, H.; Shapira, I., Scheduling split intervals, SIAM J. Comput., 36, 1, 1-15 (2006) · Zbl 1111.68046 |
| [5] | Bar-Yehuda, R.; Hermelin, D.; Rawitz, D., Minimum vertex cover in rectangle graphs, Comput. Geom.: Theory Appl., 44, 6-7, 356-364 (2011) · Zbl 1225.05199 |
| [6] | Bodlaender, H. L., A tourist guide through treewidth, Acta Cybernet., 11, 1-2, 1-22 (1993) · Zbl 0804.68101 |
| [7] | Bodlaender, H. L., A linear-time algorithm for finding tree-decompositions of small treewidth, SIAM J. Comput., 25, 6, 1305-1317 (1996) · Zbl 0864.68074 |
| [8] | Borie, R. B.; Parker, R. G.; Tovey, C. A., Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families, Algorithmica, 7, 555-581 (1992) · Zbl 0753.05062 |
| [9] | Butman, A.; Hermelin, D.; Lewenstein, M.; Rawitz, D., Optimization problems in multiple-interval graphs, ACM Trans. Algorithms, 6, 2 (2010) · Zbl 1300.05295 |
| [11] | Courcelle, B., The monadic second-order logic of graphs. I. Recognizable sets of finite graphs, Inform. Comput., 85, 1, 12-75 (1990) · Zbl 0722.03008 |
| [12] | Erlebach, T.; Jansen, K.; Seidel, E., Polynomial-time approximation schemes for geometric intersection graphs, SIAM J. Comput., 34, 6, 1302-1323 (2005) · Zbl 1081.68031 |
| [13] | Fellows, M. R.; Hermelin, D.; Rosamond, F. A.; Vialette, S., On the parameterized complexity of multiple-interval graph problems, Theoret. Comput. Sci., 410, 1, 53-61 (2009) · Zbl 1161.68038 |
| [15] | Garey, M. R.; Johnson, D. S.; Miller, G. L.; Papadimitriou, C. H., The complexity of coloring circular arcs and chords, SIAM J. Algebr. Discrete Methods, 1, 2, 216-227 (1980) · Zbl 0499.05058 |
| [16] | Golumbic, M. C.; Hammer, P. L., Stability in circular arc graphs, J. Algorithms, 9, 3, 314-320 (1988) · Zbl 0651.68083 |
| [17] | Hermelin, D.; Rawitz, D., Optimization problems in multiple subtree graphs, Discrete Appl. Math., 159, 7, 588-594 (2011) · Zbl 1213.05247 |
| [18] | Hsu, W.-L.; Tsai, K.-H., Linear time algorithms on circular-arc graphs, Inform. Process. Lett., 40, 3, 123-129 (1991) · Zbl 0748.68044 |
| [19] | Hunt, H. B.; Marathe, M. V.; Radhakrishnan, V.; Ravi, S. S.; Rosenkrantz, D. J.; Stearns, R. E., NC-approximation schemes for NP- and PSPACE-hard problems for geometric graphs, J. Algorithms, 26, 2, 238-274 (1998) · Zbl 0894.68105 |
| [20] | Jiang, M., Approximating minimum coloring and maximum independent set in dotted interval graphs, Inform. Process. Lett., 98, 1, 29-33 (2006) · Zbl 1187.68710 |
| [21] | Robertson, N.; Seymour, P. D., Graph minors. I. Excluding a forest, J. Combin. Theory Ser. B, 35, 1, 39-61 (1983) · Zbl 0521.05062 |
| [24] | Yanovski, V., Approximation algorithm for coloring of dotted interval graphs, Inform. Process. Lett., 108, 1, 41-44 (2008) · Zbl 1185.05142 |
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.
