On the threshold of intractability. (English) Zbl 1478.68104
Summary: The computational complexity of the graph modification problems Threshold Editing and Chain Editing has been an important open question in computational graph theory for more than 15 years. These problems consist of adding and deleting the fewest possible edges to transform a graph into a threshold or chain graph. We show that both problems are NP-hard, resolving a conjecture by A. Natanzon et al. [Discrete Appl. Math. 113, No. 1, 109–128 (2001; Zbl 0982.68104)]. On the positive side, we show both problems admit quadratic vertex kernels and give subexponential time parameterized algorithms solving both problems in \(2^{O(\sqrt{k}\log k)}+n^{O(1)}\) time. Few natural problems are known to be in this complexity class. These results also extend to the completion and deletion variants of both problems, and threshold/chain graphs are the only known graph classes for which all three versions – completion, deletion, and editing – are both NP-complete and solvable in subexponential parameterized time.
MSC:
| 68Q27 | Parameterized complexity, tractability and kernelization |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 68R10 | Graph theory (including graph drawing) in computer science |
Citations:
Zbl 0982.68104References:
| [1] | Alon, N.; Lokshtanov, D.; Saurabh, S., Fast FAST, (ICALP. ICALP, Lecture Notes in Computer Science, vol. 5555 (2009), Springer), 49-58 · Zbl 1248.68547 |
| [2] | Brandes, U., Social network algorithmics, (ISAAC (2014)) |
| [3] | Brandstädt, A.; Le, V. B.; Spinrad, J. P., Graph Classes. A Survey, SIAM Monographs on Discrete Mathematics and Applications (1999), SIAM: SIAM Philadelphia, USA · Zbl 0919.05001 |
| [4] | 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 |
| [5] | Cai, L., Fixed-parameter tractability of graph modification problems for hereditary properties, Inf. Process. Lett., 58, 4, 171-176 (1996) · Zbl 0875.68702 |
| [6] | Cao, Y.; Marx, D., Chordal editing is fixed-parameter tractable, (STACS. STACS, LIPIcs, vol. 25 (2014), Schloss Dagstuhl), 214-225 · Zbl 1359.05119 |
| [7] | Chen, Z.-Z.; Jiang, T.; Lin, G., Computing phylogenetic roots with bounded degrees and errors, SIAM J. Comput., 32, 4, 864-879 (2003) · Zbl 1053.68069 |
| [8] | Damaschke, P., Parameterized enumeration, transversals, and imperfect phylogeny reconstruction, Theor. Comput. Sci., 351, 3, 337-350 (2006) · Zbl 1087.68067 |
| [9] | Dehne, F.; Langston, M. A.; Luo, X.; Pitre, S.; Shaw, P.; Zhang, Y., The cluster editing problem: implementations and experiments, (Parameterized and Exact Computation (2006), Springer), 13-24 · Zbl 1154.68451 |
| [10] | Drange, P. G.; Dregi, M. S.; Lokshtanov, D.; Sullivan, B. D., On the threshold of intractability, (ESA. ESA, Lecture Notes in Computer Science, vol. 9294 (2015), Springer), 411-423 · Zbl 1466.68042 |
| [11] | Drange, P. G.; Fomin, F. V.; Pilipczuk, M.; Villanger, Y., Exploring the subexponential complexity of completion problems, ACM Trans. Comput. Theory, 7, 4, Article 14 pp. (2015) · Zbl 1347.68180 |
| [12] | Drange, P. G.; Pilipczuk, M., A polynomial kernel for trivially perfect editing, Algorithmica, 80, 12, 3481-3524 (2018) · Zbl 1397.05070 |
| [13] | Feder, T.; Mannila, H.; Terzi, E., Approximating the minimum chain completion problem, Inf. Process. Lett., 109, 17, 980-985 (2009) · Zbl 1202.68483 |
| [14] | Flum, J.; Grohe, M., Parameterized Complexity Theory (2006), Springer-Verlag New York Inc. · Zbl 1143.68016 |
| [15] | Fomin, F. V.; Villanger, Y., Subexponential parameterized algorithm for minimum fill-in, SIAM J. Comput., 42, 6, 2197-2216 (2013) · Zbl 1285.68055 |
| [16] | Ghosh, E.; Kolay, S.; Kumar, M.; Misra, P.; Panolan, F.; Rai, A.; Ramanujan, M. S., Faster parameterized algorithms for deletion to split graphs, Algorithmica, 71, 4, 989-1006 (2015) · Zbl 1325.68108 |
| [17] | Golumbic, M. C., Algorithmic Graph Theory and Perfect Graphs, vol. 57 (2004), Elsevier · Zbl 1050.05002 |
| [18] | Guo, J., Problem kernels for NP-complete edge deletion problems: split and related graphs, (ISAAC. ISAAC, Lecture Notes in Computer Science, vol. 4835 (2007), Springer), 915-926 · Zbl 1193.68194 |
| [19] | Hammer, P. L.; Simeone, B., The splittance of a graph, Combinatorica, 1, 3, 275-284 (1981) · Zbl 0492.05043 |
| [20] | Liu, Y.; Wang, J.; Guo, J., An overview of kernelization algorithms for graph modification problems, Tsinghua Sci. Technol., 19, 4, 346-357 (2014) |
| [21] | Liu, Y.; Wang, J.; Guo, J.; Chen, J., Complexity and parameterized algorithms for cograph editing, Theor. Comput. Sci., 461, 45-54 (2012) · Zbl 1253.68179 |
| [22] | Liu, Y.; Wang, J.; You, J.; Chen, J.; Cao, Y., Edge deletion problems: branching facilitated by modular decomposition, Theor. Comput. Sci., 573, 63-70 (2015) · Zbl 1318.68128 |
| [23] | Mahadev, N.; Peled, U., Threshold Graphs and Related Topics, vol. 56 (1995), North Holland · Zbl 0852.05001 |
| [24] | Mancini, F., Graph modification problems related to graph classes (2008), University of Bergen, PhD thesis |
| [25] | Masuda, N.; Miwa, H.; Konno, N., Analysis of scale-free networks based on a threshold graph with intrinsic vertex weights, Phys. Rev. E, 70, 3, Article 036124 pp. (2004) |
| [26] | Nastos, J.; Gao, Y., Familial groups in social networks, Soc. Netw., 35, 3, 439-450 (2013) |
| [27] | Natanzon, A., Complexity and approximation of some graph modification problems (1999), Tel Aviv University, PhD thesis |
| [28] | Natanzon, A.; Shamir, R.; Sharan, R., Complexity classification of some edge modification problems, Discrete Appl. Math., 113, 1, 109-128 (2001) · Zbl 0982.68104 |
| [29] | Nocaj, A.; Ortmann, M.; Brandes, U., Untangling the hairballs of multi-centered, small-world online social media networks, J. Graph Algorithms Appl., 19, 2, 595-618 (2015) · Zbl 1328.05176 |
| [30] | Schoch, D.; Brandes, U., Stars, neighborhood inclusion, and network centrality, (SIAM Workshop on Network Science (2015)) |
| [31] | Shamir, R.; Sharan, R.; Tsur, D., Cluster graph modification problems, Discrete Appl. Math., 144, 1-2, 173-182 (2004) · Zbl 1068.68107 |
| [32] | Sharan, R., Graph modification problems and their applications to genomic research (2002), Tel-Aviv University, PhD thesis |
| [33] | Yannakakis, M., Computing the minimum fill-in is NP-complete, SIAM J. Algebraic Discrete Methods, 2, 1, 77-79 (1981) · Zbl 0496.68033 |
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.
