{"entities":{"Q1759874":{"pageid":1770616,"ns":120,"title":"Item:Q1759874","lastrevid":70841556,"modified":"2026-04-13T17:37:33Z","type":"item","id":"Q1759874","labels":{"en":{"language":"en","value":"Spanning cactus of a graph: Existence, extension, optimization, and approximation"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6109941"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1759874$BD765F87-4AD0-489F-9D39-F38FA4081B61","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"33da8f1b7b9db9bbf9d4601422362229fafe37bc","datavalue":{"value":{"text":"Spanning cactus of a graph: Existence, extension, optimization, and approximation","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1759874$7A5C7AF3-326A-42BF-9415-A9920EED670D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"03de3ba40afb53cdec8d7a6d64231a0f68c7669a","datavalue":{"value":"1258.05101","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1759874$D3CB032A-93C1-4437-A1D9-39505AE539D5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e220435c00b29aa44bd23746fb69b285a27bc9c1","datavalue":{"value":{"entity-type":"item","numeric-id":429678,"id":"Q429678"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1759874$47C9C191-4857-4B70-A370-50BE67FA17B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3145210ff03b7e6872f84577842c5a1fe41816db","datavalue":{"value":{"entity-type":"item","numeric-id":293329,"id":"Q293329"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1759874$8AC0E35F-D6B2-4D7F-BF49-C68EAE26CDB7","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1759874$E0D8EB5E-9B99-4001-9F25-8982DD996BC6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2f3aa46d2f66375aad8f9f235cf6aa2da570e73e","datavalue":{"value":{"time":"+2012-11-22T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1759874$9EA0D86B-D2B9-4E92-AAE4-B5F4E42842B1","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7b51f0f0731c451ba6adc72ce93b57d1eb337d69","datavalue":{"value":"A cactus is an undirected, connected graph in which each edge is contained in exactly one cycle. Equivalently, a cactus is a connected graph in which each block (maximal \\(2\\)-connected subgraph) is a cycle. The authors address the spanning cactus existence problem (SCEP) which asks if a given graph contains a spanning cactus, the optimization version of the SCEP, the minimum spanning cactus problem (MSCP), which asks for a spanning cactus \\(H\\) of minimum cost \\(\\sum_{e\\in E(H)} c_e\\) in a given graph \\(G\\) with non-negative edge-costs \\(c_e\\), \\(e\\in E(G)\\), and the minimum cactus extension problem (MCEP) which, given a graph \\(G\\) and a partial cactus (a spanning subgraph in which each edge is contained in at most one cycle), asks for an edge set \\(S\\subseteq E(G)\\setminus E(H)\\) such that \\(H+S\\) is a cactus and \\(\\sum_{e\\in S} c_e\\) is minimum. Among others, the authors prove that  {\\parindent=7mm \\begin{itemize}\\item[(1)]SCEP is NP-complete, and MSCP and MCEP are NP-hard on complete graphs with \\(0/1\\) edge-costs,  \\item[(2)]a spanning tree of a complete graph is extendable to a cactus if and only if it has at least one vertex of even degree.  \\end{itemize}} In general, partial cacti that are cactus-extendable are characterized in Theorem 5, {\\parindent=7mm \\begin{itemize}\\item[(3)] MCEP for spanning trees in complete graphs is solvable in strongly polynomial time.  \\end{itemize}} The authors also point out that in complete graphs with edge-costs satisfying the triangle inequality, MSCP and the traveling salesman problem are equivalent and have the same approximation hardness.      The directed version of MSCP and SCEP were previously discussed by \\textit{A. Palbom} [``Complexity of the directed spanning cactus problem,'' Discrete Appl. Math. 146, No. 1, 81--91 (2005; Zbl 1087.90081)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q1759874$B77F61B6-B4E3-4DE6-970B-FB27C75860DC","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c4d08f81dccf0def423a8aaa09abdd52c85c61ef","datavalue":{"value":{"entity-type":"item","numeric-id":185062,"id":"Q185062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1759874$61AF6AFB-52A7-4BAE-B3ED-471AEC53BE19","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1759874$EB56A99D-BF4F-4C39-B00D-FC9D1C6D36A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1759874$286FD2AD-EEE6-4EF4-9914-8A7CD9B3C971","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f75a34b7a75525d2f38738d1ca836db457ac616f","datavalue":{"value":"6109941","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1759874$AC1BE20E-0449-4DB0-80EB-DED477E015A9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c15fe6256b321c86a75b3c3c3d3b5e38691fb0dc","datavalue":{"value":"spanning cactus","type":"string"},"datatype":"string"},"type":"statement","id":"Q1759874$52D2FFFC-4CB5-48DA-BF26-E33B06571E91","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1759874$BBF195BB-38FE-40B9-B8B1-75FB3C650D41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc4837877785b4675d8ac1c6d4c911bcaf794e13","datavalue":{"value":"approximation algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1759874$1B31CAAE-6A68-493E-BA2D-447B041AE981","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b576abc0a66512603108cea0ec5ef5c7cd738b02","datavalue":{"value":"cactus extension","type":"string"},"datatype":"string"},"type":"statement","id":"Q1759874$CA4062BE-E9F4-44D9-A3DB-4FB256A91D43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8e7ad3a72d4c097630e99b699d68a3d20116b804","datavalue":{"value":"odd spanning tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1759874$4A694C42-2619-4CA3-A71B-57A90E372354","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"959dfea57d0e69124807f2be631cb584be6ccf7c","datavalue":{"value":"even spanning tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1759874$AED8CFA6-C9DC-4A5A-9265-EBF23F907CFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f01a4fda354e1cba3f1a86ec960a7ac96077c025","datavalue":{"value":"minimum spanning cactus problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1759874$1CCD191D-92AB-4A91-B852-436B37ECA216","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c0174c55c1cbe2d0e1bcf549bf6033271fd4e31d","datavalue":{"value":"maximum cactus extension problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1759874$C66858CC-01D5-4CB1-8AB5-37313CA3DAB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e89b4ccded6a9dfd41e679adb7266ebc2c319d06","datavalue":{"value":"edge-cost","type":"string"},"datatype":"string"},"type":"statement","id":"Q1759874$FD65B3D2-D67E-48A3-95C6-603EB3768622","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1759874$9D0B1B60-EF3E-43A6-B05E-E0A05A59DCA6","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"be8f2ce39c6a690494cb0f216c6183c74724ca53","datavalue":{"value":"https://doi.org/10.1016/j.dam.2012.08.006","type":"string"},"datatype":"url"},"type":"statement","id":"Q1759874$80BAE981-F0FF-4787-97DC-56611DF75BB0","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"6becc9cc4c78aca58d0f54774ca1b9e52dbc5d43","datavalue":{"value":"W2085596541","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1759874$5148475A-64F1-43B7-B9B6-587BBA71A8F0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3352d868524920c39b6ea13bb3a73f599c02f8e2","datavalue":{"value":"10.1016/J.DAM.2012.08.006","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1759874$6A2A9C95-18E1-4966-A0AE-1B085E68025D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"967c1da81b044a93373027b9fe8dded30f23288b","datavalue":{"value":{"entity-type":"item","numeric-id":2410246,"id":"Q2410246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"791580cb65fe5615d165250b006ce97c1e4cb7e1","datavalue":{"value":{"amount":"+0.90388703","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1759874$2FBDBB57-22D6-4A4B-BAC8-1C9AC9117005","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e972e9a35534ec86f2185cbea0c755d872ebdeea","datavalue":{"value":{"entity-type":"item","numeric-id":3539528,"id":"Q3539528"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fd0cced2a51ababb7efce0670b93a4a53dbafc6e","datavalue":{"value":{"amount":"+0.883595","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1759874$641BC8C4-EBF0-4049-B203-6E542762EF7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"afb6cae4789ff8175238a7db207e28aebf335b04","datavalue":{"value":{"entity-type":"item","numeric-id":4258252,"id":"Q4258252"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3bc02d32cc5929c47da56dc424b9cb7468771337","datavalue":{"value":{"amount":"+0.8771802","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1759874$A7F04266-82EE-4221-B27B-2397286D0173","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9f470ea6b15c6247eaa62175ce6f01d36d2f2c56","datavalue":{"value":{"entity-type":"item","numeric-id":277650,"id":"Q277650"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5b4c85b31e3626d71af5ecda6793c89178edca59","datavalue":{"value":{"amount":"+0.8737848","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1759874$7493D269-F3CF-4D39-8508-6FFC794070B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a5c7b318495872bc1a9a6fceca344631400b6631","datavalue":{"value":{"entity-type":"item","numeric-id":3514059,"id":"Q3514059"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"85e2b76450b85162d779acf166de3d795c73629d","datavalue":{"value":{"amount":"+0.8730874","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1759874$C8A411E0-284A-478C-87FD-13219EC869C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e4eb55793936bfcc4e3ff8738a55d3868c642744","datavalue":{"value":{"entity-type":"item","numeric-id":5261052,"id":"Q5261052"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d4a036859b2e674cb2b4cd9ac44f6d340aa4d067","datavalue":{"value":{"amount":"+0.87180305","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1759874$9EE11927-7034-49BA-9DCB-FE14BAFF1492","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"16a5dee4754c2c81bd470ed82764da0f969e8f4b","datavalue":{"value":{"entity-type":"item","numeric-id":1178689,"id":"Q1178689"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a6c6d9fda80e393195fb9e0084ffc8da06f8dfc9","datavalue":{"value":{"amount":"+0.86906636","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1759874$9B3A1823-31CC-4946-BF56-D93B828D0FCC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"66e79a3d02d92c7750dbfde94b6010fa287a1747","datavalue":{"value":{"entity-type":"item","numeric-id":5492649,"id":"Q5492649"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"990387d3d60ab44af03182587ebf970a0271de68","datavalue":{"value":{"amount":"+0.86817896","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1759874$AFB119D5-CE02-45BC-86B2-F51A00904619","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f2044534bf6f78cf5efdb3d25bedc37aa9fc8bb1","datavalue":{"value":{"entity-type":"item","numeric-id":1193532,"id":"Q1193532"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e0ad25875e6f3bbdeed32ad4b8be8b61f09b1943","datavalue":{"value":{"amount":"+0.8680138","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1759874$5D63624D-CA10-4FB3-AC63-745603B3E0B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b0ad09da9c681cf2f032e6b992750dfc395dcfa2","datavalue":{"value":{"entity-type":"item","numeric-id":5405926,"id":"Q5405926"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"622bea460fc9e6be81529c63891bbaa7830f8a15","datavalue":{"value":{"amount":"+0.8679132","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1759874$7D6E88DB-165E-471B-A2D0-78A867ECA592","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Spanning cactus of a graph: Existence, extension, optimization, and approximation","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Spanning_cactus_of_a_graph:_Existence,_extension,_optimization,_and_approximation"}}}}}