Proper interval vertex deletion. (English) Zbl 1262.68052
Summary: The NP-complete problem Proper Interval Vertex Deletion is to decide whether an input graph on \(n\) vertices and \(m\) edges can be turned into a proper interval graph by deleting at most \(k\) vertices. R. van Bevern et al. [Lect. Notes Comput. Sci. 6410, 232–243 (2010; Zbl 1309.68158)] showed that this problem can be solved in \(\mathcal {O}((14k +14)^{k+1} kn^{6})\) time. We improve this result by presenting an \(\mathcal {O}(6^{k} kn^{6})\) time algorithm for Proper Interval Vertex Deletion. Our fixed-parameter algorithm is based on a new structural result stating that every connected component of a {claw, net, tent, \(C _{4},C _{5},C _{6}\}\)-free graph is a proper circular arc graph, combined with a simple greedy algorithm that solves Proper Interval Vertex Deletion on {claw, net, tent,\(C _{4},C _{5},C _{6}\}\)-free graphs in \(\mathcal {O}(n+m)\) time. Our approach also yields a polynomial-time 6-approximation algorithm for the optimization variant of Proper Interval Vertex Deletion.
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
Citations:
Zbl 1309.68158References:
| [1] | Brandstädt, A., Dragan, F.F.: On linear and circular structure of (claw, net)-free graphs. Discrete Appl. Math. 129(2–3), 285–303 (2003) · Zbl 1032.05095 · doi:10.1016/S0166-218X(02)00571-1 |
| [2] | Brandstädt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey. Society for Industrial and Applied Mathematics, Philadelphia (1999) · Zbl 0919.05001 |
| [3] | Cai, L.: Fixed-parameter tractability of graph modification problems for hereditary properties. Inf. Process. Lett. 58(4), 171–176 (1996) · Zbl 0875.68702 · doi:10.1016/0020-0190(96)00050-6 |
| [4] | Cao, Y., Chen, J., Liu, Y.: On feedback vertex set new measure and new structures. In: Proceedings SWAT 2010. Lecture Notes in Computer Science, vol. 6139, pp. 93–104. Springer, Berlin (2010) · Zbl 1285.68061 |
| [5] | Chen, J., Liu, Y., Lu, S., O’Sullivan, B., Razgon, I.: A fixed-parameter algorithm for the directed feedback vertex set problem. J. ACM 55(5), 21:1–21:19 (2008) |
| [6] | Chen, J., Kanj, I.A., Xia, G.: Improved upper bounds for vertex cover. Theor. Comput. Sci. 411(40–42), 3736–3756 (2010) · Zbl 1205.05217 · doi:10.1016/j.tcs.2010.06.026 |
| [7] | Courcelle, B.: Graph rewriting: an algebraic and logic approach. In: Handbook of Theoretical Computer Science, Volume B: Formal Models and Semantics (B), pp. 193–242 (1990) · Zbl 0900.68282 |
| [8] | Deng, X., Hell, P., Huang, J.: Linear-time representation algorithms for proper circular-arc graphs and proper interval graphs. SIAM J. Comput. 25(2), 390–403 (1996) · Zbl 0858.05094 · doi:10.1137/S0097539792269095 |
| [9] | Gavril, F.: Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph. SIAM J. Comput. 1(2), 180–187 (1972) · Zbl 0227.05116 · doi:10.1137/0201013 |
| [10] | Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980) · Zbl 0541.05054 |
| [11] | Grötschel, M., Lovász, L., Schrijver, A.: Polynomial algorithms for perfect graphs. In: Berge, C., Chvátal, V. (eds.) Topics on Perfect Graphs. Annals of Discrete Mathematics, vol. 21, pp. 325–356 (1984) · Zbl 0554.05041 |
| [12] | Heggernes, P., van ’t Hof, P., Jansen, B.M.P., Kratsch, S., Villanger, Y.V.: Parameterized complexity of vertex deletion into perfect graph classes. In: Proceedings FCT 2011. Lecture Notes in Computer Science, vol. 6914, pp. 240–251 (2011) · Zbl 1342.68165 |
| [13] | Kaplan, H., Shamir, R., Tarjan, R.E.: Tractability of parameterized completion problems on chordal, strongly chordal, and proper interval graphs. SIAM J. Comput. 28(5), 1906–1922 (1999) · Zbl 0928.68124 · doi:10.1137/S0097539796303044 |
| [14] | Kawarabayashi, K., Reed, B.A.: Computing crossing number in linear time. In: Proceedings STOC 2007, pp. 382–390. ACM, New York (2007) · Zbl 1232.90339 |
| [15] | Lekkerkerker, C., Boland, J.: Representation of a finite graph by a set of intervals on the real line. Fundam. Math. 51, 45–64 (1962) · Zbl 0105.17501 |
| [16] | Lewis, J.M., Yannakakis, M.: The node-deletion problem for hereditary properties is NP-complete. J. Comput. Syst. Sci. 20(2), 219–230 (1980) · Zbl 0436.68029 · doi:10.1016/0022-0000(80)90060-4 |
| [17] | Lokshtanov, D.: Wheel-free deletion is W[2]-hard. In: Proceedings IWPEC 2008. Lecture Notes in Computer Science, vol. 5018, pp. 141–147. Springer, Berlin (2008) · Zbl 1142.68366 |
| [18] | Marx, D.: Chordal deletion is fixed-parameter tractable. Algorithmica 57(4), 747–768 (2010) · Zbl 1220.05066 · doi:10.1007/s00453-008-9233-8 |
| [19] | Marx, D., Schlotter, I.: Obtaining a planar graph by vertex deletion. Algorithmica 62(3–4), 807–822 (2012) · Zbl 1239.05044 · doi:10.1007/s00453-010-9484-z |
| [20] | Roberts, F.S.: Indifference graphs. In: Proof Techniques in Graph Theory, pp. 139–146. Academic Press, San Diego (1969) · Zbl 0193.24205 |
| [21] | Seymour, P.D., Thomas, R.: Call routing and the ratcatcher. Combinatorica 14(2), 217–241 (1994) · Zbl 0799.05057 · doi:10.1007/BF01215352 |
| [22] | Tucker, A.: Structure theorems for some circular-arc graphs. Discrete Math. 7, 167–195 (1974) · Zbl 0269.05119 · doi:10.1016/S0012-365X(74)80027-0 |
| [23] | van Bevern, R., Komusiewicz, C., Moser, H., Niedermeier, R.: Measuring indifference: unit interval vertex deletion. In: Proceedings WG 2010. Lecture Notes in Computer Science, vol. 6410, pp. 232–243. Springer, Berlin (2010) · Zbl 1309.68158 |
| [24] | Villanger, Y.V., Heggernes, P., Paul, C., Telle, J.A.: Interval completion is fixed parameter tractable. SIAM J. Comput. 38(5), 2007–2020 (2009) · Zbl 1227.05241 · doi:10.1137/070710913 |
| [25] | Wegner, G.: Eigenschaften der Nerven homologisch-einfacher Familien im R n . Ph.D. thesis, University of Göttingen (1967) |
| [26] | Yannakakis, M.: Edge-deletion problems. SIAM J. Comput. 10(2), 297–309 (1981) · Zbl 0468.05043 · doi:10.1137/0210021 |
| [27] | Yannakakis, M.: Computing minimum fill-in is NP-complete. SIAM J. Algebr. Discrete Methods 2(1), 77–79 (1981) · Zbl 0496.68033 · doi:10.1137/0602010 |
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.
