List H-Coloring a Graph by Removing Few Vertices
| Autor: | Dániel Marx, László Egri, Rajesh Chitnis |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2013 |
| Předmět: |
Discrete mathematics
FOS: Computer and information sciences General Computer Science Applied Mathematics Vertex cover Neighbourhood (graph theory) 0102 computer and information sciences 02 engineering and technology 01 natural sciences Computer Science Applications Combinatorics New digraph reconstruction conjecture 010201 computation theory & mathematics Circular-arc graph Computer Science - Data Structures and Algorithms 0202 electrical engineering electronic engineering information engineering Bipartite graph Iterative compression 020201 artificial intelligence & image processing Graph homomorphism Data Structures and Algorithms (cs.DS) Complement graph Mathematics |
| Popis: | In the deletion version of the list homomorphism problem, we are given graphs G and H, a list $$L(v)\subseteq V(H)$$L(v)⊆V(H) for each vertex $$v\in V(G)$$vźV(G), and an integer k. The task is to decide whether there exists a set $$W \subseteq V(G)$$W⊆V(G) of size at most k such that there is a homomorphism from $$G {\setminus } W$$G\W to H respecting the lists. We show that DL-Hom($${H}$$H), parameterized by k and |H|, is fixed-parameter tractable for any $$(P_6,C_6)$$(P6,C6)-free bipartite graph H; already for this restricted class of graphs, the problem generalizes Vertex Cover, Odd Cycle Transversal, and Vertex Multiway Cut parameterized by the size of the cutset and the number of terminals. We conjecture that DL-Hom($${H}$$H) is fixed-parameter tractable for the class of graphs H for which the list homomorphism problem (without deletions) is polynomial-time solvable; by a result of Feder et al. (Combinatorica 19(4):487---505, 1999), a graph H belongs to this class precisely if it is a bipartite graph whose complement is a circular arc graph. We show that this conjecture is equivalent to the fixed-parameter tractability of a single fairly natural satisfiability problem, Clause Deletion Chain-SAT. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|