Odd cycle transversal

A graph with an odd cycle transversal of size 2: removing the two blue bottom vertices leaves a bipartite graph.

In graph theory, an odd cycle transversal of an undirected graph is a set of vertices of the graph that has a nonempty intersection with every odd cycle in the graph. Removing the vertices of an odd cycle transversal from a graph leaves a bipartite graph as the remaining induced subgraph.[1]

Relation to vertex cover

A given -vertex graph has an odd cycle transversal of size , if and only if the Cartesian product of graphs (a graph consisting of two copies of , with corresponding vertices of each copy connected by the edges of a perfect matching) has a vertex cover of size . The odd cycle transversal can be transformed into a vertex cover by including both copies of each vertex from the transversal and one copy of each remaining vertex, selected from the two copies according to which side of the bipartition contains it. In the other direction, a vertex cover of can be transformed into an odd cycle transversal by keeping only the vertices for which both copies are in the cover. The vertices outside of the resulting transversal can be bipartitioned according to which copy of the vertex was used in the cover.[1]

Algorithms and complexity

The problem of finding the smallest odd cycle transversal, or equivalently the largest bipartite induced subgraph, is also called odd cycle transversal, and abbreviated as OCT. It is NP-hard, as a special case of the problem of finding the largest induced subgraph with a hereditary property (as the property of being bipartite is hereditary). All such problems for nontrivial properties are NP-hard.[2][3]

The equivalence between the odd cycle transversal and vertex cover problems has been used to develop fixed-parameter tractable algorithms for odd cycle transversal, meaning that there is an algorithm whose running time can be bounded by a polynomial function of the size of the graph multiplied by a larger function of . The development of these algorithms led to the method of iterative compression, a more general tool for many other parameterized algorithms.[1] The parameterized algorithms known for these problems take nearly-linear time for any fixed value of .[4] Alternatively, with polynomial dependence on the graph size, the dependence on can be made as small as .[5] In contrast, the analogous problem for directed graphs does not admit a fixed-parameter tractable algorithm under standard complexity-theoretic assumptions.[6]

See also

  • Maximum cut, equivalent to asking for a minimum set of edges whose removal leaves a bipartite graph

References

  1. ^ a b c Cygan, Marek; Fomin, Fedor V.; Kowalik, Lukasz; Lokshtanov, Daniel; Marx, Dániel; Pilipczuk, Marcin; Pilipczuk, Michal; Saurabh, Saket (2015), Parameterized Algorithms, Springer, pp. 64–65, doi:10.1007/978-3-319-21275-3, ISBN 978-3-319-21274-6, MR 3380745
  2. ^ Garey, Michael R.; Johnson, David S. (1979), "GT21: Induced subgraph with property Π", Computers and Intractability: A Guide to the Theory of NP-completeness, W. H. Freeman, p. 195
  3. ^ Yannakakis, Mihalis (1978), "Node-and edge-deletion NP-complete problems", Proceedings of the 10th ACM Symposium on Theory of Computing (STOC '78), pp. 253–264, doi:10.1145/800133.804355
  4. ^ Kawarabayashi, Ken-ichi; Reed, Bruce (2010), "An (almost) linear time algorithm for odd cycles transversal", Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, Philadelphia, PA: SIAM, pp. 365–378, CiteSeerX 10.1.1.215.2581, doi:10.1137/1.9781611973075.31, ISBN 978-0-89871-701-3, MR 2809682
  5. ^ Lokshtanov, Daniel; Narayanaswamy, N. S.; Raman, Venkatesh; Ramanujan, M. S.; Saurabh, Saket (2014), "Faster parameterized algorithms using linear programming", ACM Transactions on Algorithms, 11 (2): Art. 15, 31, arXiv:1203.0833, doi:10.1145/2566616, MR 3283570
  6. ^ Lokshtanov, Daniel; Ramanujan, M. S.; Saurabh, Saket; Zehavi, Meirav (2017), Parameterized complexity and approximability of directed odd cycle transversal, arXiv:1704.04249, Bibcode:2017arXiv170404249L

Read other articles:

This list of famous or notable people has no clear inclusion or exclusion criteria. Please help to define clear inclusion criteria and edit the list to contain only subjects that fit those criteria. (August 2013) (Learn how and when to remove this template message) This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: List of Koreans in Japan –&…

Artikel ini sebatang kara, artinya tidak ada artikel lain yang memiliki pranala balik ke halaman ini.Bantulah menambah pranala ke artikel ini dari artikel yang berhubungan atau coba peralatan pencari pranala.Tag ini diberikan pada Oktober 2022. Halaman ini berisi artikel tentang istilah politik. Untuk jalan di Singapura, lihat Jalan Arab (Singapura). Jalan raya telah lama menjadi tempat utama untuk interaksi masyarakat di dunia Arab, yang berujung pada pemakaian kiasan jalan Arab untuk opini pub…

Caspar HedioBiografiKelahiran1494 (Kalender Masehi Gregorius) Ettlingen Kematian17 Oktober 1552 (Kalender Masehi Gregorius) (57/58 tahun)Strasbourg   Cathedral preacher (en)  Data pribadiAgamaGereja Lutheran PendidikanUniversitas Albert Ludwig Freiburg KegiatanPekerjaanSejarawan dan teolog Caspar Hedio, ukiran tembaga abad ke-16 Caspar Hedio, juga ditulis sebagai Kaspar Hedio, Kaspar Heyd, Kaspar Bock atau Kaspar Böckel (Ettlingen, 1494 - Strasbourg, 17 Oktober 1552) adalah seora…

Documentation generator Not to be confused with CMU Sphinx or Sphinx (search engine). SphinxDeveloper(s)Georg BrandlInitial releaseMarch 21, 2008 (2008-03-21)Stable release7.2.6[1] / September 13, 2023; 6 months ago (2023-09-13) Repositorygithub.com/sphinx-doc/sphinx Written inPythonOperating systemCross-platformTypeDocumentation generatorLicenseBSDWebsitewww.sphinx-doc.org Sphinx is a documentation generator written and used by the Python community. It i…

Disambiguazione – Se stai cercando la squadra di Rivarolo Canavese, vedi Unione Sportiva Dilettantistica Rivarolese 1906. US RivaroleseCalcio Gli avvoltoi, rivarolesi Segni distintivi Uniformi di gara Casa Trasferta Colori sociali Giallo, rosso, nero Dati societari Città Genova Nazione  Italia Confederazione UEFA Federazione FIGC Campionato Seconda Categoria Fondazione 1919 Scioglimento1937Rifondazione1938Scioglimento1941Rifondazione1945Rifondazione2022 Presidente Ivo Bellinazzi Allenato…

Vostok (Rusia Восток, diterjemahkan sebagai Timur) adalah sebuah keluarga roket berasal dari ICBM Soviet R-7 Semyorka dirancang untuk program luar angkasa manusia. Keluarga ini roket yang meluncurkan satelit buatan pertama (sputnik) dan pesawat ruang angkasa berawak pertama dalam sejarah manusia. Itu adalah subset dari keluarga roket R-7. Pada tanggal 18 Maret tahun 1980, sebuah roket Vostok-2M meledak di landasan peluncuran di Plesetsk selama operasi pengisian bahan bakar, menewaskan 48 o…

В Википедии есть статьи о других людях с фамилией Реклю. Элизе РеклюÉlisée Reclus Имя при рождении фр. Jacques Élisée Reclus Дата рождения 15 марта 1830(1830-03-15)[1][2][…] Место рождения Сент-Фуа-ла-Гранд, Жиронда, Франция Дата смерти 4 июля 1905(1905-07-04)[1][3][…] (75 лет) Место смерти То…

This article is about reports filed by consumers who are dissatisfied with a business transaction and/or interaction. For the consumers in biology, see Heterotroph. The Complaint tablet to Ea-nāṣir may be the oldest known written customer complaint[1] A consumer complaint or customer complaint is an expression of dissatisfaction on a consumer's behalf to a responsible party (London, 1980). It can also be described in a positive sense as a report from a consumer providing documentation…

Hakim Israel kuno Kitab Yosua:Yosua Kitab Hakim-hakim yoi: Otniel • Ehud • Samgar • Debora • Barak† • Gideon • Abimelekh† • Tola • Yair • Yefta • Ebzan • Elon • Abdon • Simson Kitab 1 Samuel:Eli • Samuel †Tidak resmi diangkat sebagai hakim Kotak ini: lihatbicarasunting Lukisan pertarungan Simson dengan seekor singa yang dilukis Lucas Cranach the Elder pada tahun 1525. Simson (Ibrani: שִׁמְשׁוֹן Šimšon, Tiberias Šimšôn, Arab: شمشون Syamsyun/Sa…

Pour les articles homonymes, voir Argentin. Moreno ArgentinMoreno Argentin en 1987InformationsSurnom Il MaestroNaissance 17 décembre 1960 (63 ans)San Donà di PiaveNationalité italienneÉquipes amateurs 1979SC La Nuova Baggio-San Siro01.1980-09.1980SC La Nuova Baggio-CappÉquipes professionnelles 10.1980-12.1980Mobili San Giacomo-Benotto 1981-1982 Sammontana-Benotto1983-1984 Sammontana-Campagnolo1985-1986 Sammontana-Bianchi1987-1989 Gewiss-Bianchi 1990-1992 Ariostea 1993 Mecair-Ballan 199…

Kwadwo Asamoah Asamoah pemanasan bersama Juventus, Agustus 2014Informasi pribadiNama lengkap Kwadwo AsamoahTanggal lahir 9 Desember 1988 (umur 35)Tempat lahir Accra, GhanaTinggi 173 cm (5 ft 8 in)[1]Posisi bermain Gelandang kiri, Bek kiri,Gelandang tengahInformasi klubKlub saat ini CagliariNomor 19Karier junior2005–2006 Kaaseman2006–2007 Liberty Professionals2008 Bellinzona2008 → TorinoKarier senior*Tahun Tim Tampil (Gol)2008–2012 Udinese 114 (8)2012–2018 Ju…

YeniseyNama lengkapFutbolny KlubYenisey KrasýsdnoyarskdanJulukanbyBerdiri1937; 87 tahun lalu (1937)StadionStadion Sentral,Krasnoyarsk(Kapasitas: 22.500)PemilikKrai KrasnoyarskKetuaViktor KardashovLigaFNL4 444 Kostum kandang Kostum tandang FK Yenisey Krasnoyarsk (ФК Енисей Красноярск) adalah sebuah tim sepak bola Rusia yang berasal dari Krasnoyarsk. Tim ini bermain di Liga Sepak Bola Nasional Rusia, kompetisi kasta kedua Rusia.1300watt Sejarah Tim ini didirikan pada 1937 d…

Village in Illinois, United StatesGiffordVillageA picture of Gifford's Main StreetMotto: America's HometownGiffordLocation within Champaign CountyShow map of Champaign County, IllinoisGiffordGifford (Illinois)Show map of IllinoisCoordinates: 40°18′28″N 88°01′17″W / 40.30778°N 88.02139°W / 40.30778; -88.02139CountryUnited StatesStateIllinoisCountyChampaignGovernment • Village presidentAdam Pannbacker[citation needed]Area[1] …

Cet article est une ébauche concernant une localité tchèque. Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants. Hevlín Centre de Hevlín.   Administration Pays Tchéquie Région Moravie-du-Sud District Znojmo Région historique Moravie Code postal 671 69 Démographie Population 1 437 hab. (2019) Densité 53 hab./km2 Géographie Coordonnées 48° 45′ 07″ nord, 16° 22′&#…

  لمعانٍ أخرى، طالع نيوبورت (توضيح). نيوبورت     الإحداثيات 44°56′39″N 72°12′16″W / 44.9442°N 72.2044°W / 44.9442; -72.2044   [1] تاريخ التأسيس 1918  تقسيم إداري  البلد الولايات المتحدة[2][3]  التقسيم الأعلى مقاطعة أورليانز  عاصمة لـ مقاطعة أورليانز  خص…

Cet article est une ébauche concernant l’automobile. Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants. Pour les articles homonymes, voir Yeoman (homonymie). Une Chevrolet Yeoman La Chevrolet Yeoman est un break quatre portes à hayon produit par la marque américaine Chevrolet sur la base de la Chevrolet Delray lors de l'unique millésime 1958 en remplacement de la série populaire Chevrolet 210 produite de 1953 à…

Polish lawyer and politician Marek BiernackiMinister of JusticeIn office6 May 2013 – 22 September 2014PresidentBronisław KomorowskiPrime MinisterDonald TuskPreceded byJarosław GowinSucceeded byCezary GrabarczykMinister of Interior and AdministrationIn office7 October 1999 – 19 October 2001PresidentAleksander KwaśniewskiPrime MinisterJerzy BuzekMember of the SejmIncumbentAssumed office 25 September 2005 Personal detailsBorn (1959-04-28) 28 April 1959 (age 64)Sopo…

Stasiun Takanosu鷹ノ巣駅 (鷹巣駅)Stasiun Takanosu pada Oktober 2011LokasiMatsubachō, Kitaakita-shi, Akita-ken 018-3321JepangKoordinat40°13′55.39″N 140°22′11.49″E / 40.2320528°N 140.3698583°E / 40.2320528; 140.3698583Koordinat: 40°13′55.39″N 140°22′11.49″E / 40.2320528°N 140.3698583°E / 40.2320528; 140.3698583Operator JR East Akita Nairiku Jūkan Railway Jalur ■ Jalur Utama Ōu ■ Jalur Nariku Letak379.5 kilometer …

US law addressing ex-Confederate states' readmission to the Union (1867–68) This article is about the U.S. legislation enacted between 1867 and 1868. For the history of the Southern United States from 1863 until 1877, see Reconstruction era. For other uses, see Reconstruction (disambiguation). The Reconstruction Acts, or the Military Reconstruction Acts (March 2, 1867, 14 Stat. 428-430, c.153; March 23, 1867, 15 Stat. 2-5, c.6; July 19, 1867, 15 Stat. 14-16, c.30; and March 11, 1868, 15 Stat. …

  هذه المقالة عن مادة الكرتون. لمعانٍ أخرى، طالع كرتون (توضيح). الكرتون (بالإنجليزية: Cardboard)‏ هو الورق يصنع من الألياف السميكة، وله استخدامات عديدة منها في تصنيع علب الكرتون.[1][2][3] استخدامات الكرتون علبة كرتونية علبة الكرتون هي نوع من الصناديق أو العلب، المصن…

Kembali kehalaman sebelumnya