Content deleted Content added
→References: +authorlinks |
3 easier than 4 |
||
Line 22:
{{harvtxt|Kratochvíl|1991b}} showed string graph recognition to be [[NP-hard]], but was not able to show that it could be solved in [[NP (complexity)|NP]].{{sfnp|Kratochvíl|1991b}} One barrier to solving the problem in NP is that, for some string graphs, all systems of curves that realize the graph have an exponential number of crossings, so an explicit realization cannot be used as a polynomial-size witness for the graph being a string graph.{{sfnp|Kratochvíl|Matoušek|1991}} Instead, subsequent research in this area focused on compressed descriptions of realizations in terms of the sequences of crossings on each string, described using the theory of [[formal language]]s. After intermediate results by {{harvtxt|Schaefer|Štefankovič|2001}} and {{harvtxt|Pach|Tóth|2002}}, {{harvtxt|Schaefer|Sedgwick|Štefankovič|2003}} completed the proof that the problem is in NP, and therefore is [[NP-complete]].{{sfnp|Schaefer|Sedgwick|Štefankovič|2003}}
{{harvtxt|Ehrlich|Even|Tarjan|1976}} showed that testing whether a string graph is <math>k</math>-colorable is NP-complete, for every <math>k\ge 3</math>, and even when restricted to graphs with a given string representation consisting of straight line segments.{{sfnp|Ehrlich|Even|Tarjan|1976}} 3-colorings of string graphs, when they exist, can be found in the subexponential time bound <math>2^{O(n^{2/3}\log n)}</math>, but a similarly fast time for higher numbers of colorings is unlikely, under standard complexity-theoretic assumptions: an algorithm for 4-coloring in time <math>2^{o(n)}</math> would contradict the [[exponential time hypothesis]].{{sfnp|Bonnet|Rzążewski|2019}}
==Other results==
Line 47:
| pmid=16590553
| pmc=222769| doi-access = free }}.
*{{citation
| last1 = Bonnet | first1 = Édouard
| last2 = Rzążewski | first2 = Paweł
| doi = 10.1007/s00453-019-00568-7
| issue = 7
| journal = Algorithmica
| mr = 3948280
| pages = 3047–3073
| title = Optimality program in segment and string graphs
| volume = 81
| year = 2019}}.
*{{citation
| last1 = Chalopin | first1 = J. | last2 = Gonçalves | first2 = D. | last3 = Ochem | first3 = P.
| |||