{"entities":{"Q1123898":{"pageid":1134647,"ns":120,"title":"Item:Q1123898","lastrevid":80317979,"modified":"2026-05-06T15:55:22Z","type":"item","id":"Q1123898","labels":{"en":{"language":"en","value":"On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4110719"}},"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":"Q1123898$40671735-A857-4D46-8E1A-808C5880ED56","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"cf496c46cad46d21c738e6a6ba2015e6670d5ab9","datavalue":{"value":{"text":"On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1123898$B45E4A2E-C15C-4E1E-B3EA-BF9A1C11AC45","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a901f24519bea7e36c059a451afc9035ba0e7af7","datavalue":{"value":"0678.05026","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123898$5BB9B367-2CA2-4D0A-90D6-4DDA22C58832","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"50ca59b7249f39d7f3046f998ba0ab997638912b","datavalue":{"value":"10.1016/0012-365X(88)90226-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123898$7DE5F0BF-F338-4525-8205-CD478AF24565","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c261379e8a37f236b4a2ff1bba217c4e07a7cc65","datavalue":{"value":{"entity-type":"item","numeric-id":436543,"id":"Q436543"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123898$25B1AD06-2D13-42DB-A30D-C1B57C9355EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6f9687f1c89507047b3c63b7a488446f455e2b28","datavalue":{"value":{"entity-type":"item","numeric-id":674340,"id":"Q674340"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123898$34BBDBFC-3F0A-4FC8-A4AD-EADAB152BB89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1a1126afd5664d64502f40209b8376c1a745e373","datavalue":{"value":{"entity-type":"item","numeric-id":1123897,"id":"Q1123897"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123898$C009C6DD-2337-4162-9891-22E0FC049695","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123898$011697B7-4FFA-400F-81FF-6A04A9449193","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1123898$4565213A-EF33-414D-877D-271877073CA6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"874b5cd009129aa61f375157a233e9f3e09e0a9d","datavalue":{"value":"For a graph \\(G=(V,E)\\) and a set \\(S\\subset V\\) let G-S be the graph obtained from G by deleting the vertices in S. A set of vertices F is called a feedback set of G if G-F contains no circuit. The feedback set problem is to find a minimum feedback set. It is known both the nonseparating independent set problem (to find the maximum independent set which contains no separating sets) and feedback set problem are NP- complete graph problems.    In the paper these problems for graphs with no vertex degree exceeding 3 are reduced to the corresponding problems for 3-regular graphs, and then to the matching problem and the spanning set problem of some linearly represented 2-polymatroid, respectively, for which Lov\u00e1sz\u015b polynomial-time algorithms are known.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123898$E32BCC41-2D1E-4079-B895-6839585E9E8C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123898$9644D0DD-D04A-41FE-B09D-FCA6A0493493","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123898$43EC8542-AFD9-4FCE-B05D-6C930876BDAE","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"56898eff3f2860627a47ef9e2a94ee350a1d1c69","datavalue":{"value":"4110719","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123898$8AF4A8F7-C7E7-493D-B340-EC62E95A60A7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"57470db9999dec535f8e38fda8f236f820b6240b","datavalue":{"value":"feedback set problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123898$DD4D34DE-503E-43D7-B59C-DAEF96FE79DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c3bf74fef7345ac3440f38562cc0ccb7d209ca5b","datavalue":{"value":"minimum feedback set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123898$5BC6B8FC-B094-4703-B59A-467D657B116D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b4c085ffc0581283ee8d94cf2db79f1de3b95a5f","datavalue":{"value":"nonseparating independent set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123898$EC8D9C89-CFF1-4134-BA7F-BE899C511FCC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5a23d15bc9cbd737803a12e8c552f3c4e83e1665","datavalue":{"value":"NP-complete graph problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123898$6893EBB9-C120-49EB-8D68-73B45D044D88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e6ca28fe262dc4406acfcbf757b519c703f60b86","datavalue":{"value":"3-regular graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123898$08A2B084-B89B-479F-A5CC-D678C8D7FECF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"56922b44f4b77c888d5a91237cc4964d535123f5","datavalue":{"value":"matching problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123898$23DE4B11-38D2-4C87-81A1-3E818B847EA3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"60afa63a217961dc2d325d46fc5d3d0ea5914aa2","datavalue":{"value":"spanning set problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123898$D9B02D14-D1FE-49C9-8381-47EA3A5CFCD2","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"54137af57c114690e650737f71d6927503190408","datavalue":{"value":"Q59442098","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123898$9BECB7E1-5116-4E5F-A3B9-BE1AD2DBC39D","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":"Q1123898$A0193170-E5C5-4FBD-96DF-227A1BE75EC9","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b382547d8fad964f6c32dd98e9936f8afb92f192","datavalue":{"value":{"entity-type":"item","numeric-id":1230637,"id":"Q1230637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123898$0CC0C17C-6720-4710-B917-D80D1578FEE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f89a031afe32dfcbf4f8fba11966dba55c1408ae","datavalue":{"value":{"entity-type":"item","numeric-id":4179026,"id":"Q4179026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123898$AA44E140-E256-4B93-9CE2-024EDFFD5F15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123898$5544A885-AED4-4B73-922B-A8A6219F7F52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"43f7430338b64b3789e62f6f656eea2c66f30a45","datavalue":{"value":{"entity-type":"item","numeric-id":3934404,"id":"Q3934404"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123898$16B147C8-CC56-4A5F-8FE4-8ED84140DF01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a6d76ca597ca9190efb3163439722d9148e6f8e5","datavalue":{"value":{"entity-type":"item","numeric-id":3739144,"id":"Q3739144"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123898$D80BD61F-FDF9-4AE8-9FF4-26B97E758DAE","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7c326bf63205b0509a9126bdec86f34bd9eac4b8","datavalue":{"value":"https://doi.org/10.1016/0012-365x(88)90226-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q1123898$CEE70E08-F307-44A7-ADAE-E446402C0317","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"9e321bd42b7cf4328fcff9b6f9bc90569ee4978f","datavalue":{"value":"W2069169607","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123898$84C4FDB5-DDE2-4515-B10D-605B36BD3A58","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"37be9d0cb6f8573fa57f9f9085bb057df4c8657f","datavalue":{"value":{"entity-type":"item","numeric-id":3318125,"id":"Q3318125"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"941d89f84f1fa879d96cf6748c53631752f2b517","datavalue":{"value":{"amount":"+0.8245331645011902","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":"Q1123898$F8D198DD-9565-4361-A2D8-E91C683CAD66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4c41ccd8e303f478e0701eafe88963c27e8e5988","datavalue":{"value":{"entity-type":"item","numeric-id":4952178,"id":"Q4952178"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"31b049dc738922ffe0a254acf0aa31ecc1a9bf4c","datavalue":{"value":{"amount":"+0.8236719965934753","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":"Q1123898$B97C6BF8-A5EF-451F-9BE1-5761675BAD3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cd1f5eb1e1a1843af0efe83b12383405fc66aefb","datavalue":{"value":{"entity-type":"item","numeric-id":3804730,"id":"Q3804730"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"30372d5e25b56a10bf20ecf42c1ffa99c1e0e925","datavalue":{"value":{"amount":"+0.8099924325942993","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":"Q1123898$C484B82D-1E9E-4E66-B521-12BEDCF74283","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c89ac61bab2c234cabc96edc24d40e15c54e1c7e","datavalue":{"value":{"entity-type":"item","numeric-id":2946071,"id":"Q2946071"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6c466ee72568649761a5f8d096d4ce967def2ec1","datavalue":{"value":{"amount":"+0.7872653603553772","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":"Q1123898$34CF8D92-B1EC-4A64-9DE8-90864ED6F477","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"141060f2e3ed11e3c1570c65949c62a7a7409123","datavalue":{"value":{"entity-type":"item","numeric-id":1281930,"id":"Q1281930"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8d6666c2daa3363c82e868e98f7c2895eb25b855","datavalue":{"value":{"amount":"+0.7808625102043152","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":"Q1123898$8E45AAD0-C68C-4F25-9966-51010947A4DF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_nonseparating_independent_set_problem_and_feedback_set_problem_for_graphs_with_no_vertex_degree_exceeding_three"}}}}}