On structural parameterizations of hitting set: hitting paths in graphs using 2-SAT

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Citation (Scopus)
57 Downloads (Pure)

Abstract

Hitting Set is a classic problem in combinatorial optimization. Its input consists of a set system F over a finite universe U and an integer t; the question is whether there is a set of t elements that intersects every set in F. The Hitting Set problem parameterized by the size of the solution is a well-known W[2]-complete problem in parameterized complexity theory. In this paper we investigate the complexity of Hitting Set under various structural parameterizations of the input. Our starting point is the folklore result that Hitting Set is polynomial-time solvable if there is a tree T on vertex set U such that the sets in F induce connected subtrees of T. We consider the case that there is a treelike graph with vertex set U such that the sets in F induce connected subgraphs; the parameter of the problem is a measure of how treelike the graph is. Our main positive result is an algorithm that, given a graph G with cyclomatic number k, a collection P of simple paths in G, and an integer t, determines in time 2^{5k} (|G| +|P|)^O(1) whether there is a vertex set of size t that hits all paths in P. It is based on a connection to the 2-SAT problem in multiple valued logic. For other parameterizations we derive W[1]-hardness and para-NP-completeness results.
Original languageEnglish
Title of host publicationGraph-Theoretic Concepts in Computer Science : 41st International Workshop, WG 2015, Garching, Germany, June 17-19, 2015
EditorsE.W. Mayr
Place of PublicationBerlin
PublisherSpringer
Pages472-486
ISBN (Electronic)978-3-662-53174-7
ISBN (Print)978-3-662-53173-0
DOIs
Publication statusPublished - 5 Aug 2016
Event41st International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2015), June 17-19, 2015, Munich, Germany - Munich, Germany
Duration: 17 Jun 201519 Jun 2015
http://wwwmayr.in.tum.de/konferenzen/WG2015/

Publication series

NameLecture Notes in Computer Science
Volume9224
ISSN (Print)0302-9743

Workshop

Workshop41st International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2015), June 17-19, 2015, Munich, Germany
Abbreviated titleWG 2015
CountryGermany
CityMunich
Period17/06/1519/06/15
Internet address

    Fingerprint

Cite this

Jansen, B. M. P. (2016). On structural parameterizations of hitting set: hitting paths in graphs using 2-SAT. In E. W. Mayr (Ed.), Graph-Theoretic Concepts in Computer Science : 41st International Workshop, WG 2015, Garching, Germany, June 17-19, 2015 (pp. 472-486). (Lecture Notes in Computer Science; Vol. 9224). Berlin: Springer. https://doi.org/10.1007/978-3-662-53174-7_33