Feedback vertex set: Revision history

27 March 2025

• curprev 23:0223:02, 27 March 2025 2603:8001:3d00:6bd:947e:7d53:db1e:fdd8 talk 16,752 bytes +21 The summary used to claim that the optimization problem is NP-complete. That's false, it is NP-hard. Changed that to the decision problem, which is NP-complete. undo

20 March 2025

• curprev 20:0120:01, 20 March 2025 LucasBrown talk contribs 16,731 bytes +46 Adding local short description: "Concept in graph theory", overriding Wikidata description "a set of vertices in a node-link graph whose deletion eliminates all cycles in the graph" undo Tag: Shortdesc helper

6 February 2025

• curprev 19:2719:27, 6 February 2025 Giftlite talk contribs 16,685 bytes −16 simplify undo
• curprev 00:0000:00, 6 February 2025 David Eppstein talk contribs 16,701 bytes +60 →NP-completeness: matroid parity problem undo

5 February 2025

• curprev 20:2920:29, 5 February 2025 David Eppstein talk contribs 16,641 bytes +68 →NP-hardness: we don't need to distinguish hard vs complete here undo
• curprev 19:5319:53, 5 February 2025 Giftlite talk contribs 16,573 bytes +4 →NP-hardness: wlnk undo

2 February 2025

• curprev 23:4823:48, 2 February 2025 David Eppstein talk contribs 16,569 bytes −62 Undid revision 1273562252 by BagLuke (talk) WTF no it isn't. Maybe you're thinking of the undirected case? undo Tag: Undo
• curprev 23:1323:13, 2 February 2025 BagLuke talk contribs 16,631 bytes +62 Added wiki link undo Tag: Reverted
• curprev 23:1223:12, 2 February 2025 BagLuke talk contribs 16,569 bytes +420 Added illustration and description. undo

20 August 2024

• curprev 21:2221:22, 20 August 2024 Onel5969 talk contribs m 16,149 bytes +28 Disambiguating links to Deadlock (link changed to Deadlock (computer science)) using DisamAssist. undo

29 July 2024

• curprev 00:2800:28, 29 July 2024 Citation bot talk contribs 16,121 bytes +21 Added doi-access. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox2 | #UCB_webform_linked 479/1051 undo

13 June 2024

• curprev 00:3500:35, 13 June 2024 David Eppstein talk contribs 16,100 bytes +34 Mauricio Resende undo

11 December 2023

• curprev 01:0001:00, 11 December 2023 OAbot talk contribs m 16,066 bytes +21 Open access bot: doi updated in citation with #oabot. undo

4 September 2023

• curprev 10:4910:49, 4 September 2023 Citation bot talk contribs 16,045 bytes −12 Alter: title, template type. Add: chapter-url, chapter. Removed or converted URL. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Headbomb | #UCB_toolbar undo

29 August 2023

• curprev 05:3105:31, 29 August 2023 David Eppstein talk contribs 16,057 bytes −417 Undid revision 1172767461 by N6garcia (talk) WP:OR and crankery undo Tag: Undo
• curprev 05:1805:18, 29 August 2023 N6garcia talk contribs 16,474 bytes +417 added my algorithm to the page undo Tag: Reverted

23 July 2023

• curprev 00:5800:58, 23 July 2023 Headbomb talk contribs 16,057 bytes +7 Alter: template type. Add: chapter-url, chapter, title. Removed or converted URL. | Use this tool. Report bugs. | #UCB_Gadget undo
• curprev 00:2600:26, 23 July 2023 JCW-CleanerBot talk contribs m 16,050 bytes −5 task, replaced: Algorithm Theory - → Algorithm Theory – undo Tag: AWB

17 February 2023

• curprev 12:2212:22, 17 February 2023 Citation bot talk contribs 16,055 bytes +24 Add: isbn. | Use this bot. Report bugs. | Suggested by Superegz | Category:NP-complete problems | #UCB_Category 29/78 undo

4 January 2023

• curprev 12:2912:29, 4 January 2023 Citation bot talk contribs 16,031 bytes +57 Alter: url. URLs might have been anonymized. Add: s2cid, isbn, authors 1-1. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by SemperIocundus | #UCB_webform 1913/2500 undo

28 December 2022

• curprev 03:5803:58, 28 December 2022 WikiCleanerBot talk contribs m 15,974 bytes 0 v2.05b - Bot T20 CW#61 - Fix errors for CW project (Reference before punctuation) undo Tag: WPCleaner

23 December 2022

• curprev 10:4110:41, 23 December 2022 GraphsAndAlgorithms talk contribs 15,974 bytes +1,215 Updated statement on the approximability of the problem in directed graphs: no constant factor approximation is possible in polynomial time assuming both P =/= NP and the unique games conjecture. Previously, the page only mentioned that it was not known whether such an algorithm exists for the directed version of the problem. undo Tag: Visual edit

25 July 2022

• curprev 00:5100:51, 25 July 2022 Citation bot talk contribs 14,759 bytes +237 Alter: doi, template type. Add: s2cid, isbn, year, series, bibcode, volume, authors 1-1. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Abductive | #UCB_webform 809/3850 undo

26 March 2022

• curprev 19:3919:39, 26 March 2022 InternetArchiveBot talk contribs 14,522 bytes +205 Rescuing 1 sources and tagging 0 as dead.) #IABot (v2.0.8.6 undo

13 July 2021

• curprev 13:2713:27, 13 July 2021 FrescoBot talk contribs m 14,317 bytes −13 Bot: link syntax undo

5 July 2021

• curprev 15:2615:26, 5 July 2021 FrescoBot talk contribs m 14,330 bytes −17 Bot: link syntax undo

9 May 2021

• curprev 17:1917:19, 9 May 2021 Erel Segal talk contribs 14,347 bytes +487 →Applications undo Tag: Visual edit
• curprev 13:4113:41, 9 May 2021 Erel Segal talk contribs 13,860 bytes +31 →Approximation undo Tag: Visual edit
• curprev 13:3513:35, 9 May 2021 Erel Segal talk contribs 13,829 bytes +642 No edit summary undo Tag: Visual edit
• curprev 13:2413:24, 9 May 2021 Erel Segal talk contribs 13,187 bytes +453 No edit summary undo Tag: Visual edit

4 November 2020

• curprev 20:2520:25, 4 November 2020 WikiCleanerBot talk contribs m 12,734 bytes −1 v2.03b - Bot T20 CW#61 - WP:WCW project (Reference before punctuation) undo Tag: WPCleaner

25 October 2020

• curprev 17:3117:31, 25 October 2020 David Eppstein talk contribs 12,735 bytes −319 Undid revision 985347256 by Jochen Burghardt (talk) I think this example is too small, too specific, and too ambiguous to be illuminating. Is it even a graph? Are A,B,out vertices? What about the three-point junction near out? What about the triple points where the wires and the boundaries of the gate symbols meet? Why should we expect readers to understand which gate is an and gate and which an or? undo Tag: Undo
• curprev 12:3412:34, 25 October 2020 Jochen Burghardt talk contribs 13,054 bytes +319 →top: suggest image (application to digital circuits) undo Tag: Reverted

18 December 2019

• curprev 04:2904:29, 18 December 2019 InternetArchiveBot talk contribs 12,735 bytes +54 Bluelinking 1 books for verifiability.) #IABot (v2.1alpha3 undo

1 October 2019

• curprev 08:0908:09, 1 October 2019 77.11.132.228 talk 12,681 bytes +183 →Approximation undo

5 September 2019

• curprev 13:1713:17, 5 September 2019 ContentNerd talk contribs 12,498 bytes +30 Added free to read link in citations with OAbot #oabot undo Tag: OAbot [1.0]

10 February 2019

• curprev 19:0519:05, 10 February 2019 David Eppstein talk contribs 12,468 bytes −29 →Research articles: Bafna/Berman/Fujito is another CiteSeerX strike against Citation Bot undo
• curprev 17:3217:32, 10 February 2019 Citation bot talk contribs m 12,497 bytes +178 Alter: issue, isbn, title. Add: title-link, isbn, citeseerx. Formatted dashes. | You can use this bot yourself. Report bugs here. | User-activated. undo

19 June 2018

• curprev 18:0118:01, 19 June 2018 Bibcode Bot talk contribs m 12,319 bytes +31 Adding 0 arxiv eprint(s), 1 bibcode(s) and 0 doi(s). Did it miss something? Report bugs, errors, and suggestions at User talk:Bibcode Bot undo

16 May 2018

• curprev 13:2113:21, 16 May 2018 OAbot talk contribs m 12,288 bytes +19 Open access bot: add arxiv identifier to citation with #oabot. undo

11 February 2018

• curprev 16:1916:19, 11 February 2018 Rjwilmsi talk contribs m 12,269 bytes +37 →Research articles: Journal cites, Added 1 doi to a journal cite undo Tag: AWB

17 December 2017

• curprev 06:0706:07, 17 December 2017 David Eppstein talk contribs 12,232 bytes −545 →Textbooks and survey articles: oops, dup undo
• curprev 06:0506:05, 17 December 2017 David Eppstein talk contribs 12,777 bytes +11 →Exact algorithms: (undirected) undo
• curprev 06:0506:05, 17 December 2017 David Eppstein talk contribs 12,766 bytes +805 polynomial for subcubic undo

25 July 2017

• curprev 15:4215:42, 25 July 2017 David Eppstein talk contribs m 11,961 bytes −401 Reverted edits by 77.179.8.249 (talk) to last version by David Eppstein undo
• curprev 10:1510:15, 25 July 2017 77.179.8.249 talk 12,362 bytes +401 →Exact algorithms undo

29 April 2016

• curprev 05:1705:17, 29 April 2016 David Eppstein talk contribs m 11,961 bytes +38 Giuseppe F. Italiano undo

31 January 2016

• curprev 20:0420:04, 31 January 2016 BD2412 talk contribs m 11,923 bytes −30 Fixing links to disambiguation pages, replaced: graph{{dn|date=January 2016}} → graph (2) using AWB undo
• curprev 14:4214:42, 31 January 2016 BD2412 talk contribs m 11,953 bytes +48 Graph (mathematics) is now a disambiguation link; please fix., replaced: graph → graph{{dn|{{subst:DATE}}}}, graph → grap using [[Project:AWB|AWB undo

20 August 2014

• curprev 21:2821:28, 20 August 2014 David Eppstein talk contribs 11,905 bytes +490 alternative approximation algorithm with the same approximation ratio undo