{"entities":{"Q1177173":{"pageid":1187922,"ns":120,"title":"Item:Q1177173","lastrevid":46246438,"modified":"2025-12-24T09:42:03Z","type":"item","id":"Q1177173","labels":{"en":{"language":"en","value":"\\(\\Delta{} ^ p_ 2\\)-complete lexicographically first maximal subgraph problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 20024"}},"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":"Q1177173$0242B277-E11B-4C5E-8257-8DCD02D24F52","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"808e32319b09a4c1402cb02c54b3c7a9ea14397a","datavalue":{"value":{"text":"\\(\\Delta{} ^ p_ 2\\)-complete lexicographically first maximal subgraph problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1177173$8BE236F5-CAF5-4FED-BB2F-F120B4B749E6","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"375340dc2b525b6b9157d4f82fc57b7e0ebff16b","datavalue":{"value":"0745.68050","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1177173$F783A3A3-123F-4FBB-8B1A-0542FB7A8F28","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9340a0071ebd4ddc87ebe8bfc87718b25caadede","datavalue":{"value":"10.1016/0304-3975(91)90072-A","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1177173$D7AB0ABF-3D13-46C6-A827-F405C3C500F2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c72921619bb1683825427c57b2aba25da8a8b109","datavalue":{"value":{"entity-type":"item","numeric-id":610146,"id":"Q610146"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177173$8B5C23D5-06B8-48E9-B551-E57F31416601","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177173$B78B0BF9-720B-4A37-AECC-18F5F07681C0","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1422b5e3113eee9dc98f0455d275631058399b8b","datavalue":{"value":{"time":"+1992-06-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":"Q1177173$32E95609-46AF-45A9-ADD2-37D05F57D349","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"cb1eeebb3938fd940de7dd26e5437f5629843731","datavalue":{"value":"The complexity class \\(\\Delta^ P_ 2\\) is the class of problems solvable in polynomial time using oracles in \\(NP\\).   The main result of the paper gives a fairly general class of \\(\\Delta^ P_ 2\\)-complete problems which are of the following kind:   Let \\(G=(V,E)\\) be a graph with a linearly ordered vertex set \\(V\\). For a given hereditary property \\(\\Pi\\) on graphs find the lexicographically first maximal (lfm) subset \\(U\\subseteq V\\) such that \\(U\\) induces a connected subgraph satisfying \\(\\Pi\\).   Without the connectedness condition the \\(P\\)-completeness of the lfm subgraph problem is known for any nontrivial polynomial-time testable property \\(\\Pi\\). The connectedness, however, makes the problem harder, as it is shown here.   The definition of the lfm connected subgraph problem for \\((LFMCSP(\\Pi))\\) is as follows:   Instance: A graph \\(G=(V,E)\\) with linear order on \\(V\\) and a vertex \\(v\\in V\\)   Question: Let \\(U\\) be the lfm subset of \\(V\\) whose induced subgraph is connected and satisfies \\(\\Pi\\). Is then \\(v\\in U\\)?   The main result shows the following:   Let \\(\\Pi\\) be a property satisfying the following conditions:   (i) \\(\\Pi\\) is hereditary on induced subgraphs.   (ii) \\(\\Pi\\) is determined by the blocks.   (iii) \\(\\Pi\\) is nontrivial on connected graphs.   (iv) \\(\\Pi\\) is polynomial-time testable.   Then \\(LFMCSP(\\Pi)\\) is \\(\\Delta^ P_ 2\\)-complete.   The \\(\\Delta^ P_ 2\\)-completeness of the lfm induced path problem and the \\(\\Delta^ P_ 2\\)-completeness of the lfm rooted tree problem for directed graphs are also shown.   The last problem becomes polynomial-time solvable when it is restricted to topologically sorted dags. For degree 4 the problem is \\(P\\)-complete and for degree 3 it is shown to be in \\(NC^ 2\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1177173$31F3E030-8C68-4846-84F5-59FD8CDE1B95","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1177173$8BFBD5B5-81EC-4786-92F7-138715E67084","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1177173$F8BA2645-30F3-4E32-8DAD-69F6BC9260C8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ed72a6dff6fac71275e2717b1a14420ec1d9133a","datavalue":{"value":"20024","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1177173$BFC440B6-B1BA-461E-B997-EEF54DA5F811","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"326de1d0743cf864e893913f9bc400368f3c475f","datavalue":{"value":"lexicographically first maximal subgraph problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1177173$CB7C3713-A173-4F60-A104-FE5F60F36538","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"53064f6609fb5177611c085d6f78e739c7e3f7f6","datavalue":{"value":"time complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1177173$AF0B0250-824B-4F1B-9D3C-9FC32A908DED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d556b8ef6d14752424a231945e88d2a64f249dd9","datavalue":{"value":"\\(\\Delta^ P_ 2\\)-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1177173$B5953090-30F1-43E2-81D6-E5E4020469E7","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"5af1aa80224172db75f7ae535f0d2940793ea880","datavalue":{"value":{"entity-type":"item","numeric-id":170457,"id":"Q170457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177173$E25C180D-E8B8-447D-B162-CB1D899D9F9D","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":"Q1177173$40F7AA5E-5F84-4BDC-A4DA-F487D1CF38DF","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb053d53af4aba25f2c65acd243c1fd587e0b70e","datavalue":{"value":{"entity-type":"item","numeric-id":1098641,"id":"Q1098641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177173$0C75B219-6419-4B1B-BF1A-F0A93B4C65A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fa6b88d7c0c035ddcdc73a99f8a04d3f8ce9fbcc","datavalue":{"value":{"entity-type":"item","numeric-id":4187840,"id":"Q4187840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177173$6FB99A92-08D2-4C8D-A9EB-2E6A56F6DA4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b90df03a170fcc85d9f6d5af38c0866a51f22b3f","datavalue":{"value":{"entity-type":"item","numeric-id":3694688,"id":"Q3694688"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177173$412F83A7-8D55-4BF8-BCC2-A2E0A5C395ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5fd898582b3042cd9f98f55a99a55f26af0712fb","datavalue":{"value":{"entity-type":"item","numeric-id":4128417,"id":"Q4128417"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177173$12237E48-A17F-4766-A6A4-03031B42C0AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c30f6e432ce9e9ae75031144ac1199e0b83ca0d7","datavalue":{"value":{"entity-type":"item","numeric-id":1107309,"id":"Q1107309"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177173$557E5C35-DAA3-4463-8E70-57DEF0A971F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a7a6c6b8ed22abfff754835104aaed55a1d4a80","datavalue":{"value":{"entity-type":"item","numeric-id":1140988,"id":"Q1140988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177173$02C74DF6-43CF-4C59-A648-EA6309E35A6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f1888200bdf18fb21113269f25f46af2d007268b","datavalue":{"value":{"entity-type":"item","numeric-id":1072703,"id":"Q1072703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177173$20107219-05DA-4C0E-8A19-2342D4CF40AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f4a7fa7d54032351874536d3a22aa174c5466f0d","datavalue":{"value":{"entity-type":"item","numeric-id":1108808,"id":"Q1108808"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177173$23AB6E57-D4C5-4FA1-B715-F8ED629D67B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"763e64b2188f866a166dbe50e81e86f6aa7ad552","datavalue":{"value":{"entity-type":"item","numeric-id":4729355,"id":"Q4729355"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177173$A01813BF-B267-4BFC-8220-3F62FD253C01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"32c9cf122d104d7332be7d6610d7ce2681b03b64","datavalue":{"value":{"entity-type":"item","numeric-id":3768398,"id":"Q3768398"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177173$A2158924-3B9D-4B85-B105-2607A226140A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"90edd91337b9f75f05ada0540fd29f2958b60727","datavalue":{"value":{"entity-type":"item","numeric-id":1062456,"id":"Q1062456"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177173$3D5EBF72-4B3B-463D-92A3-BE0278914768","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0f6be2378be9ef718165d6decb820a8d040ba744","datavalue":{"value":{"entity-type":"item","numeric-id":3766851,"id":"Q3766851"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177173$8FB73DB7-39E8-410D-BFB4-AAF42E9638A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2f6e21f081b18e8c1b37c600fa32ad6a2a06b4c0","datavalue":{"value":{"entity-type":"item","numeric-id":1146698,"id":"Q1146698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177173$30C611AA-1B37-41E3-93CF-964CFCE73136","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4f553c8f59e26fce96d1650fc4043c8eb59e4441","datavalue":{"value":{"entity-type":"item","numeric-id":3854626,"id":"Q3854626"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177173$8648D0DE-AC6C-4BAE-8F28-D6C969BB712D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6dca477d65333d3d53a4667c44899b3e70251aa0","datavalue":{"value":{"entity-type":"item","numeric-id":3921261,"id":"Q3921261"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177173$393BEF45-422B-45A6-9BE1-7502817FFEEA","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1083a9ea2ddeb620a2319195427b4438d5c862aa","datavalue":{"value":{"entity-type":"item","numeric-id":3795248,"id":"Q3795248"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1d71253649a6b80268813bd483044ed18026252b","datavalue":{"value":{"amount":"+0.936818778514862","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":"Q1177173$5F3FC006-77D0-4408-8F8C-4401651C969F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e646f802be5c3424504d96f271da79566c16c44d","datavalue":{"value":{"entity-type":"item","numeric-id":4729355,"id":"Q4729355"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"21af00e3245d1a6818395bfdbad3f37a6d0b2c97","datavalue":{"value":{"amount":"+0.8567959070205688","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":"Q1177173$A15FE29E-A74E-4F23-865B-12391A86C70A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f7ca6e66bf91c4c8ac13dc7a3f72b80eaf7f1414","datavalue":{"value":{"entity-type":"item","numeric-id":3783600,"id":"Q3783600"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"51cd99d636882968585557977aac6e0cdca28f90","datavalue":{"value":{"amount":"+0.8392024040222168","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":"Q1177173$3E32F807-1271-46D3-9ECA-6513AE85E503","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2fbaceb890d5c053a359b4d8f79b7d25dcfbf2f6","datavalue":{"value":{"entity-type":"item","numeric-id":3975140,"id":"Q3975140"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7fb2378bbd1282e3018903778b8f58b536fbcc8c","datavalue":{"value":{"amount":"+0.75398850440979","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":"Q1177173$CE59707D-E00A-4871-BA37-1BF493397568","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1177173","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1177173"}}}}}