graph theory In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, an odd cycle transversal of an

undirected graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...

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 In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V ar ...

as the remaining

induced subgraph In the mathematical field of graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and ''all'' of the edges (from the original graph) connecting pairs of vertices in that subset. Definit ...

Relation to vertex cover

A given

n

-vertex graph

G

has an odd cycle transversal of size

k

, if and only if the

Cartesian product of graphs Cartesian means of or relating to the French philosopher René Descartes—from his Latinized name ''Cartesius''. It may refer to: Mathematics *Cartesian closed category, a closed category in category theory *Cartesian coordinate system, modern ...

G\square K_2

(a graph consisting of two copies of

G

, with corresponding vertices of each copy connected by the edges of a

perfect matching In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph , a perfect matching in is a subset of edge set , such that every vertex in the vertex set is adjacent to exactly ...

) has a

vertex cover In graph theory, a vertex cover (sometimes node cover) of a graph is a set of vertices that includes at least one endpoint of every edge of the graph. In computer science, the problem of finding a minimum vertex cover is a classical optimiza ...

of size

n+k

. 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

G\square K_2

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.

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 In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...

, 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. The equivalence between the odd cycle transversal and vertex cover problems has been used to develop

fixed-parameter tractable In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to ''multiple'' parameters of the input or output. ...

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

k

. The development of these algorithms led to the method of

iterative compression In computer science, iterative compression is an algorithmic technique for the design of fixed-parameter tractable algorithms, in which one element (such as a vertex of a graph) is added to the problem in each step, and a small solution for the pr ...

, a more general tool for many other parameterized algorithms. The parameterized algorithms known for these problems take nearly-linear time for any fixed value of

k

. Alternatively, with polynomial dependence on the graph size, the dependence on

k

can be made as small as

2.3146^k

. In contrast, the analogous problem for

directed graph In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs. Definition In formal terms, a directed graph is an ordered pai ...

s does not admit a fixed-parameter tractable algorithm under standard complexity-theoretic assumptions.

References

{{reflist, refs= {{citation , last1 = Lokshtanov , first1 = Daniel , last2 = Ramanujan , first2 = M. S. , last3 = Saurabh , first3 = Saket , last4 = Zehavi , first4 = Meirav , arxiv = 1704.04249 , title = Parameterized complexity and approximability of directed odd cycle transversal , year = 2017, bibcode = 2017arXiv170404249L {{citation , last1 = Garey , first1 = Michael R. , author1-link = Michael Garey , last2 = Johnson , first2 = David S. , author2-link = David S. Johnson , contribution = GT21: Induced subgraph with property Π , page = 195 , publisher = W. H. Freeman , title = Computers and Intractability: A Guide to the Theory of NP-completeness , year = 1979 {{citation , last1 = Kawarabayashi , first1 = Ken-ichi , author1-link = Ken-ichi Kawarabayashi , last2 = Reed , first2 = Bruce , author2-link = Bruce Reed (mathematician) , contribution = An (almost) linear time algorithm for odd cycles transversal , doi = 10.1137/1.9781611973075.31 , location = Philadelphia, PA , mr = 2809682 , pages = 365–378 , publisher = SIAM , title = Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms , year = 2010, isbn = 978-0-89871-701-3 , citeseerx = 10.1.1.215.2581 {{citation , last1 = Lokshtanov , first1 = Daniel , last2 = Narayanaswamy , first2 = N. S. , last3 = Raman , first3 = Venkatesh , last4 = Ramanujan , first4 = M. S. , last5 = Saurabh , first5 = Saket , doi = 10.1145/2566616 , issue = 2 , journal = ACM Transactions on Algorithms , mr = 3283570 , page = Art. 15, 31 , title = Faster parameterized algorithms using linear programming , volume = 11 , year = 2014, arxiv = 1203.0833 {{citation , last1 = Cygan , first1 = Marek , last2 = Fomin , first2 = Fedor V. , last3 = Kowalik , first3 = Lukasz , last4 = Lokshtanov , first4 = Daniel , last5 = Marx , first5 = Dániel , last6 = Pilipczuk , first6 = Marcin , last7 = Pilipczuk , first7 = Michal , last8 = Saurabh , first8 = Saket , doi = 10.1007/978-3-319-21275-3 , mr = 3380745 , pages = 64–65 , publisher = Springer , title = Parameterized Algorithms , year = 2015, isbn = 978-3-319-21274-6 {{citation , last = Yannakakis , first = Mihalis , author-link = Mihalis Yannakakis , contribution = Node-and edge-deletion NP-complete problems , doi = 10.1145/800133.804355 , pages = 253–264 , title = Proceedings of the 10th ACM Symposium on Theory of Computing (STOC '78) , year = 1978, title-link = Symposium on Theory of Computing Graph theory objects Computational problems in graph theory

Relation to vertex cover

Algorithms and complexity

See also

References