2023/02/27 by Falko Hegerfeld, Stefan Kratsch, Hegerfeld, Falko +1 · 2 citations
Computer Science · Biochemistry, Genetics and Molecular Biology · Engineering · #Complexity and Algorithms in Graphs #Advanced biosensing and bioanalysis techniques #Ferroelectric and Negative Capacitance Devices
paper · pdf · doi:10.48550/arxiv.2302.14128
We study connectivity problems from a fine-grained parameterized perspective. Cygan et al. (TALG 2022) obtained algorithms with single-exponential running time αtw nO(1) for connectivity problems parameterized by treewidth (tw) by introducing the cut-and-count-technique, which reduces connectivity problems to locally checkable counting problems. In addition, the bases α were proven to be optimal assuming the Strong Exponential-Time Hypothesis (SETH). As only sparse graphs may admit small treewidth, these results do not apply to graphs with dense structure. A well-known tool to capture dense structure is the modular decomposition, which recursively partitions the graph into modules whose members have the same neighborhood outside of the module. Contracting the modules yields a quotient graph describing the adjacencies between modules. Measuring the treewidth of the quotient graph yields the parameter modular-treewidth, a natural intermediate step between treewidth and clique-width. We obtain the first tight running times for connectivity problems parameterized by modular-treewidth. For some problems the obtained bounds are the same as relative to treewidth, showing that we can deal with a greater generality in input structure at no cost in complexity. We obtain the following randomized algorithms for graphs of modular-treewidth k, given an appropriate decomposition: Steiner Tree can be solved in time 3k nO(1), Connected Dominating Set can be solved in time 4k nO(1), Connected Vertex Cover can be solved in time 5k nO(1), Feedback Vertex Set can be solved in time 5k nO(1). The first two algorithms are tight due to known results and the last two algorithms are complemented by new tight lower bounds under SETH.