Subexponential algorithms for variants of the homomorphism problem in string graphs

DOI10.1016/j.jcss.2019.12.004zbMath1435.68243arXiv1809.09345OpenAlexW2972759174WikidataQ126434548 ScholiaQ126434548MaRDI QIDQ2301363

Karolina Okrasa, Paweł Rzążewski

Publication date: 24 February 2020

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1809.09345

zbMATH Keywords

graph homomorphismstring graphssegment graphssubexponential algorithmsETH

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (11)

Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity ⋮ List covering of regular multigraphs ⋮ Degeneracy of \(P_t\)-free and \(C_{\geq t}\)-free graphs with no large complete bipartite subgraphs ⋮ An algorithmic framework for locally constrained homomorphisms ⋮ Computing list homomorphisms in geometric intersection graphs ⋮ List covering of regular multigraphs with semi-edges ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Finding Large $H$-Colorable Subgraphs in Hereditary Graph Classes ⋮ On cycle transversals and their connected variants in the absence of a small linear forest

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On strongly planar not-all-equal 3SAT
• Fixed points, Nash equilibria, and the existential theory of the reals
• \(k-L(2,1)\)-labelling for planar graphs is NP-complete for \(k\geq 4\)
• Exact algorithms for \(L(2,1)\)-labeling of graphs
• The complexity of locally injective homomorphisms
• A complete complexity classification of the role assignment problem
• Cantor--Bernstein type theorem for locally constrained graph homomorphisms
• String graphs. II: Recognizing string graphs is NP-hard
• String graphs. I: The number of critical nonstring graphs is infinite
• String graphs requiring exponential representations
• Intersection graphs of segments
• Independent feedback vertex set for \(P_5\)-free graphs
• On the injective chromatic number of graphs
• Integer realizations of disk and segment graphs
• List homomorphisms and circular arc graphs
• On simplified NP-complete variants of \textsc{Monotone} 3\textsc{-Sat}
• Subexponential algorithms for variants of homomorphism problem in string graphs
• \(H\)-colouring \(P_t\)-free graphs in subexponential time
• Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree
• A dichotomy for minimum cost graph homomorphisms
• A Separator Theorem for String Graphs and its Applications
• Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams
• Locally Injective Graph Homomorphism: Lists Guarantee Dichotomy
• A Separator Theorem for Planar Graphs
• Labelling Graphs with a Condition at Distance 2
• Separators for sphere-packings and nearest neighbor graphs
• Coloring the square of a planar graph
• Geometric separation and exact solutions for the parameterized independent set problem on disk graphs
• Finding, Hitting and Packing Cycles in Subexponential Time on Unit Disk Graphs
• Every planar graph is the intersection graph of segments in the plane
• On the Exact Complexity of Hamiltonian Cycle and q-Colouring in Disk Graphs
• Near-Optimal Separators in String Graphs
• On Injective Colourings of Chordal Graphs
• Mathematical Foundations of Computer Science 2005
• Optimality program in segment and string graphs
• Recognizing string graphs in NP
• On the complexity of \(k\)-SAT

This page was built for publication: Subexponential algorithms for variants of the homomorphism problem in string graphs