Abstract
We show that several variants of the problem k -Dominating Set, including k -Connected Dominating Set, k -Independent Dominating Set, k -Dominating Clique, d -Distance k -Dominating Set, k -Perfect Code and d -Distance k -Perfect Code, when parameterized by the solution size k, remain W[1]-hard in either multiple-interval graphs or their complements or both.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Bar-Yehuda, R., Halldórsson, M.M., Naor, J., Shachnai, H., Shapira, I.: Scheduling split intervals. SIAM Journal on Computing 36, 1–15 (2006)
Butman, A., Hermelin, D., Lewenstein, M., Rawitz, D.: Optimization problems in multiple-interval graphs. ACM Transactions on Algorithms 6, 40 (2010)
Cesati, M.: Perfect Code is W[1]-complete. Information Processing Letters 81, 163–168 (2002)
Chen, Z., Fu, B., Jiang, M., Zhu, B.: On recovering syntenic blocks from comparative maps. Journal of Combinatorial Optimization 18, 307–318 (2009)
Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness II: on completeness for W[1]. Theoretical Computer Science 141, 109–131 (1995)
Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1999)
Fellows, M.R., Hermelin, D., Rosamond, F., Vialette, S.: On the parameterized complexity of multiple-interval graph problems. Theoretical Computer Science 410, 53–61 (2009)
Jiang, M.: Approximation algorithms for predicting RNA secondary structures with arbitrary pseudoknots. IEEE/ACM Transactions on Computational Biology and Bioinformatics 7, 323–332 (2010)
Jiang, M.: On the parameterized complexity of some optimization problems related to multiple-interval graphs. Theoretical Computer Science 411, 4253–4262 (2010)
Jiang, M.: Recognizing d-Interval Graphs and d-Track Interval Graphs. In: Lee, D.-T., Chen, D.Z., Ying, S. (eds.) FAW 2010. LNCS, vol. 6213, pp. 160–171. Springer, Heidelberg (2010)
Jiang, M., Zhang, Y.: Parameterized Complexity in Multiple-Interval Graphs: Partition, Separation, Irredundancy. In: Fu, B., Du, D.-Z. (eds.) COCOON 2011. LNCS, vol. 6842, pp. 62–73. Springer, Heidelberg (2011)
Kratochvíl, J.: Perfect codes in general graphs. Akademia Praha (1991)
Roberts, F.S.: Graph Theory and Its Applications to Problems of Society. SIAM (1987)
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
Jiang, M., Zhang, Y. (2012). Parameterized Complexity in Multiple-Interval Graphs: Domination. 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_3
Download citation
DOI: https://doi.org/10.1007/978-3-642-28050-4_3
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)