List H-coloring a graph by removing few vertices

Research output: Contribution to journalArticlepeer-review

Standard

List H-coloring a graph by removing few vertices. / Chitnis, Rajesh; Egri, László; Marx, Dániel.

In: Algorithmica, Vol. 78, No. 1, 05.2017, p. 110-146.

Research output: Contribution to journalArticlepeer-review

Harvard

APA

Vancouver

Author

Chitnis, Rajesh ; Egri, László ; Marx, Dániel. / List H-coloring a graph by removing few vertices. In: Algorithmica. 2017 ; Vol. 78, No. 1. pp. 110-146.

Bibtex

@article{d86b9ed4cd5c4f77b849acffd448f017,
title = "List H-coloring a graph by removing few vertices",
abstract = "In the deletion version of the list homomorphism problem, we are given graphs G and H, a list L(v) ⊆ V(H) for each vertex v∈ V(G) , and an integer k. The task is to decide whether there exists a set W⊆ 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; 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.",
keywords = "Fixed-parameter tractability, Graph homomorphism, Iterative compression, Shadow removal, Treewidth reduction",
author = "Rajesh Chitnis and L{\'a}szl{\'o} Egri and D{\'a}niel Marx",
year = "2017",
month = may,
doi = "10.1007/s00453-016-0139-6",
language = "English",
volume = "78",
pages = "110--146",
journal = "Algorithmica",
issn = "0178-4617",
publisher = "Springer",
number = "1",

}

RIS

TY - JOUR

T1 - List H-coloring a graph by removing few vertices

AU - Chitnis, Rajesh

AU - Egri, László

AU - Marx, Dániel

PY - 2017/5

Y1 - 2017/5

N2 - In the deletion version of the list homomorphism problem, we are given graphs G and H, a list L(v) ⊆ V(H) for each vertex v∈ V(G) , and an integer k. The task is to decide whether there exists a set W⊆ 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; 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.

AB - In the deletion version of the list homomorphism problem, we are given graphs G and H, a list L(v) ⊆ V(H) for each vertex v∈ V(G) , and an integer k. The task is to decide whether there exists a set W⊆ 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; 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.

KW - Fixed-parameter tractability

KW - Graph homomorphism

KW - Iterative compression

KW - Shadow removal

KW - Treewidth reduction

UR - http://www.scopus.com/inward/record.url?scp=85014817745&partnerID=8YFLogxK

U2 - 10.1007/s00453-016-0139-6

DO - 10.1007/s00453-016-0139-6

M3 - Article

AN - SCOPUS:85014817745

VL - 78

SP - 110

EP - 146

JO - Algorithmica

JF - Algorithmica

SN - 0178-4617

IS - 1

ER -