List H-coloring a graph by removing few vertices
- Submitting institution
-
The University of Birmingham
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 84877628
- Type
- D - Journal article
- DOI
-
10.1007/s00453-016-0139-6
- Title of journal
- Algorithmica
- Article number
- -
- First page
- 110
- Volume
- 78
- Issue
- 1
- ISSN
- 0178-4617
- Open access status
- Out of scope for open access requirements
- Month of publication
- April
- Year of publication
- 2016
- URL
-
-
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
2
- Research group(s)
-
-
- Citation count
- 4
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- This paper provided a powerful "hammer" by relating the polynomial time solvability of the List Homomorphism problem to the fixed-parameter tractability (FPT) of its deletion version. An extended abstract of the paper co-won the Best Paper Award at the 21st Annual European Symposium on Algorithms (ESA 2013). The meta-algorithm designed in this paper encompasses the previously known FPT algorithms for various fundamental problems such as Vertex Cover, Odd Cycle Transversal and Multiway Cut. Several FTP techniques such as treewidth reduction, iterative compression and shadow removal are used in conjunction to determine the main outcome of the paper.
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -