Editing to a planar graph of given degrees. (English) Zbl 1356.68096
Summary: We consider the following graph modification problem. Let the input consist of a graph \(G = (V, E)\), a weight function \(w : V \cup E \rightarrow \mathbb{N}\), a cost function \(c : V \cup E \rightarrow \mathbb{N}_0\) and a degree function \(\delta : V \rightarrow \mathbb{N}_0\), together with three integers \(k_v\), \(k_e\) and \(C\). The question is whether we can delete a set of vertices of total weight at most \(k_v\) and a set of edges of total weight at most \(k_e\) so that the total cost of the deleted elements is at most \(C\) and every non-deleted vertex \(v\) has degree \(\delta(v)\) in the resulting graph \(G^\prime\). We also consider the variant in which \(G^\prime\) must be connected. Both problems are known to be \(\mathsf{NP}\)-complete and \(\mathsf{W} [1]\)-hard when parameterized by \(k_v + k_e\). We prove that, when restricted to planar graphs, they stay \(\mathsf{NP}\)-complete but have polynomial kernels when parameterized by \(k_v + k_e\).
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 68R10 | Graph theory (including graph drawing) in computer science |
References:
| [1] | Belmonte, R.; Golovach, P. A.; van ’t Hof, P.; Paulusma, D., Parameterized complexity of three edge contraction problems with degree constraints, Acta Inform., 51, 7, 473-497 (2014) · Zbl 1360.68489 |
| [2] | Bodlaender, H. L.; Drange, P. G.; Dregi, M. S.; Fomin, F. V.; Lokshtanov, D.; Pilipczuk, M., A \(c^k n 5\)-approximation algorithm for treewidth, SIAM J. Comput., 45, 2, 317-378 (2016) · Zbl 1333.05282 |
| [3] | Bodlaender, H. L.; Fomin, F. V.; Lokshtanov, D.; Penninkx, E.; Saurabh, S.; Thilikos, D. M., (Meta) kernelization, J. ACM, 63, 5, Article 44 pp. (2016) · Zbl 1425.68137 |
| [4] | Boesch, F. T.; Suffel, C. L.; Tindell, R., The spanning subgraphs of Eulerian graphs, J. Graph Theory, 1, 1, 79-84 (1977) · Zbl 0363.05042 |
| [5] | Burzyn, P.; Bonomo, F.; Durán, G., NP-completeness results for edge modification problems, Discrete Appl. Math., 154, 13, 1824-1844 (2006) · Zbl 1110.68094 |
| [6] | Cai, L., Fixed-parameter tractability of graph modification problems for hereditary properties, Inf. Process. Lett., 58, 4, 171-176 (1996) · Zbl 0875.68702 |
| [7] | Cai, L.; Yang, B., Parameterized complexity of even/odd subgraph problems, J. Discret. Algorithms, 9, 3, 231-240 (2011) · Zbl 1225.05228 |
| [8] | Cygan, M.; Marx, D.; Pilipczuk, M.; Pilipczuk, M.; Schlotter, I., Parameterized complexity of Eulerian deletion problems, Algorithmica, 68, 1, 41-61 (2014) · Zbl 1284.05157 |
| [9] | Dabrowski, K. K.; Golovach, P. A.; van ’t Hof, P.; Paulusma, D., Editing to Eulerian graphs, J. Comput. Syst. Sci., 82, 2, 213-228 (2016) · Zbl 1346.05150 |
| [10] | Dabrowski, K. K.; Golovach, P. A.; van ’t Hof, P.; Paulusma, D.; Thilikos, D. M., Editing to a planar graph of given degrees, (CSR 2015. CSR 2015, Lecture Notes in Computer Science, vol. 9139 (2015), Springer), 143-156 · Zbl 1356.68095 |
| [11] | Downey, R. G.; Fellows, M. R., Fundamentals of Parameterized Complexity, Texts in Computer Science (2013), Springer · Zbl 1358.68006 |
| [12] | Flum, J.; Grohe, M., Parameterized Complexity Theory, Texts in Theoretical Computer Science. An EATCS Series (2006), Springer-Verlag: Springer-Verlag Berlin · Zbl 1143.68016 |
| [13] | Fomin, F. V.; Lokshtanov, D.; Saurabh, S.; Thilikos, D. M., Linear kernels for (connected) dominating set on \(H\)-minor-free graphs, (SODA 2012 (2012), SIAM), 82-93 · Zbl 1421.68078 |
| [14] | Froese, V.; Nichterlein, A.; Niedermeier, R., Win-win kernelization for degree sequence completion problems, J. Comput. Syst. Sci., 82, 6, 1100-1111 (2016) · Zbl 1345.68156 |
| [15] | Garey, M. R.; Johnson, D. S.; Tarjan, R. E., The planar hamiltonian circuit problem is NP-complete, SIAM J. Comput., 5, 4, 704-714 (1976) · Zbl 0346.05110 |
| [16] | Garnero, V.; Paul, C.; Sau, I.; Thilikos, D. M., Explicit linear kernels via dynamic programming, SIAM J. Discrete Math., 29, 4, 1864-1894 (2015) · Zbl 1323.05119 |
| [17] | Garnero, V.; Sau, I.; Thilikos, D. M., A linear kernel for planar red-blue dominating set, Discrete Appl. Math. (2016), in press · Zbl 1358.05217 |
| [18] | Golovach, P. A., Editing to a connected graph of given degrees, (MFCS 2014, Part II. MFCS 2014, Part II, Lecture Notes in Computer Science, vol. 8635 (2014), Springer), 324-335 · Zbl 1426.68122 |
| [19] | Golovach, P. A., Editing to a graph of given degrees, Theor. Comput. Sci., 591, 72-84 (2015) · Zbl 1322.68142 |
| [20] | Hopcroft, J. E.; Tarjan, R. E., Efficient planarity testing, J. ACM, 21, 4, 549-568 (1974) · Zbl 0307.68025 |
| [21] | Khot, S.; Raman, V., Parameterized complexity of finding subgraphs with hereditary properties, Theor. Comput. Sci., 289, 2, 997-1008 (2002) · Zbl 1061.68061 |
| [22] | Kim, E. J.; Langer, A.; Paul, C.; Reidl, F.; Rossmanith, P.; Sau, I.; Sikdar, S., Linear kernels and single-exponential algorithms via protrusion decompositions, ACM Trans. Algorithms, 12, 2, 21 (2016) · Zbl 1398.68245 |
| [23] | Kloks, T., Treewidth, Computations and Approximations, Lecture Notes in Computer Science, vol. 842 (1994), Springer · Zbl 0825.68144 |
| [24] | Lewis, J. M.; Yannakakis, M., The node-deletion problem for hereditary properties is NP-complete, J. Comput. Syst. Sci., 20, 2, 219-230 (1980) · Zbl 0436.68029 |
| [25] | Lovász, L.; Plummer, M. D., Matching Theory, Annals of Discrete Mathematics, vol. 29 (1986), Elsevier: Elsevier Oxford · Zbl 0618.05001 |
| [26] | Mathieson, L., Graph editing problems with extended regularity constraints (2015), CoRR · Zbl 1370.68137 |
| [27] | Mathieson, L.; Szeider, S., Editing graphs to satisfy degree constraints: a parameterized approach, J. Comput. Syst. Sci., 78, 1, 179-191 (2012) · Zbl 1242.68124 |
| [28] | Moser, H.; Thilikos, D. M., Parameterized complexity of finding regular induced subgraphs, J. Discret. Algorithms, 7, 2, 181-190 (2009) · Zbl 1187.68351 |
| [29] | Natanzon, A.; Shamir, R.; Sharan, R., Complexity classification of some edge modification problems, Discrete Appl. Math., 113, 1, 109-128 (2001) · Zbl 0982.68104 |
| [30] | Niedermeier, R., Invitation to Fixed-Parameter Algorithms, Oxford Lecture Series in Mathematics and Its Applications, vol. 31 (2006), Oxford University Press: Oxford University Press Oxford · Zbl 1095.68038 |
| [31] | Stewart, I. A., Deciding whether a planar graph has a cubic subgraph is NP-complete, Discrete Math., 126, 1-3, 349-357 (1994) · Zbl 0795.68150 |
| [32] | Tutte, W., A short proof of the factor theorem for finite graphs, Can. J. Math., 6, 347-359 (1954) · Zbl 0055.17102 |
| [33] | Yannakakis, M., Node- and edge-deletion NP-complete problems, (STOC 1978 (1978), ACM), 253-264 · Zbl 1282.68131 |
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.
