乐胖代购免代理版

{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,5,23]],"date-time":"2024-05-23T00:20:59Z","timestamp":1716423659526},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2024,3,6]],"date-time":"2024-03-06T00:00:00Z","timestamp":1709683200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,3,6]],"date-time":"2024-03-06T00:00:00Z","timestamp":1709683200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Helmholtz-Zentrum f\u00fcr Informationssicherheit \u2013 CISPA gGmbH"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2024,6]]},"abstract":"Abstract<\/jats:title>Can we efficiently compute optimal solutions to instances of a hard problem from optimal solutions to neighbor instances, that is, instances with one local modification? For example, can we efficiently compute an optimal coloring for a graph from optimal colorings for all one-edge-deleted subgraphs? Studying such questions not only gives detailed insight into the structure of the problem itself, but also into the complexity of related problems, most notably, graph theory\u2019s core notion of critical graphs (e.g., graphs whose chromatic number decreases under deletion of an arbitrary edge) and the complexity-theoretic notion of minimality problems (also called criticality problems, e.g., recognizing graphs that become 3-colorable when an arbitrary edge is deleted). We focus on two prototypical graph problems, colorability and vertex cover. For example, we show that it is

$$\\text {NP}$$<\/jats:tex-math>\n NP<\/mml:mtext>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-hard to compute an optimal coloring for a graph from optimal colorings for all<\/jats:italic> its one-vertex-deleted subgraphs, and that this remains true even when optimal solutions for all<\/jats:italic> one-edge-deleted subgraphs are given. In contrast, computing an optimal coloring from all (or even just two) one-edge-added supergraphs is in

$$\\text {P}$$<\/jats:tex-math>\n P<\/mml:mtext>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. We observe that vertex cover exhibits a remarkably different behavior, demonstrating the power of our model to delineate problems from each other more precisely on a structural level. Moreover, we provide a number of new complexity results for minimality and criticality problems. For example, we prove that Minimal<\/jats:sc>-3-UnColorability<\/jats:sc> is complete for

$$\\text {DP}$$<\/jats:tex-math>\n DP<\/mml:mtext>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> (differences of

$$\\text {NP}$$<\/jats:tex-math>\n NP<\/mml:mtext>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> sets), which was previously known only for the more amenable case of deleting vertices rather than edges. For vertex cover, we show that recognizing

$$\\beta $$<\/jats:tex-math>\n \u03b2<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-vertex-critical graphs is complete for\u00a0

$$\\Theta _2^\\text {p}$$<\/jats:tex-math>\n \n \u0398<\/mml:mi>\n 2<\/mml:mn>\n p<\/mml:mtext>\n <\/mml:msubsup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> (parallel access to

$$\\text {NP}$$<\/jats:tex-math>\n NP<\/mml:mtext>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>), obtaining the first completeness result for a criticality problem for this class.<\/jats:p>","DOI":"10.1007\/s00453-023-01204-1","type":"journal-article","created":{"date-parts":[[2024,3,6]],"date-time":"2024-03-06T14:02:52Z","timestamp":1709733772000},"page":"1921-1947","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Finding Optimal Solutions with Neighborly Help"],"prefix":"10.1007","volume":"86","author":[{"given":"Elisabet","family":"Burjons","sequence":"first","affiliation":[]},{"given":"Fabian","family":"Frei","sequence":"additional","affiliation":[]},{"given":"Edith","family":"Hemaspaandra","sequence":"additional","affiliation":[]},{"given":"Dennis","family":"Komm","sequence":"additional","affiliation":[]},{"given":"David","family":"Wehner","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,3,6]]},"reference":[{"issue":"1","key":"1204_CR1","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1112\/plms\/s3-2.1.69","volume":"s3\u20132","author":"GA Dirac","year":"1952","unstructured":"Dirac, G.A.: Some theorems on abstract graphs. Proc. Lond. Math. Soc. s3\u20132(1), 69\u201381 (1952)","journal-title":"Proc. Lond. Math. Soc."},{"key":"1204_CR2","series-title":"Colloquia Mathematica Societatis Janos Bolyai","first-page":"829","volume-title":"Finite and Infinite Sets (6th Hungarian Combinatorial Colloquium, Eger, 1981)","author":"W Wessel","year":"1984","unstructured":"Wessel, W.: Criticity with respect to properties and operations in graph theory. In: Andr\u00e1s Hajnal, L.L., S\u00f3s, V.T. (eds.) Finite and Infinite Sets (6th Hungarian Combinatorial Colloquium, Eger, 1981). Colloquia Mathematica Societatis Janos Bolyai, vol. 2, pp. 829\u2013837. North-Holland, Amsterdam (1984)"},{"issue":"1","key":"1204_CR3","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/0022-0000(88)90042-6","volume":"37","author":"CH Papadimitriou","year":"1988","unstructured":"Papadimitriou, C.H., Wolfe, D.: The complexity of facets resolved. J. Comput. Syst. Sci. 37(1), 2\u201313 (1988)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"1204_CR4","doi-asserted-by":"publisher","first-page":"222","DOI":"10.1007\/s00224-008-9127-9","volume":"46","author":"P Faliszewski","year":"2010","unstructured":"Faliszewski, P., Ogihara, M.: On the autoreducibility of functions. Theory Comput. Syst. 46(2), 222\u2013245 (2010)","journal-title":"Theory Comput. Syst."},{"key":"1204_CR5","unstructured":"Schnorr, C.-P.: Optimal algorithms for self-reducible problems. In: Proceedings of the 3rd International Colloquium on Automata, Languages, and Programming (ICALP 1976), pp. 322\u2013337. Edinburgh University Press, Edinburgh (1976)"},{"key":"1204_CR6","unstructured":"Meyer, A.R., Paterson, M.: With what frequency are apparently intractable problems difficult? Technical Report MIT\/LCS\/TM-126, Laboratory for Computer Science, MIT, Cambridge (1979)"},{"issue":"1\u20132","key":"1204_CR7","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/S0166-218X(96)00042-X","volume":"72","author":"MW Sch\u00e4ffter","year":"1997","unstructured":"Sch\u00e4ffter, M.W.: Scheduling with forbidden sets. Discrete Appl. Math. 72(1\u20132), 155\u2013166 (1997)","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"1204_CR8","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1002\/net.10091","volume":"42","author":"C Archetti","year":"2003","unstructured":"Archetti, C., Bertazzi, L., Speranza, M.G.: Reoptimizing the traveling salesman problem. Networks 42(3), 154\u2013159 (2003)","journal-title":"Networks"},{"key":"1204_CR9","doi-asserted-by":"crossref","unstructured":"B\u00f6ckenhauer, H.-J., Forlizzi, L., Hromkovi\u010d, J., Kneis, J., Kupke, J., Proietti, G., Widmayer, P.: Reusing optimal TSP solutions for locally modified input instances. In: Proceedings of the 4th IFIP International Conference on Theoretical Computer Science (FIP TCS\u00a02006), pp. 251\u2013270. Springer, Berlin (2006)","DOI":"10.1007\/978-0-387-34735-6_21"},{"key":"1204_CR10","doi-asserted-by":"crossref","unstructured":"Ausiello, G., Escoffier, B., Monnot, J., Paschos, V.: Reoptimization of minimum and maximum traveling salesman\u2019s tours. In: Proceedings of the 10th Scandinavian Workshop on Algorithm Theory (SWAT\u00a02006). Lecture Notes in Computer Science, vol. 4059, pp. 196\u2013207. Springer, Berlin (2006)","DOI":"10.1007\/11785293_20"},{"key":"1204_CR11","first-page":"427","volume-title":"AAM Handbook of Approximation Algorithms and Metaheuristics","author":"H-J B\u00f6ckenhauer","year":"2018","unstructured":"B\u00f6ckenhauer, H.-J., Hromkovi\u010d, J., Komm, D.: Reoptimization of hard optimization problems. In: Gonzalez, T.F. (ed.) AAM Handbook of Approximation Algorithms and Metaheuristics, vol. 1, 2nd edn., pp. 427\u2013454. CRC Press, London (2018) . (Chap. 25)","edition":"2nd edn."},{"issue":"5","key":"1204_CR12","doi-asserted-by":"publisher","first-page":"833","DOI":"10.1137\/0219058","volume":"19","author":"KW Wagner","year":"1990","unstructured":"Wagner, K.W.: Bounded query classes. SIAM J. Comput. 19(5), 833\u2013846 (1990)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"1204_CR13","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1137\/0216022","volume":"16","author":"J-Y Cai","year":"1987","unstructured":"Cai, J.-Y., Meyer, G.E.: Graph minimal uncolorability is $${\\rm D}^P$$-complete. SIAM J. Comput. 16(2), 259\u2013277 (1987)","journal-title":"SIAM J. Comput."},{"key":"1204_CR14","unstructured":"Joret, G.: Entropy and stability in graphs. PhD thesis, Universit\u00e9 Libre de Bruxelles, Facult\u00e9 des Sciences (2008)"},{"key":"1204_CR15","series-title":"Leibniz International Proceedings in Informatics (LIPIcs)","first-page":"19","volume-title":"31st International Symposium on Algorithms and Computation (ISAAC 2020)","author":"F Frei","year":"2020","unstructured":"Frei, F., Hemaspaandra, E., Rothe, J.: Complexity of stability. In: Cao, Y., Cheng, S.-W., Li, M. (eds.) 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), vol. 181, pp. 19\u201311914. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl (2020)"},{"key":"1204_CR16","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/j.jcss.2021.07.001","volume":"123","author":"F Frei","year":"2022","unstructured":"Frei, F., Hemaspaandra, E., Rothe, J.: Complexity of stability. J. Comput. Syst. Sci. 123, 103\u2013121 (2022)","journal-title":"J. Comput. Syst. Sci."},{"key":"1204_CR17","first-page":"339","volume-title":"Handbook of Satisfiability 2009","author":"HK B\u00fcning","year":"2009","unstructured":"B\u00fcning, H.K., Kullmann, O.: Minimal unsatisfiability and autarkies. In: Biere, A., Heule, M., van Maaren, H., Walsh, T. (eds.) Handbook of Satisfiability 2009, pp. 339\u2013401. IOS Press, Amsterdam (2009)"},{"issue":"5","key":"1204_CR18","first-page":"551","volume":"12","author":"J Rothe","year":"2006","unstructured":"Rothe, J., Riege, T.: Completeness in the Boolean Hierarchy. J. Univ. Comput. Sci. 12(5), 551\u2013578 (2006)","journal-title":"J. Univ. Comput. Sci."},{"key":"1204_CR19","doi-asserted-by":"publisher","DOI":"10.21236\/AD0705364","volume-title":"Graph Theory","author":"F Harary","year":"1969","unstructured":"Harary, F.: Graph Theory. Addison-Wesley, New York (1969)"},{"key":"1204_CR20","doi-asserted-by":"crossref","unstructured":"B\u00f6ckenhauer, H.-J., Hromkovi\u010d, J., M\u00f6mke, T., Widmayer, P.: On the hardness of reoptimization. In: Proceedings of the 34th Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM\u00a02008). Lecture Notes in Computer Science, vol. 4910, pp. 50\u201365. Springer, Berlin (2008)","DOI":"10.1007\/978-3-540-77566-9_5"},{"key":"1204_CR21","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M Garey","year":"1979","unstructured":"Garey, M., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York (1979)"},{"issue":"3","key":"1204_CR22","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1016\/j.tcs.2005.08.031","volume":"349","author":"E Hemaspaandra","year":"2005","unstructured":"Hemaspaandra, E., Spakowski, H., Vogel, J.: The complexity of Kemeny elections. Theoret. Comput. Sci. 349(3), 382\u2013391 (2005)","journal-title":"Theoret. Comput. Sci."},{"issue":"1\u20132","key":"1204_CR23","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0304-3975(87)90049-1","volume":"51","author":"KW Wagner","year":"1987","unstructured":"Wagner, K.W.: More complicated questions about maxima and minima, and some closures of NP. Theoret. Comput. Sci. 51(1\u20132), 53\u201380 (1987)","journal-title":"Theoret. Comput. Sci."},{"key":"1204_CR24","unstructured":"Burjons, E., Frei, F., Hemaspaandra, E., Komm, D., Wehner, D.: Finding optimal solutions with Neighborly Help. In: Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), vol. 138, pp. 78\u201317814. Schloss Dagstuhl, Dagstuhl (2019)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01204-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-023-01204-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01204-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,22]],"date-time":"2024-05-22T07:03:28Z","timestamp":1716361408000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-023-01204-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,6]]},"references-count":24,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2024,6]]}},"alternative-id":["1204"],"URL":"https:\/\/doi.org\/10.1007\/s00453-023-01204-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3,6]]},"assertion":[{"value":"20 December 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 December 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 March 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}