{"entities":{"Q1736537":{"pageid":1747278,"ns":120,"title":"Item:Q1736537","lastrevid":72377502,"modified":"2026-04-14T04:29:51Z","type":"item","id":"Q1736537","labels":{"en":{"language":"en","value":"Maximum disjoint paths on edge-colored graphs: approximability and tractability"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7042147"}},"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":"Q1736537$8CBC9E17-8A7F-4A63-85FB-B6BFA07E6DBA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7b78cec8373ea673be80fe5660bee6b32d3042c0","datavalue":{"value":{"text":"Maximum disjoint paths on edge-colored graphs: approximability and tractability","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1736537$E095EF63-7020-4619-B18E-335606D30DB5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0c932b6b2db7cffc78e596ce2b29eefddb505456","datavalue":{"value":"1461.68144","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736537$F2A1232B-1AA4-4A12-BD38-63FEA5C197AF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a12141a30b62e30eb0fdbf8f3a0b0c8897ffbef3","datavalue":{"value":{"entity-type":"item","numeric-id":243591,"id":"Q243591"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736537$660B2D41-FF3E-4A6F-9B8D-7144C3CE566D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"bcfaf5505fae0d5445807a2568aded0d4a7b3d8a","datavalue":{"value":{"entity-type":"item","numeric-id":243593,"id":"Q243593"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736537$A3533E61-6E1F-43BF-A572-E1F65EE86804","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"663f3ecf25a95889dc029b7d32c527217e0e7fe5","datavalue":{"value":{"entity-type":"item","numeric-id":243835,"id":"Q243835"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736537$61D51910-636B-4F24-AFE2-A8A544A2E628","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"18e3aed7ec2baba1bc6b2c08988b16bb9ac0e77f","datavalue":{"value":{"entity-type":"item","numeric-id":82263,"id":"Q82263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736537$8ABA31A1-DB5E-4919-BFFF-B77A2A4C25C9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d660e31d569d3203bec6d5e897b7f6ed7f6a3a72","datavalue":{"value":{"time":"+2019-03-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1736537$6E82545B-9F34-40C3-A8AF-74D7B5201FCA","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"fb60b0477c7e11df4fc84bcf94c5c4492e013f1f","datavalue":{"value":"Summary: The problem of finding the maximum number of vertex-disjoint uni-color paths in an edge-colored graph has been recently introduced in literature, motivated by applications in social network analysis. In this paper we investigate the approximation and parameterized complexity of the problem. First, we show that, for any constant \\(\\varepsilon >0\\), the problem is not approximable within factor \\(c^{1-\\varepsilon}\\), where \\(c\\) is the number of colors, and that the corresponding decision problem is W[1]-hard when parametrized by the number of disjoint paths. Then, we present a fixed-parameter algorithm for the problem parameterized by the number and the length of the disjoint paths.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736537$41130637-3954-436E-8D5D-FFA4919A2CF2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736537$B192221B-C07F-4961-BF7E-EB9896B887B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736537$14257DBC-C9E9-4EA1-AED7-9991DD01945B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736537$4DBDB034-B439-436A-85AC-2E07C3A0F0D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736537$10FF3B91-440E-4048-AFF1-AC568E274BE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736537$6D16B88F-808E-4A3B-B662-72B7D251BB6D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ca84c0a1de3e8c9074706ad5adbc0b1d28c30279","datavalue":{"value":"68Q27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736537$F4AC5F83-FC5F-4352-9480-156FEC07BAC3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6818f07a9933dfaf85292145e3cc8b51abba4a95","datavalue":{"value":"7042147","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736537$897651BE-1E15-4779-84A1-0126740CBA3B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"28a4b44179c8ba7be77e50b39fa5f88351bfdd89","datavalue":{"value":"social networks","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736537$C21372D2-63A3-4C94-AC73-00891CF44836","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a8415b13e13866b2a902e773eb49890a053b3a53","datavalue":{"value":"disjoint paths","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736537$B422D8FA-76CE-4818-84EC-9C9A6BE4A77C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cdd31bd27a7952322bda50b6d3d83e798c57764d","datavalue":{"value":"fixed-parameter algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736537$9D79F0D1-90E7-466A-A2CA-FB0C63402994","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c932864c8d857b058190f9c7572ffef7f1e96210","datavalue":{"value":"hardness of approximation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736537$DF4BACC9-83B1-4303-AE17-DE8D68103782","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":"Q1736537$E4D9AB3C-499D-46AE-A5B6-9CCDC17E80B0","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9468c562ee806b267df737bbd7e134f089534739","datavalue":{"value":"https://doi.org/10.3390/a6010001","type":"string"},"datatype":"url"},"type":"statement","id":"Q1736537$73C2F920-AC30-4087-8A51-BE775E28F616","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a72d8929bc5afe4ec50af29dde808985d728127f","datavalue":{"value":"W2142971798","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736537$2EC4E2FA-6076-4F9A-B52D-FA1E9204E694","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"003bc6c20bd1d8ced7d2a1dc42f1b9c84a55618d","datavalue":{"value":{"entity-type":"item","numeric-id":4397004,"id":"Q4397004"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736537$41FAD7B0-F08B-4FAB-AAB9-C7754CC7C92B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a96e76139df01186cd89e2d05fcaf80e65c1a682","datavalue":{"value":{"entity-type":"item","numeric-id":435732,"id":"Q435732"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736537$F2693F3B-3DA8-48C1-B38F-C0B1AA369603","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5aa2a1ac4e864d41c30b8a828a68a91d18d8ecae","datavalue":{"value":{"entity-type":"item","numeric-id":4258216,"id":"Q4258216"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736537$9B1ED230-04A3-4266-9F92-29D2EE7E296D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7eb66b87688bc2ff814b7b9b7a7d0a2a04333d71","datavalue":{"value":{"entity-type":"item","numeric-id":2931428,"id":"Q2931428"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736537$71040BEC-64E8-4DBC-9EC5-3E2FD0EB6B48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e1357b15aa0895d858d392a7ff419092326aafa","datavalue":{"value":{"entity-type":"item","numeric-id":5710169,"id":"Q5710169"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736537$CCB30418-FEAB-404F-AA7F-82F6B1061E52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"500bfeba9231a071c9bfde5b167ca0a56cfc8d2f","datavalue":{"value":{"entity-type":"item","numeric-id":673779,"id":"Q673779"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736537$92897C6B-DA42-45F2-A2B5-6E8A8AA825CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"42451d9b2f091244b010a7dc1fc6a0f53a57abc4","datavalue":{"value":{"entity-type":"item","numeric-id":4369883,"id":"Q4369883"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736537$3597FD99-45FC-4432-8836-7E2AF2CF5582","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a1552bd3d5951baf8fae8798e974ce686f215b50","datavalue":{"value":{"entity-type":"item","numeric-id":716314,"id":"Q716314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736537$8A9A1340-E75C-4A4D-92C2-6D75B7CB05B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"798d4826cffcf2b66484df70505c5456a56c335a","datavalue":{"value":{"entity-type":"item","numeric-id":533412,"id":"Q533412"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736537$E01CB615-78DA-4C42-BE81-FEB59F0DC1E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"185e2431cae92a1898cbf5df42c15a359faf1739","datavalue":{"value":{"entity-type":"item","numeric-id":958201,"id":"Q958201"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736537$C447E11B-80E0-405F-A3E1-4A95ACC4C527","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cfd9d764c33bfa700530d63996d0b22ff9e4b57c","datavalue":{"value":{"entity-type":"item","numeric-id":407588,"id":"Q407588"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736537$DDA5A181-F458-4561-B1AD-FB015FA434F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef365313663d0ae7fa68aee69938d4bced288769","datavalue":{"value":{"entity-type":"item","numeric-id":1041711,"id":"Q1041711"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736537$A17DBECA-F26B-4D66-B111-D26E1593D8AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5f8f9b88c400aa94632ac9b43a4d7e220d2d84b2","datavalue":{"value":{"entity-type":"item","numeric-id":958209,"id":"Q958209"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736537$FD76F736-0522-45F8-A6BB-413890F0F2A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"db87fb01cf4c31585b4fc9d7aff712aa3171a4c6","datavalue":{"value":{"entity-type":"item","numeric-id":2934608,"id":"Q2934608"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736537$E9D1B4C0-5C57-49A8-B93A-052C616FEF9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"667cb0679eb3acc82bff8d20cbd7271c5d24d9a2","datavalue":{"value":{"entity-type":"item","numeric-id":3656847,"id":"Q3656847"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736537$143FE666-E9C2-49D1-9EF7-E6CC99F5E97A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3ed162bb9c78b8393c8c9bdc35269b545d8a55d6","datavalue":{"value":"10.3390/A6010001","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736537$6F29EBA6-997A-411D-985E-3A51EF37D5E1","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cc318be5917127d8a2c46e13ad118feff4b254c8","datavalue":{"value":{"entity-type":"item","numeric-id":435732,"id":"Q435732"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5ba424dfde18cf68cdcb117172ed6fc3ec0f8f22","datavalue":{"value":{"amount":"+0.8936114311218262","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1736537$12A7AFC1-D9D0-4DD7-9205-EA717CC0D1F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c418b586011bd88d774ce17995c105a9409b895f","datavalue":{"value":{"entity-type":"item","numeric-id":2378531,"id":"Q2378531"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"35ff29f45155bf60b5ac535e40193d6612efd554","datavalue":{"value":{"amount":"+0.806577742099762","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1736537$1A371221-B58D-42ED-849A-29077A452EFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cfe48b5779f162a22732e2211c315cf62509eba8","datavalue":{"value":{"entity-type":"item","numeric-id":5458574,"id":"Q5458574"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a88fc068c7a7be809ab32e0a198cbc3821fa8b98","datavalue":{"value":{"amount":"+0.8029334545135498","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1736537$E1394DA2-BF20-445D-9733-257EFE26C659","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736537$F190AD75-9912-4DB7-B961-CCBD1AB63ACC","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Maximum disjoint paths on edge-colored graphs: approximability and tractability","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Maximum_disjoint_paths_on_edge-colored_graphs:_approximability_and_tractability"}}}}}