Editing Cubic graph (section)

==Algorithms and complexity==
Several researchers have studied the complexity of [[exponential time]] algorithms restricted to cubic graphs. For instance, by applying [[dynamic programming]] to a [[path decomposition]] of the graph, Fomin and Høie showed how to find their [[maximum independent set]]s in time 2<sup>''n''/6&nbsp;+&nbsp;o(''n'')</sup>.<ref name="fh06"/> The [[travelling salesman problem]] in cubic graphs can be solved in time O(1.2312<sup>''n''</sup>) and polynomial space.<ref name="XiaoNag13">{{citation
 |first1=Mingyu
 |last1=Xiao
 |first2=Hiroshi
 |last2=Nagamochi
 |series=Lecture Notes in Computer Science
 |publisher=Springer-Verlag
 |title=Theory and Applications of Models of Computation
 |contribution=An Exact Algorithm for TSP in Degree-3 Graphs via Circuit Procedure and Amortization on Connectivity Structure
 |year=2013
 |doi=10.1007/978-3-642-38236-9_10
 |volume=7876
 |pages=96–107
 |isbn=978-3-642-38236-9|arxiv=1212.6831
 }}.</ref><ref>{{citation
 |  first1 = Mingyu | last1 = Xiao
 |  first2 = Hiroshi | last2 = Nagamochi
 | arxiv = 1212.6831 
 | title = An Exact Algorithm for TSP in Degree-3 Graphs Via Circuit Procedure and Amortization on Connectivity Structure
 | journal = Algorithmica
 | year = 2012| volume = 74
 | issue = 2
 | pages = 713–741
 | doi = 10.1007/s00453-015-9970-4
 |bibcode = 2012arXiv1212.6831X| s2cid = 7654681
 }}.</ref>

Several important graph optimization problems are [[APX|APX hard]], meaning that, although they have [[approximation algorithm]]s whose [[approximation ratio]] is bounded by a constant, they do not have [[polynomial time approximation scheme]]s whose approximation ratio tends to 1 unless [[P vs NP problem|P=NP]]. These include the problems of finding a minimum [[vertex cover]], [[maximum independent set]], minimum [[dominating set]], and [[maximum cut]].<ref>{{citation
 | last1 = Alimonti | first1 = Paola
 | last2 = Kann | first2 = Viggo
 | doi = 10.1016/S0304-3975(98)00158-3
 | issue = 1–2
 | journal = [[Theoretical Computer Science (journal)|Theoretical Computer Science]]
 | pages = 123–134
 | title = Some APX-completeness results for cubic graphs
 | volume = 237
 | year = 2000| doi-access = free
 }}.</ref>
The [[Crossing number (graph theory)|crossing number]] (the minimum number of edges which cross in any [[graph drawing]]) of a cubic graph is also [[NP-hard]] for cubic graphs but may be approximated.<ref name="Hlinny2006">{{citation|first=Petr|last=Hliněný|title=Crossing number is hard for cubic graphs|journal=[[Journal of Combinatorial Theory]]|series=Series B|volume=96|issue=4|pages=455–471|year=2006|doi=10.1016/j.jctb.2005.09.009|doi-access=free}}.</ref>
The [[Travelling Salesman Problem]] on cubic graphs has been proven to be [[NP-hard]] to approximate to within any factor less than 1153/1152.<ref>{{citation
 |  first1 = Marek | last1 = Karpinski
 |  first2 = Richard | last2 = Schmied
 | arxiv = 1304.6800 
 | title = Approximation Hardness of Graphic TSP on Cubic Graphs
 | year = 2013|bibcode = 2013arXiv1304.6800K}}.</ref>