László Egri (SFU)
14/03/14 12:30 Talks
List H-Coloring a Graph by Removing Few Vertices
Speaker:
László Egri (Concordia University and SFU)
Abstract:
In the deletion version of the list homomorphism problem, we are given graphs G and H, a list L(v) that is a subset of V(H) for each vertex v of G, and an integer k. The task is to decide whether there exists a subset W of V(G) of size at most k such that there is a homomorphism from G \ W to H respecting the lists. We show that DL-Hom(H), parameterized by k and |H|, is fixed-parameter tractable for any (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) is fixed-parameter tractable for the class of graphs H for which the list homomorphism problem (without deletions) is polynomial-time solvable. We show that this conjecture is equivalent to the fixed-parameter tractability of a single fairly natural satisfiability problem, Clause Deletion Chain-SAT.
Date:
Friday, March 14, 2014
Time:
12:30 pm - 13:30 pm
Location:
TASC1 Building, Room No. 9204, Simon Fraser University, Burnaby
László Egri (Concordia University and SFU)
Abstract:
In the deletion version of the list homomorphism problem, we are given graphs G and H, a list L(v) that is a subset of V(H) for each vertex v of G, and an integer k. The task is to decide whether there exists a subset W of V(G) of size at most k such that there is a homomorphism from G \ W to H respecting the lists. We show that DL-Hom(H), parameterized by k and |H|, is fixed-parameter tractable for any (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) is fixed-parameter tractable for the class of graphs H for which the list homomorphism problem (without deletions) is polynomial-time solvable. We show that this conjecture is equivalent to the fixed-parameter tractability of a single fairly natural satisfiability problem, Clause Deletion Chain-SAT.
Date:
Friday, March 14, 2014
Time:
12:30 pm - 13:30 pm
Location:
TASC1 Building, Room No. 9204, Simon Fraser University, Burnaby