×
Drange, Pål Grønås; Fomin, Fedor V.; Pilipczuk, Michał; Villanger, Yngve

Exploring the subexponential complexity of completion problems. (English) Zbl 1347.68180

ACM Trans. Comput. Theory 7, No. 4, Article No. 14, 38 p. (2015).

Cited in 13 Documents

MSC:

68Q25 Analysis of algorithms and problem complexity
05C85 Graph algorithms (graph-theoretic aspects)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Keywords:

edge completion; modification; subexponential parameterized complexity

Citations:

Zbl 1285.68055; Zbl 1325.68108
Cite Review PDF
Full Text: DOI

References:

[1] Noga Alon, Daniel Lokshtanov, and Saket Saurabh. 2009. Fast fast. In Proceedings of the 36th Colloquium of Automata, Languages and Programming (ICALP). Lecture Notes in Computer Science, Vol. 5555. Springer, Berlin, 49–58. · Zbl 1248.68547 · doi:10.1007/978-3-642-02927-1_6
[2] Ivan Bliznets, Fedor V. Fomin, Marcin Pilipczuk, and Michał Pilipczuk. 2014a. A subexponential parameterized algorithm for interval completion. CoRR abs/1402.3473.
[3] Ivan Bliznets, Fedor V. Fomin, Marcin Pilipczuk, and Michał Pilipczuk. 2014b. A subexponential parameterized algorithm for proper interval completion. In Proceedings of the European Symposium on Algorithms (ESA). Lecture Notes in Computer Science, Vol. 8737. Springer, Berlin, 173–184. · Zbl 1330.68101 · doi:10.1007/978-3-662-44777-2_15
[4] Hans L. Bodlaender. 1998. A partialk-Arboretum of graphs with bounded treewidth. Theoretical Computer Science 209, 1–2, 1–45. · Zbl 0912.68148
[5] Andreas Brandstädt, Van Bang Le, and Jeremy P. Spinrad. 1999. Graph Classes. A Survey. SIAM, Philadelphia, PA. · Zbl 0919.05001 · doi:10.1137/1.9780898719796
[6] Pablo Burzyn, Flavia Bonomo, and Guillermo Durán. 2006. NP-Completeness results for edge modification problems. Discrete Applied Mathematics 154, 13, 1824–1844. · Zbl 1110.68094 · doi:10.1016/j.dam.2006.03.031
[7] Leizhen Cai. 1996. Fixed-parameter tractability of graph modification problems for hereditary properties. Information Processing Letters 58, 4, 171–176. · Zbl 0875.68702 · doi:10.1016/0020-0190(96)00050-6
[8] Leizhen Cai and Yufei Cai. 2015. Incompressibility ofH-Free edge modification problems. Algorithmica 71, 3, 731–757. · Zbl 1312.68096 · doi:10.1007/s00453-014-9937-x
[9] Erik D. Demaine, Fedor V. Fomin, Mohammadtaghi Hajiaghayi, and Dimitrios M. Thilikos. 2005. Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs. Journal of the ACM 52, 6, 866–893. · Zbl 1326.05152 · doi:10.1145/1101821.1101823
[10] Pål Grønås Drange, Fedor V. Fomin, Michał Pilipczuk, and Yngve Villanger. 2014. Exploring subexponential parameterized complexity of completion problems. In Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS) (LIPIcs), Vol. 25. Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik, 288–299.
[11] Pål Grønås Drange and Michał Pilipczuk. 2015. A polynomial kernel for trivially perfect editing. In European Symposium on Algorithms (ESA), N. Bansal and I. Finocchi (Eds.). LNCS 9294, Springer, Heidelberg, 424–436. · Zbl 1466.68045 · doi:10.1007/978-3-662-48350-3_36
[12] Jörg Flum and Martin Grohe. 2006. Parameterized Complexity Theory. Springer-Verlag, New York.
[13] Fedor V. Fomin, Stefan Kratsch, Marcin Pilipczuk, Michał Pilipczuk, and Yngve Villanger. 2014. Tight bounds for parameterized complexity of cluster editing with a small number of clusters. Journal of Computer and System Sciences 80, 7, 1430–1447. · Zbl 1311.68076 · doi:10.1016/j.jcss.2014.04.015
[14] Fedor V. Fomin and Yngve Villanger. 2013. Subexponential parameterized algorithm for minimum fill-in. SIAM Journal on Computing 42, 6, 2197–2216. · Zbl 1285.68055 · doi:10.1137/11085390X
[15] Esha Ghosh, Sudeshna Kolay, Mrinal Kumar, Pranabendu Misra, Fahad Panolan, Ashutosh Rai, and M. S. Ramanujan. 2015. Faster parameterized algorithms for deletion to split graphs. Algorithmica 71, 4, 989–1006. · Zbl 1325.68108 · doi:10.1007/s00453-013-9837-5
[16] Martin Charles Golumbic. 1980. Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York, NY. · Zbl 0541.05054
[17] Sylvain Guillemot, Frédéric Havet, Christophe Paul, and Anthony Perez. 2013. On the (non-)existence of polynomial kernels for Pl-free edge modification problems. Algorithmica 65, 4, 900–926. · Zbl 1262.68048 · doi:10.1007/s00453-012-9619-5
[18] Jiong Guo. 2007. Problem kernels for NP-complete edge deletion problems: Split and related graphs. In Algorithms and Computation, 18th International Symposium (ISAAC). Lecture Notes in Computer Science, Vol. 4835. Springer, Berlin, 915–926. · Zbl 1193.68194
[19] Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. 2001. Which problems have strongly exponential complexity? Journal of Computer and System Sciences 63, 4, 512–530. · Zbl 1006.68052 · doi:10.1006/jcss.2001.1774
[20] Yan Jing-Ho, Chen Jer-Jeong, and Gerard J. Chang. 1996. Quasi-threshold graphs. Discrete Applied Mathematics 69, 3, 247–255. · Zbl 0857.05082 · doi:10.1016/0166-218X(96)00094-7
[21] Haim Kaplan and Ron Shamir. 1996. Pathwidth, bandwidth, and completion problems to proper interval graphs with small cliques. SIAM Journal on Computing 25, 3, 540–561. · Zbl 0852.68072 · doi:10.1137/S0097539793258143
[22] Haim Kaplan, Ron Shamir, and Robert E. Tarjan. 1999. Tractability of parameterized completion problems on chordal, strongly chordal, and proper interval graphs. SIAM Journal on Computing 28, 5, 1906–1922. · Zbl 0928.68124 · doi:10.1137/S0097539796303044
[23] Christian Komusiewicz and Johannes Uhlmann. 2012. Cluster editing with locally bounded modifications. Discrete Applied Mathematics 160, 15, 2259–2270. · Zbl 1252.05178 · doi:10.1016/j.dam.2012.05.019
[24] Stefan Kratsch and Magnus Wahlström. 2013. Two edge modification problems without polynomial kernels. Discrete Optimization 10, 3, 193–199. · Zbl 1506.68040 · doi:10.1016/j.disopt.2013.02.001
[25] Frédéric Maffray and Myriam Preissmann. 1994. Linear recognition of pseudo-split graphs. Discrete Applied Mathematics 52, 3, 307–312. · Zbl 0805.05069 · doi:10.1016/0166-218X(94)00022-0
[26] Nadimpalli V. R. Mahadev and Uri N. Peled. 1995. Threshold Graphs and Related Topics. Annals of Discrete Mathematics, Vol. 56. Elsevier. · Zbl 0852.05001
[27] Federico Mancini. 2008. Graph Modification Problems Related to Graph Classes. Ph.D. Dissertation. University of Bergen, Bergen, Norway.
[28] Assaf Natanzon, Ron Shamir, and Roded Sharan. 2000. A polynomial approximation algorithm for the minimum fill-in problem. SIAM Journal on Computing 30, 1067–1079. Issue 4. · Zbl 0969.68194
[29] Jaroslav Nešetřil and Patrice Ossona de Mendez. 2012. Sparsity – Graphs, Structures, and Algorithms. Algorithms and combinatorics, Vol. 28. Springer.
[30] Yngve Villanger, Pinar Heggernes, Christophe Paul, and Jan Arne Telle. 2009. Interval completion is fixed parameter tractable. SIAM Journal on Computing 38, 5, 2007–2020. · Zbl 1227.05241 · doi:10.1137/070710913
[31] Mihalis Yannakakis. 1981a. Computing the minimum fill-in is NP-complete. SIAM Journal on Algebraic Discrete Methods 2, 1, 77–79. · Zbl 0496.68033 · doi:10.1137/0602010
[32] Mihalis Yannakakis. 1981b. Edge-deletion problems. SIAM Journal on Computing 10, 2, 297–309. · Zbl 0468.05043 · doi:10.1137/0210021
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.