Graph editing to a given neighbourhood degree list is fixed-parameter tractable. (English) Zbl 1474.05373
Gao, Xiaofeng (ed.) et al., Combinatorial optimization and applications. 11th international conference, COCOA 2017, Shanghai, China, December 16–18, 2017. Proceedings. Part II. Cham: Springer. Lect. Notes Comput. Sci. 10628, 138-153 (2017).
Summary: Graph editing problems ask whether an input graph can be modified to a graph with a given property by inserting and deleting vertices and edges. We consider the problem Graph Edit to NDL, which asks whether a graph can be modified to a graph with a given neighbourhood degree list (NDL) using at most \(\ell\) graph edits. The NDL lists the degrees of the neighbours of vertices in a graph, and is a stronger invariant than the degree sequence, which lists the degrees of vertices. In fact, the degree sequence of a graph is determined by its NDL. {
}We show that Graph Edit to NDL is W[1]-hard when parameterized by \(\ell\) and give an algorithm that runs in fixed-parameter time when parameterized by \(\varDelta+\ell\), where \(\varDelta\) is the maximum degree of the input graph. Furthermore, we adapt our algorithm to solve a harder problem, Constrained Graph Edit to NDL, which imposes constraints on the NDLs of the intermediate graphs produced in the sequence, in fixed-parameter time when parameterized by \(\varDelta+\ell\).{
}Moreover, there exist graph measures such as assortativity and average nearest neighbour degree that can be derived from the NDL, but not the degree sequence. Our algorithm can be adapted to solve the problem of editing to a graph with a given value of such a measure.
For the entire collection see [Zbl 1378.68013].
For the entire collection see [Zbl 1378.68013].
MSC:
| 05C85 | Graph algorithms (graph-theoretic aspects) |
References:
| [1] | Barrus, M.D., Donovan, E.: Neighborhood degree lists of graphs. arXiv preprint. arXiv:1507.08212 (2015) |
| [2] | Bazgan, C.; Nichterlein, A.; Cygan, M.; Heggernes, P., Parameterized inapproximability of degree anonymization, Parameterized and Exact Computation, 75-84, 2014, Cham: Springer, Cham · Zbl 1456.68062 |
| [3] | Casas-Roma, J.; Herrera-Joancomartí, J.; Torra, V.; Navarro-Arribas, G.; Torra, V., A summary of k-degree anonymous methods for privacy-preserving on networks, Advanced Research in Data Privacy, 231-250, 2015, Cham: Springer, Cham |
| [4] | Diestel, R., Graph Theory, 2005, Heidelberg: Springer, Heidelberg · Zbl 1074.05001 |
| [5] | Downey, RG; Fellows, MR, Fundamentals of Parameterized Complexity, 2013, London: Springer, London · Zbl 1358.68006 · doi:10.1007/978-1-4471-5559-1 |
| [6] | Eppstein, D., Diameter and treewidth in minor-closed graph families, Algorithmica, 27, 3-4, 275-291, 1999 · Zbl 0963.05128 |
| [7] | Ferrara, M., Some problems on graphic sequences, Graph Theor. Notes New York, 64, 19-25, 2013 |
| [8] | Frick, M.; Grohe, M., Deciding first-order properties of locally tree-decomposable structures, J. ACM, 48, 6, 1184-1206, 2001 · Zbl 1323.03014 · doi:10.1145/504794.504798 |
| [9] | Goldberg, PW; Golumbic, MC; Kaplan, H.; Shamir, R., Four strikes against physical mapping of DNA, J. Comput. Biol., 2, 1, 139-152, 1995 · doi:10.1089/cmb.1995.2.139 |
| [10] | Golovach, PA; Mertzios, GB; Kulikov, AS; Woeginger, GJ, Graph editing to a given degree sequence, Computer Science - Theory and Applications, 177-191, 2016, Cham: Springer, Cham · Zbl 1475.68139 |
| [11] | Harary, F.; Bari, RA; Harary, F., A survey of the reconstruction conjecture, Graphs and Combinatorics, 18-28, 1974, Heidelberg: Springer, Heidelberg · Zbl 0293.05152 · doi:10.1007/BFb0066431 |
| [12] | van den Heuvel, J., The complexity of change, Surv. Comb., 409, 127-160, 2013 · Zbl 1307.05005 |
| [13] | Kelly, PJ, A congruence theorem for trees, Pac. J. Math., 7, 1, 961-968, 1957 · Zbl 0078.37103 · doi:10.2140/pjm.1957.7.961 |
| [14] | Mathieson, L., Szeider, S.: The parameterized complexity of regular subgraph problems and generalizations. In: Proceedings of the Fourteenth Symposium on Computing: The Australasian Theory, vol. 77, pp. 79-86. Australian Computer Society, Inc. (2008) |
| [15] | 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 · doi:10.1016/j.jcss.2011.02.001 |
| [16] | Moser, H.; Thilikos, DM, Parameterized complexity of finding regular induced subgraphs, J. Discrete Algorithms, 7, 2, 181-190, 2009 · Zbl 1187.68351 · doi:10.1016/j.jda.2008.09.005 |
| [17] | Newman, MEJ, Assortative mixing in networks, Phys. Rev. Lett., 89, 20, 208701, 2002 · doi:10.1103/PhysRevLett.89.208701 |
| [18] | Pastor-Satorras, R.; Vázquez, A.; Vespignani, A., Dynamical and correlation properties of the internet, Phys. Rev. Lett., 87, 25, 258701-1-258701-4, 2001 · doi:10.1103/PhysRevLett.87.258701 |
| [19] | Plesník, J., A note on the complexity of finding regular subgraphs, Discrete Math., 49, 2, 161-167, 1984 · Zbl 0567.05029 · doi:10.1016/0012-365X(84)90113-4 |
| [20] | Stewart, IA, Finding regular subgraphs in both arbitrary and planar graphs, Discrete Appl. Math., 68, 3, 223-235, 1996 · Zbl 0855.68071 · doi:10.1016/0166-218X(95)00061-U |
| [21] | Ulam, SM, A Collection of Mathematical Problems, 1960, New York: Interscience Publishers, New York · Zbl 0086.24101 |
| [22] | Young, A., On quantitative substitutional analysis, Proc. Lond. Math. Soc., 2, 1, 196-230, 1932 · Zbl 0005.09704 · doi:10.1112/plms/s2-34.1.196 |
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.
