List H-coloring a graph by removing few vertices

DOI10.1007/s00453-016-0139-6zbMath1361.05085arXiv1308.1068OpenAlexW1836455089MaRDI QIDQ527415

Rajesh Chitnis, László Egri, Dániel Marx

Publication date: 11 May 2017

Published in: Algorithmica, Lecture Notes in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

graph homomorphismfixed-parameter tractabilityiterative compressiontreewidth reductionshadow removal

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Transversal (matching) theory (05D15) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (13)

Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity ⋮ Parameterized algorithms for min-max multiway cut and list digraph homomorphism ⋮ Parameterized complexity of weighted multicut in trees ⋮ Parameterized complexity of multicut in weighted trees ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ List homomorphism: beyond the known boundaries ⋮ Unnamed Item ⋮ On Weighted Graph Separation Problems and Flow Augmentation ⋮ Multi-Budgeted Directed Cuts ⋮ Optimal data reduction for graph coloring using low-degree polynomials ⋮ Graph isomorphism restricted by lists ⋮ The parameterized complexity of the minimum shared edges problem ⋮ Multi-budgeted directed cuts

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• The complexity of the list homomorphism problem for graphs
• Finding odd cycle transversals.
• Parameterized graph separation problems
• List homomorphisms of graphs with bounded degrees
• Almost 2-SAT is fixed-parameter tractable
• Circular-arc graphs with clique cover number two
• On the complexity of H-coloring
• List homomorphisms to reflexive graphs
• Clustering with local restrictions
• List homomorphisms and circular arc graphs
• Parametrized complexity theory.
• Minimum cost and list homomorphisms to semicomplete digraphs
• Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable
• Parameterized Tractability of Multiway Cut with Parity Constraints
• Fixed-Parameter Tractability of Directed Multiway Cut Parameterized by the Size of the Cutset
• On Multiway Cut Parameterized above Lower Bounds
• Finding small separators in linear time via treewidth reduction
• Query evaluation via tree-decompositions
• On Parameterized Approximability
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Descriptive Complexity of List H-Coloring Problems in Logspace: A Refined Dichotomy
• Bi‐arc graphs and the complexity of list homomorphisms
• Faster Parameterized Algorithms Using Linear Programming
• Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset
• Fixed-Parameter Tractability of Multicut in Directed Acyclic Graphs

This page was built for publication: List H-coloring a graph by removing few vertices