{"entities":{"Q653792":{"pageid":655641,"ns":120,"title":"Item:Q653792","lastrevid":42625965,"modified":"2025-07-07T08:35:24Z","type":"item","id":"Q653792","labels":{"en":{"language":"en","value":"The three-in-a-tree problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5990559"}},"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":"Q653792$81216F86-79A1-4163-8EB7-3541802FC96B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8a4494ae4b6238a64652c490228cd6b66ddcd7b5","datavalue":{"value":{"text":"The three-in-a-tree problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q653792$5E257BB0-AB95-4BD6-9544-74F71AED167B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2c8409a284dfd7220ab3bddf2a37b09064b003be","datavalue":{"value":"1231.05246","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q653792$E385C74A-54C0-43AE-83D1-F31A2F6FDBE3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"86791d2de8f741697c1a28c841b5e520b1ea6f17","datavalue":{"value":{"entity-type":"item","numeric-id":256974,"id":"Q256974"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653792$472571BB-4381-4314-B16B-B4007CED82F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6b7666b1aea36d852e5d73efdf8f9faa64e3f54f","datavalue":{"value":{"entity-type":"item","numeric-id":705887,"id":"Q705887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653792$8BDFD7E0-6158-4EB4-B8C1-9C8AA1ACD2EE","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653792$E579F33D-618D-478D-A6D5-B8B233BFF2C0","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5e7c33876f49da64580f033b95b71f550b669c2d","datavalue":{"value":{"time":"+2011-12-19T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q653792$9DB05EB2-2716-4F82-ADBA-02CDF5A7527D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a7902db57224836258cdd9c2e60e5879eba70557","datavalue":{"value":"The authors show that, given a graph \\(G=(V,E)\\) together with three vertices \\(v_1, v_2, v_3\\) of \\(G\\), deciding if there exists an induced tree of \\(G\\) that contains \\(v_1, v_2, v_3\\) can be done in time \\(O(| V| ^4)\\). Using this as a subroutine, they show that there is  {\\parindent=6mm \\begin{itemize}\\item[(1)]a polynomial time algorithm to test whether a graph contains a theta as an induced subgraph (this was an open question of interest), where a theta is a graph consisting of two nonadjacent vertices \\(a, b\\) and three paths \\(P_1, P_2, P_3\\), each joining \\(a, b\\) and otherwise vertex-disjoint, such that for \\(1\\leq i<j\\leq 3\\) the subgraph induced on \\(V(P_i)\\cup V(P_j)\\) is a cycle, and  \\item[(2)]an alternative way to test whether a graph contains a pyramid (a fundamental step in checking whether a graph is perfect), where a pyramid is a graph consisting of a vertex \\(a\\) and a triangle \\(\\{b_1, b_2, b_3\\}\\), and three paths \\(P_1, P_2, P_3\\), such that: \\(P_i\\) is between \\(a\\) and \\(b_i\\) for \\(i=1,2,3\\); for \\(1\\leq i<j \\leq 3\\) \\(P_i, P_j\\) are vertex-disjoint except for \\(a\\) and the subgraph induced on \\(V(P_i)\\cup V(P_j)\\) is a cycle; and at most one of \\(P_1, P_2, P_3\\) has only one edge.   \\end{itemize}} The more general \\(k\\)-in-a-tree problem has been discussed by \\textit{W. Liu} and \\textit{N. Trotignon} [``The \\(k\\)-in-a-tree problem for graphs of girth at least \\(k\\),'' Discrete Appl. Math. 158, No.\\,15, 1644--1649 (2010; Zbl 1198.05142)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q653792$53F46FB6-1B14-4CE9-A649-6B62F0934668","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":"Q653792$3A92E74A-83C4-4351-B3C3-17E699C4B607","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q653792$1C53EB3A-7167-4138-B462-EBC3EE56C8B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q653792$9C090554-2552-403E-95A1-1BA99446CA80","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3af92fa66920204da49a2d1985d64bda5e8fd5b5","datavalue":{"value":"5990559","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q653792$9D9470A0-9C43-48DE-B7EC-13063AAF53FE","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e7c81c01316d689fee305bdbfd5d50fd9c2b86c9","datavalue":{"value":"induced subgraph testing, theta, pyramid","type":"string"},"datatype":"string"},"type":"statement","id":"Q653792$268A10DF-B68B-4A42-9E71-D62767B576AF","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":"Q653792$091D043B-EDE6-402E-B03D-DE612DDCA777","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"911740b94272d86c8939bceb91b0172d11e8be4c","datavalue":{"value":"https://doi.org/10.1007/s00493-010-2334-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q653792$F42E6B77-D8DF-4618-8A3B-6BBC41C4C755","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7dc0187540f4497b026b433bf6f8acd4da666a00","datavalue":{"value":"W2104062785","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q653792$997CF892-3F4D-4D1A-89AC-963B72DC87A8","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d82cfa9f684c3350648874deb95288407da9381e","datavalue":{"value":{"entity-type":"item","numeric-id":1175980,"id":"Q1175980"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653792$67D3C13B-62DF-4D7F-93E3-1C075FE62016","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"791798dc1a003f6099937439f8e635db58bb959d","datavalue":{"value":{"entity-type":"item","numeric-id":3394995,"id":"Q3394995"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653792$633F099C-61EB-43FD-B5C7-BBE187204BBE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c20e0b8b69bb74bc107c5a48305e78f34c64cd1d","datavalue":{"value":{"entity-type":"item","numeric-id":2494439,"id":"Q2494439"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653792$F42139B0-81DD-4FCD-A6A3-9C252B81EFE9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5e6ef4217803d9c05213925537119a10d91af8f1","datavalue":{"value":{"entity-type":"item","numeric-id":5470779,"id":"Q5470779"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653792$B25035EE-06A2-47D7-B8D6-49D1FA9139F4","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5c85fd0de7e9ea6846abec57e7d80e6da37cebf7","datavalue":{"value":"10.1007/S00493-010-2334-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q653792$C4A48596-D677-49FE-9405-2B2E05252B3A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4fd0438ca2d96e016cf21341d628568c7b075984","datavalue":{"value":{"entity-type":"item","numeric-id":602681,"id":"Q602681"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fa7e72fafd1c4569986ecde8b4286e9232fbf616","datavalue":{"value":{"amount":"+0.8545969","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q653792$C7EE8564-50BB-4953-94EB-CA8555672288","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c0ee9769ea4bb0afc5a9e498f0dab63ff25c182a","datavalue":{"value":{"entity-type":"item","numeric-id":5145012,"id":"Q5145012"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c3f7a4dd9ab737271cc2bb557f8ceead24a7155a","datavalue":{"value":{"amount":"+0.82581186","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q653792$4C54295C-5CBB-4D94-9FFD-005CD8F25BC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7ed94a4240eba25d87e4949f1e22f9d93668f48b","datavalue":{"value":{"entity-type":"item","numeric-id":844235,"id":"Q844235"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"286b964fb9919afa3994f15b15fb44c6ad9b4403","datavalue":{"value":{"amount":"+0.8020398","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q653792$058B695E-B8D0-4DAA-97DC-AFC0D6FC0EA1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0f85a316b8be00f8a548e3e4967e3285fd228303","datavalue":{"value":{"entity-type":"item","numeric-id":2692722,"id":"Q2692722"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d36a7c99aaec7a496acae96a6313317cc118efaf","datavalue":{"value":{"amount":"+0.7870499","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q653792$19CF8B02-9898-4ECC-8B54-044F00B15AB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6a9045b0779a1fe4e6648b914f41069be4437e62","datavalue":{"value":{"entity-type":"item","numeric-id":1086577,"id":"Q1086577"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d42af30c2965b8923dc228fcfaf7724ca2d522f7","datavalue":{"value":{"amount":"+0.7799536","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q653792$00441028-B3AA-4516-A4A8-CA608A39D26D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7fbce7fcabf6ac497a07d9c1cddf2341168c5072","datavalue":{"value":{"entity-type":"item","numeric-id":3334090,"id":"Q3334090"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"90790188c8199cadbc6a3d51db94565230fc5342","datavalue":{"value":{"amount":"+0.7722353","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q653792$5B74C6DC-75E2-4C2E-8234-36C2381C75B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5b6be6cbea5f1ce6f49976e279ae488389b2ef67","datavalue":{"value":{"entity-type":"item","numeric-id":686254,"id":"Q686254"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3a5e5d770215625cbbaa578ce5b9ad4c0f2382d5","datavalue":{"value":{"amount":"+0.7692988","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q653792$E23D0D65-8347-47E9-82D0-B0EEE85CE32B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2dcb6e169986475fe7f3e1c55c62f003cb664c7b","datavalue":{"value":{"entity-type":"item","numeric-id":967418,"id":"Q967418"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e255058653a69a3541764de3831945c8306180ce","datavalue":{"value":{"amount":"+0.76033014","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q653792$E17A4ED8-B065-451D-B779-3DB2A2E3538C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4c4301193ac272d53bf6a55ce9aca0a718852e8a","datavalue":{"value":{"entity-type":"item","numeric-id":2934642,"id":"Q2934642"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"92ed57140dd9204a5af69651d157521e17d09bcb","datavalue":{"value":{"amount":"+0.7568782","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q653792$55CCBA2B-8D65-4D31-B188-2366BA28BE12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a61042dba55e766d0f99d3bccdacdfe5b9371c56","datavalue":{"value":{"entity-type":"item","numeric-id":3751595,"id":"Q3751595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"39e352cd30048a73f32c56f7ae8741ed47ffb420","datavalue":{"value":{"amount":"+0.7564202","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q653792$8236B8C7-A652-4155-A164-5F4C7532DC15","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:653792","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:653792"}}}}}