Abstract
In this paper, we study the parameterized complexity of the problems of partitioning the vertex set of a graph into two parts \(V_A\) and \(V_B\) such that \(V_A\) induces a graph with degree at most \(a\) (resp., an \(a\)-regular graph) and \(V_B\) induces a graph with degree at most \(b\) (resp., a \(b\)-regular graph). These two problems are called Upper-Degree-Bounded Bipartition and Regular Bipartition respectively. First, we prove that the two problems are NP-complete with any nonnegative integers \(a\) and \(b\) except \(a=b=0\). Second, we show that the two problems with parameter \(k\) being the size of \(V_A\) of a bipartition \((V_A,V_B)\) are fixed-parameter tractable for fixed integer \(a\) or \(b\) by deriving some problem kernels for them.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Amini, O., Saub, I., Saurabh, S.: Parameterized complexity of finding small degree-constrained subgraphs. Journal of Discrete Algorithms 10, 70–83 (2012)
Bazgan, C., Tuza, Z., Vanderpooten, D.: Efficient algorithms for decomposing graphs under degree constraints. Discrete Applied Mathematics 155, 979–988 (2007)
Bazgan, C., Tuza, Z., Vanderpooten, D.: Degree-constrained decompositions of graphs: bounded treewidth and planarity. Theoretical Computer Science 355(3), 389–395 (2006)
Bazgan, Cristina, Tuza, Zsolt, Vanderpooten, Daniel: On the Existence and Determination of Satisfactory Partitions in a Graph. In: Ibaraki, Toshihide, Katoh, Naoki, Ono, Hirotaka (eds.) ISAAC 2003. LNCS, vol. 2906, pp. 444–453. Springer, Heidelberg (2003)
Betzler, N., Bredereck, R., Niedermeier, R., Uhlmann, J.: On bounded-degree vertex deletion parameterized by treewidth. Discrete Applied Mathematics 160(1–2), 53–60 (2012)
Chvátal, V.: Recognizing decomposable graphs. J. Graph Theory 8, 51–53 (1984)
Diwan, A.: Decomposing graphs with girth at least five under degree constraints. J. Graph Theory 33, 237–239 (2000)
Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness II: On completeness for W[1]. Theoretical Computer Science A 141(1–2), 109–131 (1995)
Fellows, M.R., Guo, J., Moser, H., Niedermeier, R.: A generalization of Nemhauser and Trotter’s local optimization theorem. Journal of Computer and System Sciences 77, 1141–1158 (2011)
Grinsteada, D.L., Slatera, J., Sherwani, N.A., Holmesc, N.D.: Efficient edge domination problems in graphs. Information Processing Letters 48, 221–228 (1993)
Garey, M.R., Johnson, D.S.: Computers and intractability: A guide to the theory of NP-completeness. Freeman, San Francisco (1979)
Kaneko, A.: On decomposition of triangle-free graphs under degree constraints. J. Graph Theory 27, 7–9 (1998)
Lin, Min Chih, Mizrahi, Michel J., Szwarcfiter, Jayme L.: An \(O^{*}\)(1.1939\(^{n}\)) Time Algorithm for Minimum Weighted Dominating Induced Matching. In: Cai, Leizhen, Cheng, Siu-Wing, Lam, Tak-Wah (eds.) Algorithms and Computation. LNCS, vol. 8283, pp. 558–567. Springer, Heidelberg (2013)
Mathieson, L., Szeider, S.: The parameterized complexity of regular subgraphs problems and generalizations. In: CATS 2008, CRPIT 77, pp. 79–86 (2008)
Moser, H., Thilikos, D.: Parameterized complexity of finding regular induced subgraphs. Journal of Discrete Algorithms 7, 181–190 (2009)
Stiebitz, M.: Decomposing graphs under degree constraints. J. Graph Theory 23, 321–324 (1996)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Xiao, M., Nagamochi, H. (2014). Complexity and Kernels for Bipartition into Degree-bounded Induced Graphs. In: Ahn, HK., Shin, CS. (eds) Algorithms and Computation. ISAAC 2014. Lecture Notes in Computer Science(), vol 8889. Springer, Cham. https://doi.org/10.1007/978-3-319-13075-0_34
Download citation
DOI: https://doi.org/10.1007/978-3-319-13075-0_34
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-13074-3
Online ISBN: 978-3-319-13075-0
eBook Packages: Computer ScienceComputer Science (R0)