[1]
R. M. Karp, Reducibility among combinatorial problems, in Complexity of Computer Computations, 1972, pp. 85-103.
[2]
D. Kratsch, H. Müller, and I. Todinca, Feedback vertex set on AT-free graphs, Discrete Appl. Math., vol. 156, no. 10, pp. 1936-1947, 2008.
[3]
V. Bafna, P. Berman, and T. Fujito, A 2-approximation algorithm for the undirected feedback vertex set problem, SIAM J. Discrete Math., vol. 12, no. 3, pp. 289-297, 1999.
[4]
F. V. Fomin, S. Gaspers, A. V. Pyatkin, and I. Razgon, On the minimum feedback vertex set problem: Exact and enumeration algorithms, Algorithmica, vol. 52, no. 2, pp. 293-307, 2008.
[5]
M. Cygan, J. Nederlof, M. Pilipczuk, M. Pilipczuk, J. M. M. van Rooij, and J. O. Wojtaszczyk, Solving connectivity problems parameterized by treewidth in single exponential time, in Proc. 52nd FOCS, 2011, pp. 150-159.
[6]
H. L. Bodlaender, M. Cygan, S. Kratsch, and J. Nederlof, Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth, in Proc. 40th ICALP, 2013, pp. 196-207.
[7]
H. L. Bodlaender and T. C. van Dijk, A cubic kernel for feedback vertex set and loop cutset, Theory Comput. Syst., vol. 46, no. 3, pp. 566-597, 2010.
[8]
S. Thomassé, A 4k2 kernel for feedback vertex set, ACM Trans. Algorithms, vol. 6, no. 2, 2010.
[9]
P. Festa, P. M. Pardalos, and M. G. C. Resende, Feedback set problems, in Encyclopedia of Optimization, Second Edition. Springer, 2009, pp. 1005-1016.
[10]
M. R. Fellows, B. M. P. Jansen, and F. Rosamond, Towards fully multivariate algorithmics: Parameter ecology and the deconstruction of computational complexity, European J. Combin., vol. 34, no. 3, pp. 541-566, 2013.
[11]
C. Komusiewicz and R. Niedermeier, New races in parameterized algorithmics, in Proc. 37th MFCS, 2012, pp. 1930.
[12]
B. M. P. Jansen and S. Kratsch, Data reduction for graph coloring problems, Inform. Comput., vol. 231, pp. 70-88, 2013.
[13]
S. Hartung, C. Komusiewicz, and A. Nichterlein, On structural parameterizations for the 2-club problem, in Proc. 39th SOFSEM, 2013, pp. 233-243.
[14]
M. R. Fellows and M. A. Langston, Nonconstructive tools for proving polynomial-time decidability, J. ACM, vol. 35, no. 3, pp. 727-739, 1988.
[15]
N. Robertson and P. D. Seymour, Graph minors. XX. Wagner’s conjecture, J. Comb. Theory, Ser. B, vol. 92, no. 2, pp. 325-357, 2004.
[16]
R. G. Downey and M. R. Fellows, Parameterized computational feasibility, in Proc. 2nd Cornell Workshop on Feasible Mathematics, Birkhauser, 1994, pp. 219-244.
[17]
R. G. Downey and M. R. Fellows, Fundamentals of Parameterized Complexity, Texts in Computer Science. Springer, 2013.
[18]
H. L. Bodlaender, A partial k-arboretum of graphs with bounded treewidth, Theor. Comput. Sci., vol. 209, nos. 1-2, pp. 1-45, 1998.
[19]
B. A. Reed, K. Smith, and A. Vetta, Finding odd cycle transversals, Oper. Res. Lett., vol. 32, no. 4, pp. 299-301, 2004.
[20]
T. Kociumaka and M. Pilipczuk, Faster deterministic feedback vertex set, Inf. Process. Lett., vol. 114, no. 10, pp. 556-560, 2014.
[21]
B.-M. Bui-Xuan, O. Suchý, J. A. Telle, and M. Vatshelle, Feedback vertex set on graphs of low clique-width, Eur. J. Comb., vol. 34, no. 3, pp. 666-679, 2013.
[22]
M. Vatshelle, New width parameters of graphs, PhD dissertation, University of Bergen, May 2012.
[23]
M. C. Golumbic and U. Rotics, On the clique-width of some perfect graph classes, Int. J. Found. Comput. Sci., vol. 11, no. 3, pp. 423-443, 2000.
[24]
E. Balas and C. Yu, On graphs with polynomially solvable maximal-weight clique problem, Networks, vol. 19, pp. 247-253, 1989.
[25]
H. L. Bodlaender, Kernelization: New upper and lower bound techniques, in Proc. 4th IWPEC, 2009, pp. 17-37.
[26]
J. Chen, I. A. Kanj, and W. Jia, Vertex cover: Further observations and further improvements, J. Algorithms, vol. 41, no. 2, pp. 280-301, 2001.
[27]
K. Burrage, V. Estivill-Castro, M. R. Fellows, M. A. Langston, S. Mac, and F. A. Rosamond, The undirected feedback vertex set problem has a poly(k) kernel, in Proc. 2nd IWPEC, 2006, pp. 192-202.
[28]
H. L. Bodlaender, A cubic kernel for feedback vertex set, in Proc. 24th STACS, 2007, pp. 320-331.
[29]
H. Dell and D. van Melkebeek, Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses, in Proc. 42nd STOC, 2010, pp. 251-260.
[30]
C.-K. Yap, Some consequences of non-uniform conditions on uniform classes, Theor. Comput. Sci., vol. 26, pp. 287-300, 1983.
[31]
F. V. Fomin, B. M. P. Jansen, and M. Pilipczuk, Preprocessing subgraph and minor problems: When does a small vertex cover help? J. Comput. Syst. Sci., vol. 80, no. 2, pp. 468-495, 2014.
[32]
M. R. Fellows, D. Lokshtanov, N. Misra, M. Mnich, F. A. Rosamond, and S. Saurabh, The complexity ecology of parameters: An illustration using bounded max leaf number, Theory Comput. Syst., vol. 45, no. 4, pp. 822-848, 2009.
[33]
D. J. Kleitman and D. B. West, Spanning trees with many leaves, SIAM J. Discret. Math., vol. 4, no. 1, pp. 99-106, 1991.
[34]
H. L. Bodlaender, B. M. P. Jansen, and S. Kratsch, Kernelization lower bounds by cross-composition, SIAM J. Discrete Math., vol. 28, no. 1, pp. 277-305, 2014.
[35]
L. Fortnow and R. Santhanam, Infeasibility of instance compression and succinct PCPs for NP, J. Comput. Syst. Sci., vol. 77, no. 1, pp. 91-106, 2011.
[36]
B. M. P. Jansen and H. L. Bodlaender, Vertex cover kernelization revisited — Upper and lower bounds for a refined parameter, Theory Comput. Syst., vol. 53, no. 2, pp. 263-299, 2013.
[37]
M. R. Garey and D. S. Johnson, Computers and Intractability, A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York, 1979.
[38]
R. Sasák, Comparing 17 graph parameters, Master degree dissertation, University of Bergen, 2010
[39]
J. Flum and M. Grohe, Parameterized Complexity Theory. Springer-Verlag, New York, Inc., 2006.
[40]
R. Diestel, Graph Theory, 4th ed. Springer-Verlag, Heidelberg, 2010.
[41]
A. Brandstädt, V. B. Le, and J. P. Spinrad, Graph Classes: A Survey. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 1999.
[42]
B. Courcelle, J. A. Makowsky, and U. Rotics, Linear time solvable optimization problems on graphs of bounded clique-width, Theory Comput. Syst., vol. 33, no. 2, pp. 125-150, 2000.
[43]
S.-I. Oum, Graphs of bounded rank-width, PhD dissertation, Princeton University, Princeton, NJ, USA, 2005.
[44]
B.-M. Bui-Xuan, J. A. Telle, and M. Vatshelle, Boolean-width of graphs, Theor. Comput. Sci., vol. 412, no. 39, pp. 5187-5204, 2011.
[45]
D. Marx, Chordal deletion is fixed-parameter tractable, Algorithmica, vol. 57, no. 4, pp. 747-768, 2010.
[46]
F. Gavril, The intersection graphs of subtrees in trees are exactly the chordal graphs, J. Comb. Theory, Ser. B, vol. 16, no. 1, pp. 47-56, 1974.
[47]
Y. Shibata, On the tree representation of chordal graphs, J. Graph Theory, vol. 12, no. 3, pp. 421-428, 1988.
[48]
T. Kloks, C.-M. Lee, and J. Liu, New algorithms for k-face cover, k-feedback vertex set, and k-disjoint cycles on plane and planar graphs, in Proc. 28th WG, 2002, pp. 282-295.
[49]
D. S. Johnson, M. Yannakakis, and C. H. Papadimitriou, On generating all maximal independent sets, Inf. Process. Lett., vol. 27, no. 3, pp. 119-123, 1988.
[50]
H. L. Bodlaender, S. Thomassé, and A. Yeo, Kernel bounds for disjoint cycles and disjoint paths, Theor. Comput. Sci., vol. 412, no. 35, pp. 4570-4578, 2011.
[51]
F. V. Fomin, D. Lokshtanov, N. Misra, and S. Saurabh, Planar ℱ-deletion: Approximation, kernelization and optimal FPT algorithms, in Proc. 53rd FOCS, 2012, pp. 470-479.
[52]
D. Binkele-Raible, H. Fernau, F. V. Fomin, D. Lokshtanov, S. Saurabh, and Y. Villanger, Kernel(s) for problems with no kernel: On out-trees with many leaves, ACM Trans. Algorithms, vol. 8, no. 4, p. 38, 2012.
[53]
D. Hermelin, S. Kratsch, K. Sołtys, M. Wahlström, and X. Wu, A completeness theory for polynomial (Turing) kernelization, in Proc. 8th IPEC, 2013, pp. 202-215.
[54]
L. Cai, Parameterized complexity of vertex colouring, Discrete Appl. Math., vol. 127, no. 3, pp. 415-429, 2003.
[55]
S. Ueno, Y. Kajitani, and S. Gotoh, On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three, Discrete Math., vol. 72, no. 13, pp. 355-360, 1988.
AI Chat Paper
