Abstract
We give tight algorithmic lower and upper bounds for some double-parameterized subgraph problems when the clique-width of the input graph is one of the parameters. Let G be an arbitrary input graph on n vertices with clique-width at most w. We prove the following results.
-
The Dense (Sparse) k -Subgraph problem, which asks whether there exists an induced subgraph of G with k vertices and at least q edges (at most q edges, respectively), can be solved in time k O(w)·n, but it cannot be solved in time 2o(wlogk)·n O(1) unless the Exponential Time Hypothesis (ETH) fails.
-
The d -Regular Induced Subgraph problem, which asks whether there exists a d-regular induced subgraph of G, and the Minimum Subgraph of Minimum Degree at least d problem, which asks whether there exists a subgraph of G with k vertices and minimum degree at least d, can be solved in time d O(w)·n, but they cannot be solved in time 2o(wlogd)·n O(1) unless ETH fails.
This work is supported by EPSRC (EP/G043434/1 and F064551/1).
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Amini, O., Peleg, D., Pérennes, S., Sau, I., Saurabh, S.: Degree-Constrained Subgraph Problems: Hardness and Approximation Results. In: Bampis, E., Skutella, M. (eds.) WAOA 2008. LNCS, vol. 5426, pp. 29–42. Springer, Heidelberg (2009)
Amini, O., Sau, I., Saurabh, S.: Parameterized Complexity of the Smallest Degree-Constrained Subgraph Problem. In: Grohe, M., Niedermeier, R. (eds.) IWPEC 2008. LNCS, vol. 5018, pp. 13–29. Springer, Heidelberg (2008)
Arora, S., Karger, D.R., Karpinski, M.: Polynomial time approximation schemes for dense instances of p-hard problems. In: STOC, pp. 284–293. ACM (1995)
Asahiro, Y., Iwama, K., Tamaki, H., Tokuyama, T.: Greedily Finding a Dense Subgraph. In: Karlsson, R., Lingas, A. (eds.) SWAT 1996. LNCS, vol. 1097, pp. 136–148. Springer, Heidelberg (1996)
Bodlaender, H.L., Lokshtanov, D., Penninkx, E.: Planar Capacitated Dominating Set is W[1]-Hard. In: Chen, J., Fomin, F.V. (eds.) IWPEC 2009. LNCS, vol. 5917, pp. 50–60. Springer, Heidelberg (2009)
Cai, L., Juedes, D.W.: On the existence of subexponential parameterized algorithms. J. Comput. Syst. Sci. 67, 789–807 (2003)
Cheah, F., Corneil, D.G.: The complexity of regular subgraph recognition. Discrete Applied Mathematics 27, 59–68 (1990)
Chen, J., Chor, B., Fellows, M., Huang, X., Juedes, D., Kanj, I.A., Xia, G.: Tight lower bounds for certain parameterized NP-hard problems. Information and Computation 201, 216–231 (2005)
Chen, J., Huang, X., Kanj, I.A., Xia, G.: On the computational hardness based on linear FPT-reductions. J. Comb. Optim. 11, 231–247 (2006)
Chen, J., Huang, X., Kanj, I.A., Xia, G.: Strong computational lower bounds via parameterized complexity. J. Comput. Syst. Sci. 72, 1346–1367 (2006)
Chvátal, V., Fleischner, H., Sheehan, J., Thomassen, C.: Three-regular subgraphs of four-regular graphs. J. Graph Theory 3, 371–386 (1979)
Corneil, D.G., Perl, Y.: Clustering and domination in perfect graphs. Discrete Appl. Math. 9, 27–39 (1984)
Courcelle, B., Makowsky, J.A., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique-width. Theory Comput. Syst. 33, 125–150 (2000)
Courcelle, B., Olariu, S.: Upper bounds to the clique width of graphs. Discrete Appl. Math. 101, 77–114 (2000)
Demaine, E.D., Hajiaghayi, M.T., Kawarabayashi, K.: Algorithmic graph minor theory: Decomposition, approximation, and coloring. In: FOCS, pp. 637–646. IEEE Computer Society (2005)
Dom, M., Lokshtanov, D., Saurabh, S., Villanger, Y.: Capacitated Domination and Covering: A Parameterized Perspective. In: Grohe, M., Niedermeier, R. (eds.) IWPEC 2008. LNCS, vol. 5018, pp. 78–90. Springer, Heidelberg (2008)
Downey, R.G., Estivill-Castro, V., Fellows, M.R., Prieto, E., Rosamond, F.A.: Cutting up is hard to do: the parameterized complexity of k-cut and related problems. Electr. Notes Theor. Comput. Sci. 78 (2003)
Downey, R.G., Fellows, M.R.: Parameterized complexity. Monographs in Computer Science. Springer, New York (1999)
Feige, U., Peleg, D., Kortsarz, G.: The dense k-subgraph problem. Algorithmica 29, 410–421 (2001)
Fellows, M.R., Rosamond, F.A., Rotics, U., Szeider, S.: Clique-Width is NP-Complete. SIAM J. Discrete Math. 23, 909–939 (2009)
Flum, J., Grohe, M.: Parameterized complexity theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, Berlin (2006)
Fomin, F.V., Golovach, P.A., Lokshtanov, D., Saurabh, S.: Algorithmic lower bounds for problems parameterized by clique-width. In: SODA, pp. 493–502 (2010)
Hlinený, P., Oum, S.-I.: Finding branch-decompositions and rank-decompositions. SIAM J. Comput. 38, 1012–1032 (2008)
Hlinený, P., Oum, S.-I., Seese, D., Gottlob, G.: Width parameters beyond tree-width and their applications. Comput. J. 51, 326–362 (2008)
Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63, 512–530 (2001)
Keil, J.M., Brecht, T.B.: The complexity of clustering in planar graphs. J. Combin. Math. Combin. Comput. 9, 155–159 (1991)
Kortsarz, G., Peleg, D.: On choosing a dense subgraph (extended abstract). In: FOCS, pp. 692–701. IEEE (1993)
Lokshtanov, D., Marx, D., Saurabh, S.: Slightly superexponential parameterized problems. In: SODA (2011)
Mathieson, L., Szeider, S.: The parameterized complexity of regular subgraph problems and generalizations. In: CATS. CRPIT, vol. 77, pp. 79–86. Australian Computer Society (2008)
Oum, S.-I., Seymour, P.: Approximating clique-width and branch-width. J. Combin. Theory Ser. B 96, 514–528 (2006)
Moser, H., Thilikos, D.M.: Parameterized complexity of finding regular induced subgraphs. J. Discrete Algorithms 7, 181–190 (2009)
Stewart, I.A.: Deciding whether a planar graph has a cubic subgraph is np-complete. Discrete Mathematics 126, 349–357 (1994)
Stewart, I.A.: Finding regular subgraphs in both arbitrary and planar graphs. Discrete Applied Mathematics 68, 223–235 (1996)
Stewart, I.A.: On locating cubic subgraphs in bounded-degree connected bipartite graphs. Discrete Mathematics 163, 319–324 (1997)
Wanke, E.: k-NLC graphs and polynomial algorithms. Discrete Appl. Math. 54, 251–266 (1994)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Broersma, H., Golovach, P.A., Patel, V. (2012). Tight Complexity Bounds for FPT Subgraph Problems Parameterized by Clique-Width. In: Marx, D., Rossmanith, P. (eds) Parameterized and Exact Computation. IPEC 2011. Lecture Notes in Computer Science, vol 7112. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-28050-4_17
Download citation
DOI: https://doi.org/10.1007/978-3-642-28050-4_17
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-28049-8
Online ISBN: 978-3-642-28050-4
eBook Packages: Computer ScienceComputer Science (R0)