Contracting Graphs to Paths and Trees

Alon, N., Yuster, R., Zwick, U.: Color-coding. J. ACM 42(4), 844–856 (1995)

Arora, S., Barak, B.: Computational Complexity: A Modern Approach, 1st edn. Cambridge University Press, New York (2009)

Asano, T., Hirata, T.: Edge-contraction problems. J. Comput. Syst. Sci. 26(2), 197–208 (1983)

Binkele-Raible, D., Fernau, H.: Enumerate and measure: improving parameter budget management. In: Raman, V., Saurabh, S. (eds.) 5th International Symposium on Parameterized and Exact Computation, IPEC 2010. Lecture Notes in Computer Science, vol. 6478, pp. 38–49. Springer, Berlin (2010)

Bodlaender, H.L.: On disjoint cycles. Int. J. Found. Comput. Sci. 5(1), 59–68 (1994)

Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels. J. Comput. Syst. Sci. 75(8), 423–434 (2009)

Bodlaender, H.L., Fomin, F.V., Lokshtanov, D., Penninkx, E., Saurabh, S., Thilikos, D.M.: (Meta) kernelization. In: 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, pp. 629–638. IEEE Computer Society, Washington (2009)

Bodlaender, H.L., Thomassé, S., Yeo, A.: Kernel bounds for disjoint cycles and disjoint paths. Theor. Comput. Sci. 412(35), 4570–4578 (2011)

Brouwer, A.E., Veldman, H.J.: Contractibility and NP-completeness. J. Graph Theory 11(1), 71–79 (1987)

Cai, L.: Fixed-parameter tractability of graph modification problems for hereditary properties. Inf. Process. Lett. 58(4), 171–176 (1996)

Cao, Y., Chen, J., Liu, Y.: On feedback vertex set new measure and new structures. In: Kaplan, H. (ed.) 12th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2010. Lecture Notes in Computer Science, vol. 6139, pp. 93–104. Springer, Berlin (2010)

Chen, J., Fomin, F.V., Liu, Y., Lu, S., Villanger, Y.: Improved algorithms for feedback vertex set problems. J. Comput. Syst. Sci. 74(7), 1188–1198 (2008)

Chen, J., Kneis, J., Lu, S., Molle, D., Richter, S., Rossmanith, P., Sze, S.H., Zhang, F.: Randomized divide-and-conquer: improved path, matching, and packing algorithms. SIAM J. Comput. 38(6), 2526–2547 (2009)

Courcelle, B.: The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inf. Comput. 85(1), 12–75 (1990)

Cygan, M.: Deterministic parameterized connected vertex cover. In: Fomin, F. (ed.) 13th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2012. Lecture Notes in Computer Science. Springer (to appear). arXiv:1202.6642 , February 2012

Cygan, M., Nederlof, J., Pilipczuk, M., Pilipczuk, M., van Rooij, J.M.M., Wojtaszczyk, J.O.: Solving connectivity problems parameterized by treewidth in single exponential time. In: Ostrovsky, R. (ed.) 52nd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2011, pp. 150–159. IEEE, New York (2011)

Dehne, F.K.H.A., Fellows, M.R., Langston, M.A., Rosamond, F.A., Stevens, K.: An O(2 O(k) n 3) FPT algorithm for the undirected feedback vertex set problem. Theory Comput. Syst. 41(3), 479–492 (2007)

Díaz, J., Thilikos, D.M.: Fast FPT-algorithms for cleaning grids. In: Durand, B., Thomas, W. (eds.) 23rd Annual Symposium on Theoretical Aspects of Computer Science, STACS 2006. Lecture Notes in Computer Science, vol. 3884, pp. 361–371. Springer, Berlin (2006)

Dom, M., Lokshtanov, D., Saurabh, S.: Incompressibility through colors and IDs. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S.E., Thomas, W. (eds.) 36th International Colloquium on Automata, Languages and Programming, ICALP 2009. Lecture Notes in Computer Science, vol. 5555, pp. 378–389. Springer, Berlin (2009)

Downey, R.G., Fellows, R.: Parameterized Complexity. Monographs in Computer Science. Springer, Berlin (1999)

Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science. Springer, Berlin (2006)

Fortnow, L., Santhanam, R.: Infeasibility of instance compression and succinct PCPs for NP. J. Comput. Syst. Sci. 77(1), 91–106 (2011)

Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman & Co., New York (1979)

Golovach, P.A., Kaminski, M., Paulusma, D., Thilikos, D.M.: Increasing the minimum degree of a graph by contractions. In: Marx, D., Rossmanith, P. (eds.) 6th International Symposium on Parameterized and Exact Computation, IPEC 2011. Lecture Notes in Computer Science, vol. 7112, pp. 67–79. Springer, Berlin (2011)

Guo, J., Gramm, J., Hüffner, F., Niedermeier, R., Wernicke, S.: Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization. J. Comput. Syst. Sci. 72(8), 1386–1396 (2006)

Heggernes, P., van ’t Hof, P., Jansen, B.M.P., Kratsch, S., Villanger, Y.: Parameterized complexity of vertex deletion into perfect graph classes. In: Owe, O., Steffen, M., Telle, J.A. (eds.) 18th International Symposium on Fundamentals of Computation Theory, FCT 2011. Lecture Notes in Computer Science, vol. 6914, pp. 240–251. Springer, Berlin (2011)

Heggernes, P., van ’t Hof, P., Lévêque, B., Lokshtanov, D., Paul, C.: Contracting graphs to paths and trees. In: Marx, D., Rossmanith, P. (eds.) 6th International Symposium on Parameterized and Exact Computation, IPEC 2011. Lecture Notes in Computer Science, vol. 7112, pp. 55–66. Springer, Berlin (2011)

Heggernes, P., van ’t Hof, P., Lévêque, B., Paul, C.: Contracting chordal graphs and bipartite graphs to paths and trees. Electron. Notes Discrete Math. 37, 87–92 (2011)

Heggernes, P., van ’t Hof, P., Lokshtanov, D., Paul, C.: Obtaining a bipartite graph by contracting few edges. In: Chakraborty, S., Kumar, A. (eds.) IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2011. LIPIcs, vol. 13, pp. 217–228. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Saarbrücken (2011)

Kawarabayashi, K., Reed, B.A.: An (almost) linear time algorithm for odd cycles transversal. In: Charikar, M. (ed.) 21st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, pp. 365–378 (2010)

Martin, B., Paulusma, D.: The computational complexity of disconnected cut and 2k 2-partition. In: Lee, J.H.M. (ed.) 17th International Conference on Principles and Practice of Constraint Programming, CP 2011. Lecture Notes in Computer Science, vol. 6876, pp. 561–575. Springer, Berlin (2011)

Marx, D.: Chordal deletion is fixed-parameter tractable. Algorithmica 57(4), 747–768 (2010)

Marx, D., Schlotter, I.: Obtaining a planar graph by vertex deletion. Algorithmica 62(3–4), 807–822 (2012)

Naor, M., Schulman, L.J., Srinivasan, A.: Splitters and near-optimal derandomization. In: 36th Annual Symposium on Foundations of Computer Science, FOCS 1995, pp. 182–191. IEEE Computer Society, Washington (1995)

Natanzon, A., Shamir, R., Sharan, R.: Complexity classification of some edge modification problems. Discrete Appl. Math. 113(1), 109–128 (2001)

Philip, G., Raman, V., Villanger, Y.: A quartic kernel for pathwidth-one vertex deletion. In: Thilikos, D.M. (ed.) 36th International Workshop on Graph Theoretic Concepts in Computer Science, WG 2010. Lecture Notes in Computer Science, vol. 6410, pp. 196–207 (2010)

Pilipczuk, M.: Problems parameterized by treewidth tractable in single exponential time: A logical approach. In: Murlak, F., Sankowski, P. (eds.) 36th International Symposium on Mathematical Foundations of Computer Science 2011, MFCS 2011. Lecture Notes in Computer Science, vol. 6907, pp. 520–531. Springer, Berlin (2011)

Thomassé, S.: A 4k 2 kernel for feedback vertex set. ACM Trans. Algorithms 6(2) (2010)

van Bevern, R., Komusiewicz, C., Moser, H., Niedermeier, R.: Measuring indifference: unit interval vertex deletion. In: Thilikos, D.M. (ed.) 36th International Workshop on Graph Theoretic Concepts in Computer Science, WG 2010. Lecture Notes in Computer Science, vol. 6410, pp. 232–243. Springer, Berlin (2010)

van ’t Hof, P., Villanger, Y.: Proper interval vertex deletion. Algorithmica (to appear). http://dx.doi.org/10.1007/s00453-012-9661-3

Watanabe, T., Ae, T., Nakamura, A.: On the removal of forbidden graphs by edge-deletion or by edge-contraction. Discrete Appl. Math. 3(2), 151–153 (1981)

Watanabe, T., Ae, T., Nakamura, A.: On the NP-hardness of edge-deletion and -contraction problems. Discrete Appl. Math. 6(1), 63–78 (1983)

Yannakakis, M.: Node- and edge-deletion NP-complete problems. In: Lipton, R.J., Burkhard, W.A., Savitch, W.J., Friedman, E.P., Aho, A.V. (eds.) 10th Annual ACM Symposium on Theory of Computing, STOC 1978, pp. 253–264. ACM, New York (1978)

Yannakakis, M.: The effect of a connectivity requirement on the complexity of maximum subgraph problems. J. ACM 26(4), 618–630 (1979)

Yannakakis, M.: Edge-deletion problems. SIAM J. Comput. 10(2), 297–309 (1981)