FPT Approximations for Connected Maximum Coverage

Inamdar, Tanmay; Jana, Satyabrata; Kundu, Madhumita; Lokshtanov, Daniel; Saurabh, Saket; Zehavi, Meirav

doi:10.4230/LIPIcs.ITCS.2026.80

FPT Approximations for Connected Maximum Coverage

Tanmay Inamdar

Indian Institute of Technology Jodhpur, India Satyabrata Jana

University of Warwick, Coventry, UK Madhumita Kundu

University of Bergen, Norway Daniel Lokshtanov

Department of Computer Science, University of California Santa Barbara, CA, USA Saket Saurabh

The Institute of Mathematical Sciences, HBNI, Chennai, India
University of Bergen, Norway Meirav Zehavi

Ben-Gurion University of the Negev, Be’er-Sheva, Israel

Abstract

We revisit connectivity-constrained coverage through a unifying model, Partial Connected Red-Blue Dominating Set (PartialConRBDS). Given a bipartite graph $G=(R\cup B,E)$ with red vertices $R$ and blue vertices $B$ , an auxiliary connectivity graph $G_{\mathrm{conn}}$ on $R$ , and integers $k, t$ , the task is to find a set $S\subseteq R$ with $|S|\leq k$ such that $G_{\mathrm{conn}}[S]$ is connected and $S$ dominates at least $t$ blue vertices. This formulation captures connected variants of Maximum Coverage [Hochbaum–Rao, Inf. Proc. Lett., 2020; D’Angelo–Delfaraz, AAMAS 2025], Partial Vertex Cover, and Partial Dominating Set [Khuller et al., SODA 2014; Lamprou et al., TCS 2021] via standard encodings.

Limits to parameterized tractability.

PartialConRBDS is $\mathsf{W[1]}$ -hard parameterized by $k$ even under strong restrictions: it remains hard when $G_{\mathrm{conn}}$ is a clique or a star and the incidence graph $G$ is $3$ -degenerate, or when $G$ is $K_{2,2}$ -free.

Inapproximability.

For every $\varepsilon>0$ , there is no polynomial-time $(1,\,1-\frac{1}{e}+\varepsilon)$ -approximation unless $\mathsf{P}=\mathsf{NP}$ . Moreover, under ETH, no algorithm running in $f(k)\cdot n^{o(k)}$ time achieves an $g(k)$ -approximation for $k$ for any computable function $g(\cdot)$ , or for any $\varepsilon>0$ , a $(1-\frac{1}{e}+\varepsilon)$ -approximation for $t$ .

Graphical special cases.

Partial Connected Dominating Set is $\mathsf{W[2]}$ -hard parameterized by $k$ and inherits the same ETH-based $f(k)\cdot n^{o(k)}$ inapproximability bound as above; Partial Connected Vertex Cover is $\mathsf{W[1]}$ -hard parameterized by $k$ .

These hardness boundaries delineate a natural “sweet spot” for study: within appropriate structural restrictions on the incidence graph, one can still aim for fine-grained (FPT) approximations.
Our algorithms. We solve PartialConRBDS exactly by reducing it to Relaxed Directed Steiner Out-Tree in time $(2e)^{t}\cdot n^{\mathcal{O}(1)}$ . For biclique-free incidences (i.e., when $G$ excludes $K_{d,d}$ as an induced subgraph), we obtain two complementary parameterized schemes:

$\blacksquare$

An Efficient Parameterized Approximation Scheme (EPAS) running in time $2^{\mathcal{O}(k^{2}d/\varepsilon)}\cdot n^{\mathcal{O}(1)}$ that either returns a connected solution of size at most $k$ covering at least $(1-\varepsilon)t$ blue vertices, or correctly reports that no connected size- $k$ solution covers $t$ ; and
$\blacksquare$

A Parameterized Approximation Scheme (PAS) running in time $2^{\mathcal{O}(kd(k^{2}+\log d))}\cdot n^{\mathcal{O}(1/\varepsilon)}$ that either returns a connected solution of size at most $(1+\varepsilon)k$ covering at least $t$ blue vertices, or correctly reports that no connected size- $k$ solution covers $t$ .

Together, these results chart the boundary between hardness and FPT-approximability for connectivity-constrained coverage.

Keywords and phrases:

Partial Dominating Set, Connectivity, Maximum Coverage, FPT Approximation, Fixed-parameter Tractability

Funding:

Tanmay Inamdar: The author is supported by Anusandhan National Research Foundation (ANRF), grant number ANRF/ECRG/2024/004144/PMS, and IIT Jodhpur Research Initiation Grant, grant number I/RIG/TNI/20240072.

Satyabrata Jana: Supported by the Engineering and Physical Sciences Research Council (EPSRC) via the project MULTIPROCESS (grant no. EP/V044621/1).

Daniel Lokshtanov: The author is supported by NSF grant 2505099: Collaborative Research: AF Medium: Structure and Quasi-Polynomial Time Algorithms.

Saket Saurabh: The author is supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No. 819416).

Meirav Zehavi: The author is supported by Israel Science Foundation (ISF), grant no. 1470/24, and by European Research Council (ERC) grant no. 101039913 (PARAPATH).

Copyright and License:

2012 ACM Subject Classification:

Mathematics of computing

\rightarrow

Graph algorithms ; Theory of computation

\rightarrow

Graph algorithms analysis ; Theory of computation

\rightarrow

Parameterized complexity and exact algorithms

Editor:

Shubhangi Saraf

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

In the last decade, FPT approximation has enjoyed a tremendous amount of success in obtaining near-optimal approximations for NP-hard optimization problems that resist polynomial-time approximations, as well as exact FPT algorithms. Indeed, this paradigm has led to the best-known approximation guarantees for many fundamental problems, including Min $k$ -Cut [31], $k$ -Median/ $k$ -Means clustering [8], $k$ -Edge Separator [18], Balanced Separator [15], to mention a few. The field’s recent momentum owes much to the emergence of accompanying hardness-of-approximation frameworks in the FPT setting, which delineate the achievable frontier and indicate when to stop pursuing better ratios or faster schemes [25, 6, 42, 7, 28, 29, 20, 19, 2].

Possibly second only to clustering and treewidth, the strongest testament to the success of the FPT approximation paradigm lies in its applications to Max Coverage and its variants. In the classical Max Coverage problem, we are given a set system $(\mathcal{U},\mathcal{F})$ and a positive integer $k$ , where $\mathcal{U}$ is a universe of $n$ elements and $\mathcal{F}$ is a family of $m$ subsets of $\mathcal{U}$ . The goal is to select a subfamily $\mathcal{F}^{\prime}\subseteq\mathcal{F}$ of size $k$ that covers as many elements of $\mathcal{U}$ as possible. A well-known greedy algorithm achieves a tight $(1-1/e)$ -approximation [13, 21], and the problem is known to be W[2]-hard when parameterized by $k$ [14].

Recent results have established that this approximation factor remains tight even if one allows FPT running time. Specifically, Manurangsi [33] showed that assuming Gap-ETH, no algorithm can achieve an approximation ratio better than $(1-1/e)$ in time $f(k)\cdot(|\mathcal{U}|+|\mathcal{F}|)^{o(k)}$ , even with the promise that there exist $k$ sets that cover the entire universe. Very recently, this result was strengthened by Guruswami et al. [20] by weakening the assumption to ETH. Despite this barrier, significantly better results can be obtained for Max Coverage and its variants when the underlying set system has additional structural properties. This line of research was initiated by Marx [35], who gave an FPT $(1-\varepsilon)$ -approximation algorithm running in time $\mathcal{O}^{\star}(2^{\mathcal{O}(k^{2}/\varepsilon)})$ ¹¹1We use $\mathcal{O}^{\star}(\cdot)$ to suppress polynomial factors in the input size, i.e., $\mathcal{O}^{\star}(T)=T\cdot|I|^{\mathcal{O}(1)}$ , where $|I|$ denotes the input size. for the Partial Vertex Cover (PVC) problem. Here, the task is to select $k$ vertices in a graph that cover as many edges as possible – a special case of Max Coverage. Subsequent works extended this to more general settings. In particular, for set systems where each element appears in at most $d$ sets ( $d=2$ for PVC), the running time was improved to $\mathcal{O}^{\star}((d/\varepsilon)^{\mathcal{O}(k)})$ [40, 32]. More recently, Jain et al. [24] further generalized these results to $K_{d,d}$ -free set systems, where no $d$ sets share $d$ common elements.

Building on the success of FPT approximation for the vanilla Max Coverage, attention has shifted to coverage with additional constraints, a class of problems previously studied in the classical polynomial-time approximation regime. Many of these classical results have been extended to obtain stronger FPT approximations for coverage problems with fairness [23], matroid [39, 23], and capacity [30] constraints, when the underlying set systems are structurally well-behaved.

Connectivity Constraints.

Among the constrained variants, connectivity-constrained coverage has received considerable attention in the classical setting. Motivated from applications in sensor and social networks, Khuller et al. [26] introduced Connected Partial Dominating Set, where, given a graph $G$ , the goal is to find a minimum size connected subset $S\subseteq V(G)$ that dominates at least $t$ vertices. For this problem, they designed a polynomial-time $\mathcal{O}(\log\Delta)$ -approximation, where $\Delta$ is the maximum degree in $G$ . For the complementary problem, called Connected Budgeted Dominating Set – where the goal is to find a connected vertex-subset of size at most $k$ that dominates the maximum number of vertices – they designed an $\left(\frac{1}{12}(1-\frac{1}{e})\right)$ -approximation (this was also independently obtained in [27]). Subsequently, Hochbaum et al. [22] introduced a more general Connected Max Coverage problem, which is a variant of Max Coverage, where the selected sub-family needs to induce a connected subgraph in another connectivity graph additionally provided in the input. For this problem, they gave an $\left((1-\frac{1}{e})\cdot\max\left\{\frac{1}{R}-\frac{1}{k},\frac{1}{k}\right% \}\right)$ -approximation, where $R$ is the radius of the connectivity graph. Very recently, D’Angelo and Delfaraz [11] designed bicriteria approximations for the same problem; specifically, polylogarithmic approximations for the number of elements covered with a solution of size $(1+\varepsilon)k$ .

However, to the best of our knowledge, these problems have not yet been systematically explored within the parameterized approximation framework. The goal of our work is twofold:

1.

To formulate a general model of connectivity-constrained coverage that is expressive enough to capture a broad range of problems studied in the prior polynomial-time literature, and
2.

To develop new techniques within the FPT approximation paradigm for designing approximation schemes for the two fundamental minimization and maximization problems that naturally arise in this framework.

Our model separates the constraint layer – a companion graph $G_{\mathrm{conn}}$ that can enforce connectivity, independence/packing, or fault tolerance – from the coverage layer – the incidence bipartite graph $G_{\texttt{cov}}=(R\cup B,E)$ that represents the set-element incidences from a hypergraph. This separation lets us handle a wide range of set-system (hypergraph) families, including bounded-rank and biclique-free incidences, bounded VC-dimension and geometric ranges, as well as multi-coverage and weighted variants. In the next subsection, we formally define our model and demonstrate its expressivity by showing how previously studied problems can be naturally captured within this framework.

1.1 Our Model of Connectivity-Constrained Coverage

We introduce the following problem that is central to this work.

Partial Connected Red-Blue Dominating Set (PartialConRBDS)

Input: An instance $\mathcal{I}=(G_{\texttt{conn}},G_{\texttt{cov}},k,t)$ , where

$\blacksquare$

$G_{\texttt{conn}}=(R,E)$ is an arbitrary graph, called the connectivity graph,
$\blacksquare$

$G_{\texttt{cov}}=(R\uplus B,E^{\prime})$ is a bipartite graph, called the coverage graph, and
$\blacksquare$

$k$ and $t$ are non-negative integers.

Question: Does there exist a vertex subset $S\subseteq R$ such that,

(1)

$\big|S\big|\leq k$ ,
(2)

$G_{\texttt{conn}}[S]$ is connected, and
(3)

$\big|N_{G_{\texttt{cov}}}(S)\big|\geq t$ ?

Let us unpack the definition. The input consists of two graphs $G_{\texttt{conn}}$ and $G_{\texttt{cov}}$ , and two non-negative integers $k$ and $t$ . Here, $G_{\texttt{cov}}$ is a bipartite graph with vertex set $R\uplus B$ , that is to be thought of as the incidence graph of a set system – the “red side” ( $R$ ) corresponds to the set family $\mathcal{F}$ , and the “blue side” ( $B$ ) corresponds to the universe $\mathcal{U}$ , with an edge representing set-element containments. Notice that under this interpretation, Max Coverage corresponds to selecting a $k$ -sized subset of $R$ that dominates the maximum number of vertices in $B$ . Next, we have a connectivity graph $G_{\texttt{conn}}$ , whose vertex set is also $R$ . This graph is used to model the connectivity of the solution, i.e., a solution $S\subseteq R$ is required to induce a connected subgraph of $G_{\texttt{conn}}$ .

While the decision question asks whether there exists such a connected solution of size at most $k$ that dominates at least $t$ vertices in $B$ , two natural optimization variants stem from it: find a connected solution $S$ that

(i)

maximizes $|N_{G_{\texttt{cov}}}(S)|$ s.t. $|S|\leq k$ , and
(ii)

minimizes $|S|$ s.t. $|N_{G_{\texttt{cov}}}(S)|\geq t$ .

To handle both variants in a unified way, we define the notion of an $(\alpha,\beta)$ -approximation algorithm: such an algorithm either finds a connected solution $S$ such that $|S|\leq\alpha k$ and $|N_{G_{\texttt{cov}}}(S)|\geq\beta t$ ; or correctly outputs that there is no $S\subseteq R$ satisfying the original requirements.

Modeling prior problems.

Here we describe how we can model the problems from the prior literature as instances of PartialConRBDS. Consider Connected Partial/Budgeted Dominating Set, studied in [26, 27], where we are given a graph $G$ , and we want to find a connected dominating set (with dual objectives). To model it as PartialConRBDS, we let $G_{\texttt{conn}}\coloneqq G$ , and $G_{\texttt{cov}}$ is a bipartite graph on the vertex set $R\uplus B$ , where $R=V(G)$ , and $B$ is another copy of $V(G)$ . For each $u\in V(G)$ , we add the edges between $u$ and the copies of all $w\in N_{G}[u]$ in the set $B$ . Note that there is a close coupling between $G_{\texttt{conn}}$ and $G_{\texttt{cov}}$ while modeling Connected Partial Dominating Set, which is not always the case. Indeed, consider the Connected Max Coverage problem studied in [22, 11], where we are given a set system $(\mathcal{U},\mathcal{F})$ , and a graph $G$ with $V(G)=\mathcal{F}$ . To model it as PartialConRBDS, we let $G_{\texttt{cov}}$ be the set-element incidence graph (as described above), and let $G_{\texttt{conn}}\coloneqq G$ . At the other extreme, the vanilla Max Coverage can be modeled by letting $G_{\texttt{conn}}$ be a clique, rendering the connectivity requirement redundant.

Partial Hitting Set is the “dual variant”, where the roles of elements of the universe $\mathcal{U}$ and the sets of $\mathcal{F}$ are reversed ([17]) – we want to select a minimum number of elements from $\mathcal{U}$ that hits at least $t$ elements. This again can be modeled as PartialConRBDS by letting $G_{\texttt{cov}}$ be the set-element incidence graph as before; however with the roles of $R$ and $B$ flipped ( $R$ corresponds to $\mathcal{U}$ , and $B$ to $\mathcal{F}$ ), and $G_{\texttt{conn}}$ is a clique defined on the vertex set that corresponds to $\mathcal{U}$ .

1.2 Our Algorithmic Results

PartialConRBDS is $\mathsf{W[1]}$ -hard parameterized by $k$ even under strong restrictions: it remains hard when $G_{\mathrm{conn}}$ is a clique or a star and the incidence (coverage) graph $G_{\texttt{cov}}$ is $3$ -degenerate, and even when $G_{\texttt{cov}}$ is $K_{2,2}$ -free. For every $\varepsilon>0$ , there is no polynomial-time $(1,\,1-1/e+\varepsilon)$ -approximation unless $\mathsf{P}=\mathsf{NP}$ ; moreover, under ETH, no algorithm running in time $f(k)\cdot n^{o(k)}$ achieves either a $(g(k),1)$ -approximation for any computable function $g(\cdot)$ (with respect to the size bound $k$ ) or a $(1,\,1-1/e+\varepsilon)$ -approximation (with respect to the coverage threshold $t$ ). The graphical special cases reflect the same picture: Partial Connected Dominating Set is $\mathsf{W[2]}$ -hard parameterized by $k$ and inherits the ETH-based $f(k)\cdot n^{o(k)}$ inapproximability bounds above, while Partial Connected Vertex Cover is $\mathsf{W[1]}$ -hard parameterized by $k$ . For more details see Section 1.3. These hardness boundaries delineate a natural “sweet spot”: under suitable structural restrictions on the incidence graph one can still aim for fine-grained (FPT) approximation schemes. All of these results on parameterized and approximation lower bounds are established by modeling already existing problems such as Max Coverage, Connected Partial/Budgeted Dominating Set (See full version). Also the details of some sections/results marked with $\spadesuit$ can be found in the full version of the paper.

A natural question is: which restrictions on the incidence graph suffice? Recall that Partial Vertex Cover admits a $(1-\varepsilon)$ -approximation (for the coverage target $t$ ) [35, 32, 40] and a $+1$ additive approximation (for the size bound $k$ ) [24]. In fact, these guarantees hold when $\mathcal{D}$ is the class of incidence graphs of $K_{d,d}$ -free set systems (i.e., no $d$ sets share $d$ common elements). A natural next step is to ask whether the same techniques extend to connectivity-constrained coverage – namely, when the chosen set $S\subseteq R$ must also satisfy graph-side constraints imposed by an arbitrary companion graph $G_{\texttt{conn}}$ . Answering this question (almost) affirmatively is the main technical contribution of our work.

Our main algorithmic contribution is parameterized approximation schemes for the two natural optimization variants of PartialConRBDS when the coverage graph $G_{\texttt{cov}}$ is $K_{d,d}$ -free. Specifically, we prove the following two theorems. The first of the following two theorems is when we insist on a connected solution of size at most $k$ , and wish to approximate the number of blue vertices dominated by the solution.

Theorem 1.

For any $\varepsilon>0$ , there exists an $(1,1-\varepsilon)$ -approximation algorithm with running time $2^{\mathcal{O}(k^{2}d/\varepsilon)}\cdot|\mathcal{I}|^{\mathcal{O}(1)}$ for an instance $\mathcal{I}$ of PartialConRBDS where the coverage graph is $K_{d,d}$ -free, and the connectivity graph is arbitrary. That is, this algorithm takes an instance $\mathcal{I}=(G_{\texttt{conn}},G_{\texttt{cov}},k,t)$ such that $G_{\texttt{cov}}$ is $K_{d,d}$ -free, runs in time $2^{\mathcal{O}(k^{2}d/\varepsilon)}\cdot|\mathcal{I}|^{\mathcal{O}(1)}$ and either (i) outputs $S\subseteq R$ of size at most $k$ such that $G_{\texttt{conn}}[S]$ is connected and $|N_{G_{\texttt{cov}}}(S)|\geq(1-\varepsilon)t$ ; or (ii) correctly reports that there exists no $S\subseteq R$ of size at most $k$ such that $G_{\texttt{conn}}[S]$ is connected, and $|N_{G_{\texttt{cov}}}(S)|\geq t$ .

We prove a complementary result, where we approximate the solution size, but insist that it dominates at least $t$ blue vertices. More formally, we prove the following theorem.

Theorem 2 ( $\spadesuit$ ).

For any $\varepsilon>0$ , there exists an $(1+\varepsilon,1)$ -approximation algorithm with running time $2^{\mathcal{O}(kd(k^{2}+\log d))}\cdot|\mathcal{I}|^{\mathcal{O}(1/\varepsilon)}$ for an instance $\mathcal{I}$ of PartialConRBDS, where the coverage graph is $K_{d,d}$ -free, and the connectivity graph is arbitrary. That is, this algorithm takes an instance $\mathcal{I}=(G_{\texttt{conn}},G_{\texttt{cov}},k,t)$ such that $G_{\texttt{cov}}$ is $K_{d,d}$ -free, runs in time $2^{\mathcal{O}(kd(k^{2}+\log d))}\cdot|\mathcal{I}|^{\mathcal{O}(1/\varepsilon)}$ , and either (i) outputs $S\subseteq R$ of size at most $(1+\varepsilon)k$ such that $G_{\texttt{conn}}[S]$ is connected and $|N_{G_{\texttt{cov}}}(S)|\geq t$ ; or (ii) correctly reports that there exists no $S\subseteq R$ of size at most $k$ such that $G_{\texttt{conn}}[S]$ is connected, and $|N_{G_{\texttt{cov}}}(S)|\geq t$ .

We reiterate that both of the following results are in the setting where $\mathcal{C}$ is arbitrary and $\mathcal{D}$ is a family of bipartite incidence graphs that are $K_{d,d}$ -free for some $d\geq 1$ . Recall that Khuller et al. gave an $\mathcal{O}(\log\Delta)$ -approximation for Partial Connected Dominating Set. Our result above (Theorem 2) improves upon this result by returning an $(1+\varepsilon)$ -approximation in $\mathcal{O}^{\star}(2^{k\Delta(k^{2}+\log\Delta)})$ time.

Neighborhood Sparsifiers: A Conceptual Contribution.

A natural approach to solve our problem is to assign a weight to each red vertex proportional to its coverage degree in $G_{\texttt{cov}}$ – say $w(v)\coloneqq|N_{G_{\texttt{cov}}}(v)|$ and then pick a connected $k$ -set in $G_{\texttt{conn}}$ with maximum total weight, i.e., a maximum-weight $k$ -vertex tree in $G_{\texttt{conn}}$ (solvable in $2^{\mathcal{O}(k)}n^{\mathcal{O}(1)}$ time; see Section 5). The obstacle is additivity: overlaps in neighborhoods mean that a single weight function $w:R\to\mathbb{Z}_{\geq 0}$ satisfying $w(S)\;-\;\varepsilon t\;\leq\;|N_{G_{\texttt{cov}}}(S)|\;\leq\;w(S)\;+\;% \varepsilon t\quad\text{for all }S\subseteq R,\ |S|\leq k$ (and computable in FPT time) appears out of reach.

Instead, when $G_{\texttt{cov}}$ is $K_{d,d}$ -free, we construct a small family of surrogate weight functions, one of which has the desired property. This reduces the task to, for each weight function, solving a maximum-weight $k$ -tree in $G_{\texttt{conn}}$ and taking the best outcome. Technically, the family arises from a combinatorial sparsification lemma for $G_{\texttt{cov}}$ : via a greedy step coupled with random separation (later derandomized), we obtain a sparsified incidence graph that preserves the neighborhoods of all $k$ -sets. In the sparsified instance, the simple per-vertex degree $w(v)={\sf deg}_{\text{sparse}}(v)$ serves as the required weight, yielding the desired approximation once lifted back to the original graph.

Lemma 3 (Neighborhood Sparsifiers for $K_{d,d}$ -free coverage).

Let $\mathcal{I}=(G_{\texttt{conn}},G_{\texttt{cov}},k,t)$ be an instance of PartialConRBDS with $G_{\texttt{cov}}$ $K_{d,d}$ -free. There exist $\ell=f(k,d,\varepsilon)\cdot\log|B|$ weight functions $\{w_{1},\ldots,w_{\ell}\},\quad w_{i}:R\to\mathbb{Z}_{\geq 0},$ computable in time $g(k,d,\varepsilon)\,\cdot|B|^{\mathcal{O}(1)}$ , such that the following holds. For every $S\subseteq R$ with $|S|=k$ , for all $j\in[\ell]$ with $w_{j}(S)-\varepsilon t\;\leq\;|N_{G_{\texttt{cov}}}(S)|\;\leq\;w_{j}(S),$ where $w_{j}(S)\coloneqq\sum_{v\in S}w_{j}(v)$ .

We believe that Lemma 3 will find applications beyond this work, in the spirit of seminal cut and spectral sparsifiers [3, 41]. We do not prove the lemma in the form stated here, but it follows from our results. We will include a proof of this specific version in the final version of the paper.

1.3 Potential for a Dichotomy Program

Our results motivate a clean classification program separating regimes that admit FPT-approximation from those that are provably hard. We study the (parameterized) complexity of PartialConRBDS over “ $(\mathcal{C}\times\mathcal{D})$ ” families of instances, where the constraint graph $G_{\texttt{conn}}$ ranges over a class $\mathcal{C}$ and the coverage/incidence graph $G_{\texttt{cov}}$ ranges over a class $\mathcal{D}$ . We instantiate this framework by varying $\mathcal{C}$ (e.g., bounded treewidth, clique/star) and $\mathcal{D}$ (e.g., biclique-free, bounded rank/degeneracy), thereby charting the frontier between FPT-approximability and hardness. We exemplify this by varying $\mathcal{C}$ and $\mathcal{D}$ in a few different ways.

$\mathcal{C}$ = cliques, $\mathcal{D}$ = arbitrary.: As mentioned earlier, this models an arbitrary instance of Max Coverage, and therefore PartialConRBDS inherits all its positive and negative results. We explicitly spell out these approximation and parameterized lower bounds in order to contrast them with our positive algorithmic results.
$\mathcal{C}$ = max degree $\Delta$ , $\mathcal{D}$ = arbitrary.: In this case, we can enumerate $n\cdot\Delta^{\mathcal{O}(k)}$ connected vertex-subsets of $G_{\texttt{conn}}$ of size at most $k$ , and check whether any subset dominates at least $t$ blue vertices in $G_{\texttt{cov}}$ . Therefore, in this case PartialConRBDS is FPT parameterized by $k+\Delta$ . Note, in particular, that this captures the special case when $G_{\texttt{conn}}$ is a path (in this case, in fact, the problem is polynomial-time solvable). It may be tempting to conjecture that PartialConRBDS is (fixed-parameter) tractable even when $\mathcal{C}$ is the class of trees. This, however, turns out not to be the case.
$\mathcal{C}$ = stars, $\mathcal{D}$ = arbitrary.: In this case, we can again model an arbitrary instance of Max Coverage, by adding a dummy set that maps to the central vertex of the star, and all the original sets mapping to the leaves of the star. Thus, all the intractable results carry over from Max Coverage.
$\mathcal{C}$ = arbitrary, $\mathcal{D}$ = arbitrary.: In this most general case, we design an FPT algorithm for PartialConRBDS parameterized by $t$ , which runs in time $\mathcal{O}^{\star}((2e)^{t})$ in Section 4. This shows that, parameterized by the desired coverage, the problem is fixed-parameter tractable in spite of the connectivity requirements.
$\mathcal{C}$ = arbitrary, $\mathcal{D}$ = each vertex in $R$ has degree at most $\Delta_{R}$ .: In this case, note that any $k$ -sized set $S\subseteq R$ has $|N_{G_{\texttt{cov}}}(S)|\leq k\Delta$ , implying that if $t>k\Delta_{R}$ then we can conclude that we have a No-instance. Otherwise, the FPT algorithm from the previous paragraph implies that PartialConRBDS is FPT parameterized by $k+\Delta_{R}$ .
$\mathcal{C}$ = arbitrary, $\mathcal{D}$ = each vertex in $B$ has degree at most $\Delta_{B}$ .: Note that when $\Delta_{B}=2$ , this models the coverage of edges by vertices in a graph. Therefore, when $G_{\texttt{conn}}$ is a clique or a star, one can model Partial Vertex Cover, which is known to be W[1]-hard parameterized by $k$ ; and PartialConRBDS inherits this hardness.

2 Technical Overview of Our Main Results

Next, we describe some of the technical ideas that lead to our algorithmic results Theorem 1 and Theorem 2. Due to the inherent nature of the problem, our algorithms and the corresponding arguments need to juggle between the two graphs $G_{\texttt{conn}}$ and $G_{\texttt{cov}}$ , and their interplay with a hypothetical solution that we seek. These arguments go via a couple of auxiliary graphs that make finding a solution easier, albeit at the expense of a small loss in the quality of the solution (either in terms of the solution size, or in terms of the number of dominated blue vertices).

Overview of the proof of Theorem 1.

Suppose that the input instance $\mathcal{I}=(G_{\texttt{conn}},G_{\texttt{cov}},k,t)$ is a Yes-instance of PartialConRBDS, where $G_{\texttt{conn}}$ is arbitrary and $G_{\texttt{cov}}$ is $K_{d,d}$ -free. Let $S^{\star}\subseteq R=V(G_{\texttt{conn}})=V(G_{\texttt{cov}})$ be an (unknown) solution of size $k$ that is connected in $G_{\texttt{conn}}$ and dominates at least $t$ blue vertices.

1. Defining and working with a conflict graph.: We construct an auxiliary graph, called the conflict graph, denoted as $G_{\texttt{conf}}$ , where $V(G_{\texttt{conf}})=R$ , and there is an edge between two vertices iff the number of common blue neighbors of the two vertices is a “significant fraction” of $t$ (we will use $\frac{\varepsilon t}{k^{2}}$ ). Using the fact that $G_{\texttt{cov}}$ is $K_{d,d}$ -free, one can show that the maximum degree of $G_{\texttt{conf}}$ is bounded by some $f(k,d,\varepsilon)$ , notably it is independent of $t$ (cf. Lemma 6). That is, for each red vertex $u$ , the number of other red vertices that have a significant overlap with $u$ in terms of blue domination is bounded by $f(k,d,\varepsilon)$ . Notice that some pairs of vertices from $S^{\star}$ (our unknown solution) can have significant overlap, but maybe not all. Therefore, $G_{\texttt{conf}}[S^{\star}]$ may be disconnected with at most $k$ connected components, denoted by $\mathcal{C}^{\star}$ . Since $\Delta(G_{\texttt{conf}})\leq f(k,d,\varepsilon)$ , we can use the technique of random separation to obtain a collection $\mathcal{C}$ of induced connected subgraphs of $G_{\texttt{conf}}$ such that, $\mathcal{C}^{\star}\subseteq\mathcal{C}$ (even though $S^{\star}$ is unknown to us). The success probability of this step is inverse FPT in $k, d$ , and $\varepsilon$ ; and this step can be derandomized using known combinatorial tools. Let us assume henceforth that we have such a collection $\mathcal{C}$ in our hand. The algorithmic task is to figure out which set of connected components from $\mathcal{C}$ together form the desired solution.
2. Using $\mathcal{C}$ to sparsify $G_{\texttt{cov}}$ .: Recall that our unknown solution $S^{\star}$ is partitioned across $\mathcal{C}$ in such a way that, either all or none of the vertices of a component in $\mathcal{C}$ are a part of $S^{\star}$ . We process each blue vertex $u$ as follows: whenever $u$ has edges to two or more red neighbors within the same component of $\mathcal{C}$ , we arbitrarily delete all but one of these edges. We repeat this until every blue vertex has at most one neighbor in each component. The resulting graph $G_{\texttt{spar}}$ is a subgraph of $G_{\texttt{cov}}$ . This way, each blue vertex $u$ has at most one neighbor in $G_{\texttt{spar}}$ within any component of $\mathcal{C}$ , and that neighbor will be responsible for counting the domination of $u$ . For each red vertex $r\in R$ , we define its weight as the number of its blue neighbors in the sparsified graph $G_{\texttt{spar}}$ . Note that, while a solution may span across multiple components, and hence some domination overlap across different components may still remain, the construction of the conflict graph guarantees that such inter-component overlap is a negligible fraction of $t$ . Recall that the different weight functions mentioned in Lemma 3 correspond to different weight functions obtained in this manner, corresponding to different colorings from the random separation step.
3. Using sparsified weights to find an approximate solution.: We now view $G_{\texttt{conn}}$ as a weighted graph, where the weight of each vertex is defined from the sparsification step. Then, we find a connected subgraph of $G_{\texttt{conn}}$ on at most $k$ vertices with maximum total weight. This can be done using an application of the classical color-coding approach [1]. If there exists a feasible solution $S^{\star}$ of size $k$ , it corresponds to a connected subgraph with total weight at least $t$ . Conversely, if we identify a connected subgraph $S$ with total weight at least $t$ , then even after discounting the small amount of over-counting across different components, we are guaranteed that $|N_{G_{\texttt{cov}}}(S)|\geq(1-\varepsilon)t$ . This completes the description of Theorem 1.

Overview of the proof of Theorem 2.

As before, suppose that the given instance $\mathcal{I}$ is a Yes-instance and let $S^{\star}$ be an unknown solution. In this setting, the goal of $(1+\varepsilon,1)$ -approximation is flipped: we no longer insist that the solution has size exactly $k$ (we allow solutions of size up to $(1+\varepsilon)k$ ); but instead require that it dominates at least $t$ blue vertices.

1. A first attempt, and why it fails.

We begin by running the algorithm from the previous subsection with a suitable choice of $\delta$ , obtaining an $(1,1-\delta)$ -approximate solution $S$ of size $k$ that covers at least $(1-\delta)t$ blue vertices. If $|N_{G_{\texttt{cov}}}(S)|\geq t$ , we are done. Otherwise, the solution is only slightly short; but remember that we are allowed to add a few more vertices to reach the required coverage.

Let $H$ be the set of the $g(k,d,\delta)$ highest-degree red vertices. A combinatorial lemma (originally from [24]) guarantees that, when $G_{\texttt{cov}}$ is $K_{d,d}$ -free, at least one of the following holds.

(i)

the unknown solution intersects $H$ , i.e., $H\cap S^{\star}\neq\emptyset$ , or
(ii)

there exists a vertex $h\in H$ such that $S\cup\{h\}$ dominates at least $t$ blue vertices

This suggests a natural strategy: if case (i) holds, then we add $h$ to the solution, and recurse. Otherwise, in case (ii), we simply add $h$ to $S$ , yielding a solution of size $k+1$ , which is much smaller than the allowed $(1+\varepsilon)k$ . But there is a catch: we also require that the solution be connected in $G_{\texttt{conn}}$ , and there is no guarantee that $G_{\texttt{conn}}[S\cup\{h\}]$ is connected. If $h$ happened to be adjacent to, or close to, a vertex of $S$ , this would be easy to fix, but this does not hold in general.

2. A structural lemma to the rescue.

To overcome this, we first provide a structural lemma that may be of an independent interest: since $G_{\texttt{conn}}[S^{\star}]$ is connected, there exists a subset $C\subseteq S^{\star}$ of size at most $1/\varepsilon$ such that every vertex of $S^{\star}$ is at distance at most $\varepsilon k$ from $C$ . We “guess” $C$ by iterating over all subsets of $R$ of size at most $1/\varepsilon$ , and in each iteration, we require that the guessed set $C$ must be a part of our solution that we will build. During recursion, $C$ may grow as we discover additional vertices that must belong to $S^{\star}$ ; but the original $C$ serves the purpose of “cheaply connecting” a vertex to the solution.

3. Amended recursive strategy.

With this additional seed $C$ , we run the previous algorithm again to find a set $S$ of size $k$ containing $C$ that dominates at least $(1-\delta)t$ blue vertices (this requires generalizing the previous algorithm so that we can provide to it an additional terminal set–here $C$ –that must be contained in the solution). At this point, we focus only on high-degree vertices that are near $C$ in $G_{\texttt{conn}}$ , since $S^{\star}$ must be contained in this neighborhood. We then apply the lemma from Step 1:

$\blacksquare$

In case (i), we guess $h\in H$ that is guaranteed to belong to $S^{\star}$ . Then we branch on all possibilities for $h$ , extend $C$ by including it, and recurse.
$\blacksquare$

In case (ii), for some $h\in H$ , the set $S\cup\{h\}$ dominates at least $t$ blue vertices. Because $h$ is close to $C$ , we can connect it to $S$ by adding a path $P$ in $G_{\texttt{conn}}$ of length at most $\varepsilon k$ . The resulting set $S\cup P$ is connected, has size at most $(1+\varepsilon)k$ , and dominates at least $t$ blue vertices. Iterating over all $h\in H$ , we return a solution whenever this case applies.

This concludes the overview of the proof of Theorem 2. We note that the running time of this $(1+\varepsilon,1)$ -approximation algorithm is of the form $h(k,d)\cdot|\mathcal{I}|^{\mathcal{O}(1/\varepsilon)}$ , in contrast to the $(1,1-\varepsilon)$ -approximation of Theorem 1, which runs in time $f(k,d,\varepsilon)\cdot|\mathcal{I}|^{\mathcal{O}(1)}$ . A natural question is whether the dependence on $\varepsilon$ in Theorem 2 can be improved, i.e., whether one can achieve a running time of the form $h(k,d,\varepsilon)\cdot|\mathcal{I}|^{\mathcal{O}(1)}$ . In analogy with PTAS versus EPTAS, this corresponds to improving from a PAS to an EPAS ²²2EPAS stands for Efficient Parameterized Approximation Scheme, i.e., a $(1\pm\varepsilon)$ -approximation in time $f(\kappa,\varepsilon)\cdot|I|^{\mathcal{O}(1)}$ for some parameter $\kappa$ . PAS stands for Parameterized Approximation Scheme, where the running time can be $f(\kappa,\varepsilon)\cdot|I|^{g(\varepsilon)}$ ..

However, obtaining such an improvement would be unlikely due to the following simple reason. Indeed, suppose for any $\varepsilon>0$ we could compute a connected solution of size at most $(1+\varepsilon)k$ that covers at least $t$ blue vertices. Setting $\varepsilon\leftarrow\frac{1}{2k}$ would then yield a solution of size at most $k+\frac{1}{2}$ , which must in fact be of size at most $k$ . This would give an exact FPT algorithm for PartialConRBDS parameterized by $k$ and $d$ ; however the problem is W[1]-hard when parameterized by $k$ even when $d=2$ (cf. Partial Vertex Cover). Thus, Theorem 2 achieves, in a precise sense, the best possible form of approximation scheme, apart from potential improvements to the ${\sf FPT}$ factor of the running time.

3 Preliminaries

Let $[n]$ be the set of integers $\{1,\ldots,n\}$ . For a graph $G$ , we denote the set of vertices of $G$ by $V(G)$ and the set of edges by $E(G)$ . For a directed graph $D$ , we denote the set of vertices of $D$ by $V(D)$ and the set of edges by $A(D)$ . We denote an edge of an undirected graph by $u v$ and an arc of a directed graph by $(u,v)$ . For a subset $X$ of vertices $X\subseteq V(G)$ , we use the notation $G-X$ to mean the graph $G[V(G)\setminus X]$ . For a vertex subset $S\subseteq V(G)$ , $G[S]$ denotes the subgraph of $G$ induced on $S$ , i.e., $V(G[S])=S,\nobreak\ E(G[S])=\{uv:u,v\in S,uv\in E(G)\}$ . For a graph $G$ and a vertex $v\in V(G)$ , we define open neighborhood of a vertex as $N_{G}(v)\coloneqq\left\{u\mid uv\in E(G)\right\}$ and closed neighborhood of a vertex as $N_{G}[v]\coloneqq N_{G}(v)\cup\{v\}$ . Further for a set $X\subseteq V(G)$ , open neighborhood of $X$ is defined as $N_{G}(X)\coloneqq\left(\bigcup\limits_{x\in X}N_{G}(x)\right)\setminus X$ and closed neighborhood of $X$ is defined as $N_{G}[X]\coloneqq N_{G}(X)\cup X$ . We use standard terminology from the book of Diestel [12] for those graph-related terms that are not explicitly defined here. We refer to [9] for an introduction to the area of parameterized complexity and related terminology.

4 FPT for PARTIALCONRBDS parameterized by $𝒕$

In this section we design an algorithm for PartialConRBDS, parameterized by $t$ . The result is obtained by giving an FPT reduction to Relaxed Directed Steiner Out-Tree problem. A directed out-tree (or arborescence) is a digraph whose underlying undirected graph is a tree and that has a unique root $r$ such that every arc is directed away from $r$ . Equivalently, the root $r$ has in-degree $0$ and every other vertex has in-degree exactly $1$ . The problem Relaxed Directed Steiner Out-Tree is defined as follows:

Relaxed Directed Steiner Out-Tree (RDSOT)

Input: A directed graph $D=(V,A)$ , a set of terminals $T\subseteq V$ , an integer $p$ .

Question: Is there a directed out-tree $D^{\prime}\subseteq D$ with $|V(D^{\prime})|\leq p$ and $T\subseteq V(D^{\prime})$ ?

If in addition, we are given an additional distinguished vertex $r\in V$ and ask to check whether $D$ contain a directed out-tree on at most $p$ vertices that is rooted at $r$ and that contains all the vertices of $T$ , then that problem is referred as Directed Steiner Out-Tree. Misra et al. [36] gave an algorithm for Directed Steiner Out-Tree that runs in time $2^{|T|}\cdot n^{\mathcal{O}(1)}$ . Note that we can also solve Relaxed Directed Steiner Out-Tree in time $2^{|T|}\cdot n^{\mathcal{O}(1)}$ by “guessing” (i.e., enumerating $n$ choices for) the root vertex $r$ , and solving the resulting instance of Directed Steiner Out-Tree. Now we use this result to design a randomized algorithm for PartialConRBDS.

Randomized reduction from PARTIALCONRBDS to RDSOT.

Let $\mathcal{I}=\left(G_{\texttt{conn}},G_{\texttt{cov}},k,t\right)$ be the given instance of PartialConRBDS. Let $f:B\to[t]$ denote an arbitrary function (referred to as a coloring), where each vertex of $B$ is assigned an integer from $[t]$ . For each $i$ , let $B_{i}$ denote the vertices with color $i$ according to $f$ , i.e., $B_{i}=\{v\mid v\in B,f(v)=i\}$ (we omit the dependence of $f$ in the notation for the sake of brevity).

Now, we construct a directed graph $D_{f}$ that will serve as the input for the eventual instance of Relaxed Directed Steiner Out-Tree. We define

V(D):=V(G_{\texttt{cov}})\;\uplus\;T,\qquad\text{ where }T=\{\tau_{i}:i\in[t]\}.

The arc set $A(D_{f})$ is constructed by adding the following three types of arcs.

$\blacksquare$

Type 1: For every edge $uv\in E(G_{\texttt{conn}})$ , add both arcs $(u,v)$ and $(v,u)$ to $A(D_{f})$ .
$\blacksquare$

Type 2: For every edge $uv\in E(G_{\texttt{cov}})$ with $u\in R,v\in B$ , add the arc $(u,v)$ to $A(D_{f})$ .
$\blacksquare$

Type 3: For each $i\in[t]$ , add the arcs $\{(v,\tau_{i}):v\in B_{i}\}$ to $A(D_{f})$ .

Let $p=k+2t$ , and let $\mathcal{I}^{\prime}_{f}=(D_{f},T,p)$ be the resulting instance of Relaxed Directed Steiner Out-Tree.

Our randomized algorithm works on the given instance $\mathcal{I}=(G_{\texttt{conn}},G_{\texttt{cov}},k,t)$ as follows. First, it obtains a random $f:B\to[t]$ , i.e., for each $u\in B$ , it independently and uniformly assigns a color from $[t]$ . Then, it constructs the instance $\mathcal{I}^{\prime}_{f}=(D_{f},T,p)$ of RDSOT as described above. Then, it runs the $\mathcal{O}^{\star}(2^{|T|})=\mathcal{O}^{\star}(2^{t})$ time algorithm of [36], which returns Yes iff $\mathcal{I}^{\prime}_{f}$ is a Yes-instance of RDSOT. It repeats this procedure (of selecting a random coloring $f$ and solving the resulting $\mathcal{I}^{\prime}_{f}$ ) independently up to $e^{t}$ times. If in any of the iterations, the algorithm of [36] outputs Yes, then our algorithm reports that the original instance $\mathcal{I}$ of PartialConRBDS is a Yes-instance. Otherwise, if in all iterations the algorithm returns No, then the algorithm outputs that $\mathcal{I}$ is a No-instance of PartialConRBDS.

Theorem 4 ( $\spadesuit$ ).

PartialConRBDS admits a deterministic (resp. randomized) algorithm that runs in time $\mathcal{O}^{\star}((2e)^{t+o(t)})$ (resp. $\mathcal{O}^{\star}((2e)^{t})$ and outputs the correct answer with probability at least $1-1/e$ ).

5 $(1,1-\varepsilon)$ -approximation for PARTIALCONRBDS

In this section we design an FPT algorithm (parameterized by $k+d+1/\varepsilon$ ) that achieves a $(1,1-\varepsilon)$ -bicriteria approximation for PartialConRBDS when the coverage graph $G_{\texttt{cov}}$ is $K_{d,d}$ -free. If $t<\tfrac{k^{2}d}{\varepsilon}$ , we invoke the exact algorithm of Theorem 4, which (when a solution exists) returns a set of size at most $k$ dominating at least $t$ vertices. When $t\geq\tfrac{k^{2}d}{\varepsilon}$ , assuming there exists a solution of size at most $k$ dominating at least $t$ vertices, we compute a set $S\subseteq R$ with $|S|\leq k$ , $G_{\texttt{conn}}[S]$ connected, and $S$ dominating at least $(1-\varepsilon)t$ vertices of $B$ in $G_{\texttt{cov}}$ . Combining these two cases yields Theorem 17. Since the small- $t$ case is handled by Theorem 4, the remainder of this section focuses on the regime $t\geq\tfrac{k^{2}d}{\varepsilon}$ . We next present the algorithmic components and then assemble them into the full procedure, referring back to the corresponding subsections as needed.

Suppose $\mathcal{I}=(G_{\texttt{conn}},G_{\texttt{cov}},k,t)$ is a Yes-instance of PartialConRBDS; i.e., there exists $S^{\star}\subseteq R$ with $|S^{\star}|\leq k$ such that

(P1)

$G_{\texttt{conn}}[S^{\star}]$ is connected, and
(P2)

$|N_{G_{\texttt{cov}}}(S^{\star})|\geq t$ .

We will refer to these properties as ( $\mathsf{P}1$ ) and ( $\mathsf{P}2$ ) throughout this section.

5.1 Step 1: Construction of the Conflict Graph

In this subsection, we define the notion of a conflict graph as follows.

Definition 5 (conflict graph).

Let $G_{\texttt{conn}}$ and $G_{\texttt{cov}}$ denote the connectivity and coverage graphs, respectively, as given in the input. We define conflict graph, denoted by $G_{\texttt{conf}}$ as follows: the vertex set $V\left(G_{\texttt{conf}}\right)\coloneqq V\bigl(G_{\texttt{conn}}\bigr)=R$ , and $E\big(G_{\texttt{conf}}\big)\coloneqq\bigl\{uv:u,v\in R\nobreak\ \text{\em and% }\nobreak\ \big|N_{G_{\texttt{cov}}}(u)\cap N_{G_{\texttt{cov}}}(v)\big|\geq% \frac{\varepsilon t}{k^{2}}\bigr\}$ .

Note that the conflict graph can be constructed in time quadratic in the size of $G_{\texttt{cov}}$ . In the following lemma, we bound the maximum degree of the conflict graph.

Lemma 6 (Restatement of Lemma 4.1 from [24]).

Suppose the coverage graph $G_{\texttt{cov}}$ is $K_{d,d}$ -free, and $t\geq\frac{k^{2}d}{\varepsilon}$ . Then, the maximum degree $\Delta\coloneqq\Delta(G_{\texttt{conf}})$ of the conflict graph, $G_{\texttt{conf}}$ as in Definition 5 is at most $(d-1)\cdot\left(\tfrac{ek^{2}}{\varepsilon}\right)^{d}$ , where $e$ denotes the base of natural logarithm.

Proof.

The proof is essentially identical to that of Lemma 4.1 of [24], but we describe it here for the sake of completeness, using the terminology used in this paper. Recall that, $G_{\texttt{conn}},G_{\texttt{cov}},G_{\texttt{conf}}$ denote the connectivity, coverage and conflict graphs respectively. We show that the degree of every vertex $v\in V\left(G_{\texttt{conf}}\right)$ , that is ${\sf deg}_{G_{\texttt{conf}}}(v)$ is bounded. To this end, fix an arbitrary vertex $v\in V\left(G_{\texttt{conf}}\right)$ . WLOG, we only focus on the vertices with ${\sf deg}_{G_{\texttt{conf}}}(v)\geq 1$ ; vertices with degree $0$ trivially have bounded degree in $G_{\texttt{conf}}$ . Let us consider the sets $P\coloneqq N_{G_{\texttt{conf}}}(v)\subseteq R$ and $Q\coloneqq N_{G_{\texttt{cov}}}(v)\subseteq B$ . Now consider the induced subgraph $G_{\texttt{cov}}[P\uplus Q]$ of the original coverage graph $G_{\texttt{cov}}$ . Let this induced subgraph be $G_{\texttt{cov}}^{v}$ .

Let $\mathcal{K}$ denote the set of all $K_{1,d}$ ’s in the graph $G_{\texttt{cov}}^{v}$ , where one vertex (the center vertex of the star) belongs to $N_{G_{\texttt{conf}}}(v)\subseteq R$ and its $d$ neighbors belong to $N_{G_{\texttt{cov}}}(v)\subseteq B$ . Since every $u\in P$ has at least $\frac{\varepsilon t}{k^{2}}\geq d$ neighbors in $Q$ , i.e., $\big|N_{G_{\texttt{cov}}^{v}}(u)\big|\geq\frac{\varepsilon t}{k^{2}}\geq d$ , it follows that each $u\in P$ participates in at least $\displaystyle\binom{\frac{\varepsilon t}{k^{2}}}{d}$ distinct copies of $K_{1,d}$ . Therefore, $|\mathcal{K}|\geq|P|\cdot\dbinom{\frac{\varepsilon t}{k^{2}}}{d}$ .

Further, we claim that $|\mathcal{K}|\leq(d-1)\dbinom{|Q|}{d}$ . Assume towards contradiction that $|\mathcal{K}|>(d-1)\dbinom{|Q|}{d}$ . For each set $Z\subseteq Q$ of size exactly $d$ , let $\kappa(Z)$ denote the number of $K_{1,d}$ ’s in $\mathcal{K}$ that all the vertices of $Z$ together participate in. Then, it follows that $(d-1)\cdot\dbinom{|Q|}{d}<|\mathcal{K}|=\sum\limits_{Z\subseteq Q:|Z|=d}\kappa% (Z)\leq\dbinom{|Q|}{d}\kappa(Z_{\max})$ , where $Z_{\max}\coloneqq\operatorname*{arg\,max}\limits_{Z\subseteq Q:|Z|=d}\kappa(Z)$ . This implies that $\kappa(Z_{\max})>d-1$ , i.e., $\kappa(Z_{\max})\geq d$ . However, this implies the existence of a $K_{d,d}$ in $G_{\texttt{cov}}^{v}$ , which is a subgraph of $G_{\texttt{cov}}$ , a contradiction. Therefore, we obtain that,

$\displaystyle\|P\|\cdot\dbinom{\frac{\varepsilon t}{k^{2}}}{d}\leq\|\mathcal{K}\|$	$\displaystyle\leq(d-1)\cdot\binom{\|Q\|}{d}<(d-1)\cdot\binom{t}{d}$	(Since $\|Q\|<t$ , else singleton solution)
$\displaystyle\implies\|P\|$	$\displaystyle\leq(d-1)\cdot\frac{\binom{t}{d}}{\dbinom{\frac{\varepsilon t}{k^% {2}}}{d}}$
	$\displaystyle\leq(d-1)\cdot\frac{\left(\frac{et}{d}\right)^{d}}{\left(\frac{% \varepsilon t}{k^{2}d}\right)^{d}}$	(Since $\left(\frac{n}{k}\right)^{k}\leq\binom{n}{k}\leq\left(\frac{en}{k}\right)^{k}$ )
	$\displaystyle\leq(d-1)\cdot\left(\tfrac{ek^{2}}{\varepsilon}\right)^{d}$

This concludes the proof. $\hfill\blacktriangleleft$

5.2 Step 2: Isolating Connected Components of $S^{\star}$ in $G_{\texttt{conf}}$

In this section we apply the classical random separation technique [5] to probabilistically isolate the solution vertices from their $G_{\texttt{conf}}$ -neighbors in any Yes-instance.

Let $f:V(G_{\texttt{conf}})\to\{\text{{\color[rgb]{.75,0,.25}\definecolor[named]{% pgfstrokecolor}{rgb}{.75,0,.25}purple}},\text{{\color[rgb]{0.0,0.47,0.44}% \definecolor[named]{pgfstrokecolor}{rgb}{0.0,0.47,0.44}green}}\}$ be a random coloring in which each vertex of $G_{\texttt{conf}}$ is colored independently

\text{{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{% .75,0,.25}purple}}\text{\nobreak\ with probability\nobreak\ }p\coloneqq\frac{1% }{1+\Delta}\quad\text{and}\quad\text{{\color[rgb]{0.0,0.47,0.44}\definecolor[% named]{pgfstrokecolor}{rgb}{0.0,0.47,0.44}green}}\ \text{with probability}\ 1-% p=\frac{\Delta}{1+\Delta},

where $\Delta\coloneqq\Delta(G_{\texttt{conf}})$ . For a coloring $f$ , write $V_{\mathrm{purple}}\coloneqq f^{-1}(\text{{\color[rgb]{.75,0,.25}\definecolor[% named]{pgfstrokecolor}{rgb}{.75,0,.25}purple}})$ and $V_{\mathrm{green}}\coloneqq f^{-1}(\text{{\color[rgb]{0.0,0.47,0.44}% \definecolor[named]{pgfstrokecolor}{rgb}{0.0,0.47,0.44}green}})$ .

Our objective for the coloring is the following “good separation” when the instance is a Yes-instance with witness $S^{\star}$ :

(i)

$S^{\star}\subseteq V_{\mathrm{purple}}$ , and
(ii)

$N_{G_{\texttt{conf}}}(S^{\star})\subseteq V_{\mathrm{green}}$ .

Since $|S^{\star}|\leq k$ and $|N_{G_{\texttt{conf}}}(S^{\star})|\leq\Delta\,k$ , we have

\Pr[\text{good separation}]\;\geq\;p^{|S^{\star}|}\,(1-p)^{|N_{G_{\texttt{conf% }}}(S^{\star})|}\;\geq\;\Bigl(\tfrac{1}{1+\Delta}\cdot\bigl(\tfrac{\Delta}{1+% \Delta}\bigr)^{\Delta}\Bigr)^{k}\geq\Delta^{-k}\cdot 2^{-\mathcal{O}(k)}.

Derandomization.

The random-coloring step can be derandomized using standard tools such as $(n,p,p^{2})$ -splitters (see, e.g., Exercises 5.15 and 5.21 in [10]) without affecting the final running time³³3Note that $\Delta=\Omega(k^{2}d/\varepsilon)$ implies $\log\Delta=\Omega(\log k)$ .. Rather than presenting a randomized algorithm, we directly give a deterministic one via an $(n,p,q)$ lopsided-universal family of functions.

Let $U$ be the ground set of vertices (so $U=V(G_{\texttt{conf}})$ and $n\coloneqq|U|$ ). An $(n,p,q)$ lopsided-universal family is a collection $\mathcal{H}=\{f_{1},\ldots,f_{\ell}\}$ of functions $f_{i}:U\to\{\text{{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{% rgb}{.75,0,.25}purple}},\text{{\color[rgb]{0.0,0.47,0.44}\definecolor[named]{% pgfstrokecolor}{rgb}{0.0,0.47,0.44}green}}\}$ such that for every $A\in\binom{U}{p}$ and $B\in\binom{U\setminus A}{q}$ there exists $f\in\mathcal{H}$ with $A\subseteq f^{-1}(\text{{\color[rgb]{.75,0,.25}\definecolor[named]{% pgfstrokecolor}{rgb}{.75,0,.25}purple}})$ and $B\subseteq f^{-1}(\text{{\color[rgb]{0.0,0.47,0.44}\definecolor[named]{% pgfstrokecolor}{rgb}{0.0,0.47,0.44}green}})$ .

Proposition 7 ([1, 10]).

There is an algorithm that, given $n$ , $p$ , and $q$ , constructs an $(n,p,q)$ lopsided-universal family $\mathcal{H}$ of size $\binom{(p+q)^{2}}{p}\cdot(p+q)^{\mathcal{O}(1)}\cdot\log n$ in time $\binom{(p+q)^{2}}{p}\cdot(p+q)^{\mathcal{O}(1)}\cdot n\log n.$ In particular, for $p=k$ and $q=k(d-1)\cdot\!\left(\tfrac{ek^{2}}{\varepsilon}\right)^{d}$ , the size of $\mathcal{H}$ is at most $\left(\tfrac{1}{\varepsilon}\right)^{\mathcal{O}(dk\log k)}\log n.$

For our purposes we set $p\coloneqq k\quad\text{and}\quad q\coloneqq k(d-1)\!\left(\tfrac{ek^{2}}{% \varepsilon}\right)^{d}.$ Equivalently, let $\Delta_{\star}\coloneqq(d-1)\!\left(\tfrac{ek^{2}}{\varepsilon}\right)^{d}$ ; then $q=k\,\Delta_{\star}$ . By Proposition 7, this yields an $(n,p,q)$ lopsided-universal family $\mathcal{H}$ of size $\left(\tfrac{1}{\varepsilon}\right)^{\mathcal{O}(dk\log k)}\log n.$ If in addition $\Delta(G_{\texttt{conf}})\leq\Delta_{\star}$ , then $k\,\Delta(G_{\texttt{conf}})\leq q$ , so the same family suffices for enforcing $S^{\star}\subseteq f^{-1}(\text{{\color[rgb]{.75,0,.25}\definecolor[named]{% pgfstrokecolor}{rgb}{.75,0,.25}purple}})$ and $N_{G_{\texttt{conf}}}(S^{\star})\subseteq f^{-1}(\text{{\color[rgb]{% 0.0,0.47,0.44}\definecolor[named]{pgfstrokecolor}{rgb}{0.0,0.47,0.44}green}})$ .

Filtering of Connected Components.

For every coloring $f\in\mathcal{H}$ we proceed as follows. Delete all green vertices, i.e., set $V_{\mathrm{green}}\coloneqq f^{-1}(\text{{\color[rgb]{0.0,0.47,0.44}% \definecolor[named]{pgfstrokecolor}{rgb}{0.0,0.47,0.44}green}})$ and form $G_{\texttt{conf}}^{f}\coloneqq G_{\texttt{conf}}-V_{\mathrm{green}}$ . The remaining graph $G_{\texttt{conf}}^{f}$ is a disjoint union of connected components, each an induced subgraph of $G_{\texttt{conf}}$ on the purple vertices $V_{\mathrm{purple}}\coloneqq f^{-1}(\text{{\color[rgb]{.75,0,.25}\definecolor[% named]{pgfstrokecolor}{rgb}{.75,0,.25}purple}})$ . Finally, discard every purple component $C$ with $|C|>k$ ; let $\mathcal{C}_{\leq k}(f)$ denote the family of surviving components (those with $|C|\leq k$ ).

Motivation for the filtering step.

Assume the instance is a Yes-instance and let $S^{\star}\subseteq R$ , $|S^{\star}|\leq k$ , satisfy ( $\mathsf{P}1$ ) and ( $\mathsf{P}2$ ). While $G_{\texttt{conn}}[S^{\star}]$ is connected, the conflict graph $G_{\texttt{conf}}$ need not be a subgraph of $G_{\texttt{conn}}$ : there may exist $u,v\in R$ that are nonadjacent in $G_{\texttt{conn}}$ but adjacent in $G_{\texttt{conf}}$ due to a large overlap of their neighborhoods in $G_{\texttt{cov}}$ (so $uv\in E(G_{\texttt{conf}})$ but $uv\notin E(G_{\texttt{conn}})$ ). Conversely, $G_{\texttt{conf}}[S^{\star}]$ need not be connected even though $G_{\texttt{conn}}[S^{\star}]$ is: some pairs $u,v\in S^{\star}$ that are adjacent in $G_{\texttt{conn}}$ can become nonadjacent in $G_{\texttt{conf}}$ by the very definition of the conflict graph (so $uv\in E(G_{\texttt{conn}})$ but $uv\notin E(G_{\texttt{conf}})$ ).

Let $C_{1}^{\star},\dots,C_{\ell}^{\star}$ be the connected components of $G_{\texttt{conf}}[S^{\star}]$ , where $1\leq\ell\leq|S^{\star}|\leq k$ . Clearly $S^{\star}=\bigcup_{i=1}^{\ell}V(C_{i}^{\star})$ . (When convenient, we do not distinguish between a component $C$ and its vertex set $V(C)$ .)

By the choice of the lopsided-universal family $\mathcal{H}$ , there exists $f\in\mathcal{H}$ with $S^{\star}\subseteq V_{\mathrm{purple}}$ and $N_{G_{\texttt{conf}}}(S^{\star})\subseteq V_{\mathrm{green}}$ . For this good $f$ , deleting $V_{\mathrm{green}}$ removes no vertex of $S^{\star}$ , and the purple subgraph $G_{\texttt{conf}}^{f}=G_{\texttt{conf}}-V_{\mathrm{green}}$ still contains $G_{\texttt{conf}}[S^{\star}]$ unchanged; in particular, each $C_{i}^{\star}$ remains a connected purple component. Since $|V(C_{i}^{\star})|\leq|S^{\star}|\leq k$ , all these components survive the size filter. Thus, the filtering step preserves every piece of $S^{\star}$ we care about while discarding large purple components that cannot be part of any size- $k$ solution.

Constructing $G_{\texttt{conf}}^{\mathrm{purple}}:$ Recall that $\mathcal{C}_{\leq k}(f)$ denotes the family of surviving (purple) components, i.e., the connected components of $G_{\texttt{conf}}-V_{\mathrm{green}}$ whose sizes are at most $k$ . Fix a coloring $f\in\mathcal{H}$ and enumerate

\mathcal{C}\;\coloneqq\;\mathcal{C}_{\leq k}(f)\;=\;\{C_{1},C_{2},\dots,C_{s}% \},\quad\text{so that}\quad 1\leq|C_{i}|\leq k\ \text{for all }i\in[s].

We refer to the filtered purple subgraph as

G_{\texttt{conf}}^{\mathrm{purple}}\;\coloneqq\;G_{\texttt{conf}}[V_{\mathrm{% purple}}]\;-\!\!\!\!\bigcup_{\begin{subarray}{c}C\subseteq V_{\mathrm{purple}}% \\ C\text{ is a purple component}\\ |C|>k\end{subarray}}\!\!\!\!C,

so each $C_{i}\in\mathcal{C}$ is a connected component of $G_{\texttt{conf}}^{\mathrm{purple}}$ with $1\leq|C_{i}|\leq k$ . (When clear from context, we drop the explicit dependence on $f$ .) The next observation follows from the construction of $G_{\texttt{conf}}^{\mathrm{purple}}$ .

Observation 8.

$V\left(G_{\texttt{conf}}^{\mathrm{purple}}\right)\subseteq V\left(G_{\texttt{% conf}}\right)=V\left(G_{\texttt{conn}}\right)=R$ .

5.3 Step 3: Construction of Sparsified Graph

The goal here is to compute a bipartite graph which is called as sparsified graph (will be defined shortly) which will eventually help us find an approximate solution. To this end, we first consider the induced bipartite subgraph of $G_{\texttt{cov}}$ defined on the vertices $V\left(G_{\texttt{conf}}^{\mathrm{purple}}\right)$ and $B$ , namely $G_{\texttt{cov}}\bigl[V\left(G_{\texttt{conf}}^{\mathrm{purple}}\right)\uplus B\bigr]$ . Based on $G_{\texttt{cov}}\bigl[V\left(G_{\texttt{conf}}^{\mathrm{purple}}\right)\uplus B\bigr]$ and $G_{\texttt{conf}}^{\mathrm{purple}}$ , we construct another bipartite graph, called sparsified graph, denoted by $G_{\texttt{spar}}$ as follows:

Construction of $G_{\texttt{spar}}$

$\blacksquare$

$V\left(G_{\texttt{spar}}\right)\coloneqq V\left(G_{\texttt{conf}}^{\mathrm{% purple}}\right)\uplus B$ (two parts of the bipartite graph).
$\blacksquare$

Let $\mathcal{C}=\left\{C_{1},\dots C_{s}\right\}$ be the set of components in $G_{\texttt{conf}}^{\mathrm{purple}}$ . Now we have the following Sparsification process which helps to construct the edges in the sparsified graph.

Sparsification Process: For every $b\in B$ and every $C_{i}\in\mathcal{C}$ , let $E_{b}$ denote the set of edges of $G_{\texttt{cov}}$ with one endpoint at $b$ and the other endpoint at a neighbor of $b$ in the component $C_{i}$ in graph $G_{\texttt{cov}}$ . More formally, $E_{b}\coloneqq\left\{xb\in E(G_{\texttt{cov}})\mid x\in V(C_{i})\cap N_{G_{% \texttt{cov}}}(b)\right\}$ .

Now we construct $E(G_{\texttt{spar}})$ as follows: for every $b\in B$ , if $E_{b}\neq\emptyset$ , then add an arbitrary edge from $E_{b}$ to $E(G_{\texttt{spar}})$ .

We now summarize few key properties of $G_{\texttt{spar}}$ .

Properties of $G_{\texttt{spar}}$

Let $\mathcal{C}=\big\{C_{1},\dots C_{s}\big\}$ be the set of connected components in $G_{\texttt{conf}}^{\mathrm{purple}}$ and $G_{\texttt{spar}}$ be the graph defined above.

Property 9.

For every connected component $C_{i}\in\mathcal{C}$ of $G_{\texttt{conf}}^{\mathrm{purple}}$ and every subset of vertices $X\subseteq V(C_{i})$ , it holds that,

(i)	$\displaystyle\big\|N_{G_{\texttt{spar}}}(X)\big\|=\sum_{x\in X}\big\|N_{G_{% \texttt{spar}}}(x)\big\|=\sum_{x\in X}{\sf deg}_{G_{\texttt{spar}}}(x)$		(1)
(ii)	$\displaystyle N_{G_{\texttt{spar}}}(X)\subseteq N_{G_{\texttt{cov}}}(X)$	$\left(\text{if}\nobreak\ \nobreak\ X\subset V(C_{i})\right)$	(2)
(iii)	$\displaystyle N_{G_{\texttt{spar}}}(V(C_{i}))=N_{G_{\texttt{cov}}}(V(C_{i}))$	$\left(\text{if}\nobreak\ \nobreak\ X=V(C_{i})\right)$	(3)

Property 10.

Consider any pair of vertices $x\in V(C_{i})$ and $y\in V(C_{j})$ where $i,j\in[s]$ . It holds that,

	$\displaystyle\text{(i)}\nobreak\ \nobreak\ \big\|N_{G_{\texttt{spar}}}(x)\cap N% _{G_{\texttt{spar}}}(y)\big\|<\frac{\varepsilon t}{k^{2}}\quad\text{ when $i% \neq j$ and}$		(4)
	$\displaystyle\text{(ii)}\nobreak\ \nobreak\ N_{G_{\texttt{spar}}}(x)\cap N_{G_% {\texttt{spar}}}(y)=\emptyset\quad\text{ when $i=j$}$		(5)

Proof for Property 9.

(i)

Equation 1 follows directly from the construction of $G_{\texttt{spar}}$ , obtained as a result of Sparsification Process. More specifically, it follows that for every vertex $b\in B$ and for every component $C_{i}\in\mathcal{C}$ , the vertex $b$ is adjacent to at most one vertex of $C_{i}$ in $G_{\texttt{spar}}$ . Thus, the vertex $b$ contributes either $0$ or $1$ to each of the three terms in Equation 1, and in each case, its contribution is same. This establishes the desired property.
(ii)

It is clear that $N_{G_{\texttt{spar}}}(X)\subseteq N_{G_{\texttt{cov}}}(X)$ , because every vertex $v\in N_{G_{\texttt{spar}}}(X)$ must also belong to $N_{G_{\texttt{cov}}}(X)$ , given that $G_{\texttt{spar}}$ is a subgraph of $G_{\texttt{cov}}$ .
(iii)

Moreover, when $X=V(C_{i})$ and $b\in B$ is a vertex that has a neighbor in $C_{i}$ in the graph $G_{\texttt{spar}}$ , then by the definition of the Sparsification Process, we have that $b$ is in fact adjacent to exactly one vertex of $C_{i}$ in $G_{\texttt{spar}}$ . Thus $b$ contributes $1$ to both sides of Equation 3.

$\hfill\blacktriangleleft$

Proof for Property 10.

(i)

Equation 4 follows directly from the property of $G_{\texttt{conf}}$ . Note that, $N_{G_{\texttt{spar}}}(x)\cap N_{G_{\texttt{spar}}}(y)\subseteq N_{G_{\texttt{% cov}}}(x)\cap N_{G_{\texttt{cov}}}(y)$ since $G_{\texttt{spar}}$ is a subgraph of $G_{\texttt{cov}}$ . Further since $x\in V(C_{i}),y\in V(C_{j})$ for $i\neq j$ , we have that $x$ and $y$ are non-adjacent in $G_{\texttt{conf}}$ , this implies that $\big|N_{G_{\texttt{cov}}}(x)\cap N_{G_{\texttt{cov}}}(y)\big|<\frac{% \varepsilon t}{k^{2}}$ (by definition) which further implies that $\big|N_{G_{\texttt{spar}}}(x)\cap N_{G_{\texttt{spar}}}(y)\big|<\frac{% \varepsilon t}{k^{2}}$ .
(ii)

Suppose, for the sake of contradiction, there exists a pair of vertices $x,y\in V(C_{i})$ for some $C_{i}$ satisfying $N_{G_{\texttt{spar}}}(x)\cap N_{G_{\texttt{spar}}}(y)\neq\emptyset$ . Let $z\in N_{G_{\texttt{spar}}}(x)\cap N_{G_{\texttt{spar}}}(y)$ . This contradicts the property of $G_{\texttt{spar}}$ , since $G_{\texttt{spar}}$ is obtained as a result of Sparsification Process, which ensures that both edges $x z$ and $y z$ cannot simultaneously appear in $E(G_{\texttt{spar}})$ .

$\hfill\blacktriangleleft$

In the next section, we assign weights to the vertices of $G_{\texttt{conf}}^{\mathrm{purple}}$ , where each weight reflects the number of vertices dominated by that vertex in $G_{\texttt{spar}}$ .

5.4 Step 4: Introducing vertex weights to $V\bigl(G_{\texttt{conf}}^{\mathrm{purple}}\bigr)$

In this section, we assign weights to the vertices of the graph $G_{\texttt{conf}}^{\mathrm{purple}}$ . Let $w:V\bigl(G_{\texttt{conf}}^{\mathrm{purple}}\bigr)\to\mathbb{Z}_{\geq 0}$ be a weight function defined on $V\bigl(G_{\texttt{conf}}^{\mathrm{purple}}\bigr)$ as follows:

w(v)=\big|N_{G_{\texttt{spar}}}(v)\big|={\sf deg}_{G_{\texttt{spar}}}(v)\quad% \quad\text{for every }v\in V\left(G_{\texttt{conf}}^{\mathrm{purple}}\right)

(6)

By Observation 8, we have $V(G_{\texttt{conf}}^{\mathrm{purple}})\subseteq V(G_{\texttt{conf}})=V(G_{% \texttt{conn}})=R$ . Therefore, the assigned weights are restricted to a subset of the vertices in $R$ . Before proceeding further, it is important to note the following assumptions, which will be maintained throughout the subsequent discussion.

We now state a crucial lemma that, via the weight function defined above, provides a lower bound on the $G_{\texttt{cov}}$ -coverage of any set $Y\subseteq V(G_{\texttt{conf}}^{\mathrm{purple}})$ with $|Y|\leq k$ ; equivalently, it lower-bounds $|N_{G_{\texttt{cov}}}(Y)|$ for all such $Y$ .

Lemma 11.

For any subset $Y\subseteq V\bigl(G_{\texttt{conf}}^{\mathrm{purple}}\bigr)$ of size at most $k$ , it holds that

\displaystyle\big|N_{G_{\texttt{cov}}}(Y)\big|\geq\big|N_{G_{\texttt{spar}}}(Y% )\big|\geq\sum\limits_{y\in Y}w(y)-\varepsilon t

(7)

Proof.

By Inclusion-exclusion Principle, we have

$\displaystyle\big\|N_{G_{\texttt{spar}}}(Y)\big\|$	$\displaystyle=$	$\displaystyle\sum\limits_{y\in Y}\big\|N_{G_{\texttt{spar}}}(y)\big\|-\sum% \limits_{x,y\in Y}\big\|N_{G_{\texttt{spar}}}(x)\cap N_{G_{\texttt{cov}}}(y)\big\|$	(8)
	$\displaystyle+$	$\displaystyle\sum\limits_{x,y,z\in Y}\big\|N_{G_{\texttt{spar}}}(x)\cap N_{G_{% \texttt{spar}}}(y)\cap N_{G_{\texttt{spar}}}(z)\big\|-\dotsm$	(8)
	$\displaystyle\stackrel{{\scriptstyle(\P)}}{{\geq}}$	$\displaystyle\sum\limits_{y\in Y}\big\|N_{G_{\texttt{spar}}}(y)\big\|-\sum% \limits_{x,y\in Y}\big\|N_{G_{\texttt{spar}}}(x)\cap N_{G_{\texttt{spar}}}(y)\big\|$	(9)
	$\displaystyle=$	$\displaystyle\sum\limits_{y\in Y}w(y)-\sum\limits_{x,y\in Y}\big\|N_{G_{\texttt% {spar}}}(x)\cap N_{G_{\texttt{spar}}}(y)\big\|$	(10)

Here, inequality $(\P)$ holds because, in Line 9, we truncate the Inclusion–Exclusion formula by discarding all terms from the $3^{\textnormal{rd}}$ term onward, thereby obtaining a lower bound on the original expression. Line 10 follows from Equation 6. Now, it remains to provide an upper bound on ${\sum}\limits_{x,y\in Y}\big|N_{G_{\texttt{spar}}}(x)\cap N_{G_{\texttt{spar}}% }(y)\big|$ .

Recall that $\mathcal{C}=\left\{C_{1},\dots C_{s}\right\}$ is the set of connected components in $G_{\texttt{conf}}^{\mathrm{purple}}$ . For each $i\in[s]$ , consider the restriction of the connected component $C_{i}$ to $Y$ , namely $C_{i}^{Y}\coloneqq V(C_{i})\cap Y$ . Note that $G_{\texttt{conf}}^{\mathrm{purple}}[C_{i}^{Y}]$ need not be connected. Without loss of generality, we assume that for every $i\in[s]$ , $C_{i}^{Y}\neq\emptyset$ , i.e., it contains at least one vertex from $Y$ ; otherwise, we discard the empty components from the collection $\left\{C_{i}^{Y},\dots,C_{s}^{Y}\right\}$ . Thus we can write,
$\displaystyle\sum\limits_{x,y\in Y}\big|N_{G_{\texttt{spar}}}(x)\cap N_{G_{% \texttt{spar}}}(y)\big|=\sum\limits_{\begin{subarray}{c}i\in[s],\\ x,y\in C^{Y}_{i}\end{subarray}}\big|N_{G_{\texttt{spar}}}(x)\cap N_{G_{\texttt% {spar}}}(y)\big|+\sum\limits_{\begin{subarray}{c}i,j\in[s],i\neq j\\ x\in C^{Y}_{i},\\ y\in C^{Y}_{j}\end{subarray}}\big|N_{G_{\texttt{spar}}}(x)\cap N_{G_{\texttt{% spar}}}(y)\big|$ (11)

Notice that due to Equation 5 of Property 10, we have that for every $C_{i}\in\mathcal{C}$ and for every $x,y\nobreak\ \in V(C_{i})$ , it holds that $N_{G_{\texttt{spar}}}(x)\cap N_{G_{\texttt{spar}}}(y)=\emptyset$ . Hence the first term of Equation 11 becomes $0$ .

Moreover, by Equation 4 in Property 10, for all distinct $i,j\in[s]$ and all vertices $x\in C_{i}^{Y}\subseteq V(C_{i})$ and $y\in C_{j}^{Y}\subseteq V(C_{j})$ , we have

\bigl|N_{G_{\texttt{spar}}}(x)\cap N_{G_{\texttt{spar}}}(y)\bigr|\;<\;\frac{% \varepsilon t}{k^{2}},

since $x$ and $y$ are nonadjacent in the conflict graph $G_{\texttt{conf}}$ . Since $|Y|\leq k$ , there are at most $\binom{k}{2}$ pairs in $Y$ . Hence the second component of Equation 11 is upper bounded by $\binom{k}{2}\cdot\frac{\varepsilon t}{k^{2}}\leq k^{2}\cdot\frac{\varepsilon t% }{k^{2}}=\varepsilon t$ . Substituting these values in Equation 11, we obtain

\sum\limits_{x,y\nobreak\ \in Y}\big|N_{G_{\texttt{spar}}}(x)\cap N_{G_{% \texttt{spar}}}(y)\big|\leq\varepsilon t

Substituting all these values in Equation 7, we get that $\big|N_{G_{\texttt{spar}}}(Y)\big|\geq\sum\limits_{y\in Y}w(y)-\varepsilon t$ . Furthermore, since $G_{\texttt{spar}}$ is a subgraph of $G_{\texttt{cov}}$ , we have

\bigl|N_{G_{\texttt{cov}}}(Y)\bigr|\;\geq\;\bigl|N_{G_{\texttt{spar}}}(Y)\bigr|.

(Equivalently, this follows by repeatedly applying Equation 2 from Property 9.) This proves the lemma. $\hfill\blacktriangleleft$

We now require a converse to Lemma 11: an upper bound on the $G_{\texttt{cov}}$ -coverage of any set $X\subseteq V(G_{\texttt{conf}}^{\mathrm{purple}})$ with $|X|\leq k$ , expressed in terms of the weight function defined above; equivalently, we seek to upper bound $|N_{G_{\texttt{cov}}}(X)|$ for all such $X$ . However, we cannot establish this bound for arbitrary $X$ . Instead, we prove it for a particular class of sets, which is sufficient for our purposes. The next definition characterizes this class.

Definition 12 (Component-respecting set).

Let $\mathcal{C}=\{C_{1},\dots,C_{s}\}$ be the collection of all connected components of $G_{\texttt{conf}}^{\mathrm{purple}}$ . A set $Z\subseteq V(G_{\texttt{conf}}^{\mathrm{purple}})$ is component-respecting $\left(\textnormal{w.r.t.}\nobreak\ G_{\texttt{conf}}^{\mathrm{purple}}\right)$ if for every $i\in[s]$ , either $C_{i}\subseteq Z$ or $Z\cap C_{i}=\emptyset$ . Equivalently, $Z$ is a union of some components from $\mathcal{C}$ , in other words, there exists $I\subseteq[s]$ with $Z=\bigcup_{i\in I}C_{i}$ .

Lemma 13.

For any component-respecting set $X\subseteq V\left(G_{\texttt{conf}}^{\mathrm{purple}}\right)$ , it holds that

\displaystyle\sum\limits_{x\in X}w(x)\geq\big|N_{G_{\texttt{cov}}}(X)\big|

(12)

Proof.

We know that,

\displaystyle\sum\limits_{x\in X}w(x)=\sum\limits_{x\in X}\big|N_{G_{\texttt{% spar}}}(x)\big|\quad\quad\quad\quad\textnormal{(due to the definition in % \lx@cref{creftypecap~refnum}{eqn:weightfunction})}

(13)

Thus, it suffices to show that

\displaystyle\sum\limits_{x\in X}\big|N_{G_{\texttt{spar}}}(x)\big|\geq\big|N_% {G_{\texttt{cov}}}(X)\big|

(14)

Every vertex $b\in N_{G_{\texttt{cov}}}(X)\subseteq B$ contributes $1$ to the right-hand side of Equation 14, since every neighbor of $X$ in $G_{\texttt{cov}}$ is counted once in $\big|N_{G_{\texttt{cov}}}(X)\big|$ . To establish Lemma 13, it suffices to show that every vertex $b\in N_{G_{\texttt{cov}}}(X)\subseteq B$ contributes at least $1$ to the left-hand side of Equation 14. Recall that $\mathcal{C}=\left\{C_{1},\dots,C_{s}\right\}$ denotes the set of connected components in $G_{\texttt{conf}}^{\mathrm{purple}}$ . Consider an arbitrary vertex $b\in N_{G_{\texttt{cov}}}(X)$ and an arbitrary component $C_{i}\in\mathcal{C}$ of $G_{\texttt{conf}}^{\mathrm{purple}}$ such that $b\in N_{G_{\texttt{cov}}}(V(C_{i}))$ . Note that such a component exists since $b\in N_{G_{\texttt{cov}}}(X)$ . Since $X$ is component-respecting with respect to $G_{\texttt{conf}}^{\mathrm{purple}}$ , it holds that $V(C_{i})\cap X=V(C_{i})$ , i.e., $V(C_{i})\subseteq X$ . Thus, by Equation 3, we have $N_{G_{\texttt{spar}}}\!\bigl(V(C_{i})\bigr)=N_{G_{\texttt{cov}}}\!\bigl(V(C_{i% })\bigr)$ . Hence, by the construction of $G_{\texttt{spar}}$ , we have that $b$ is adjacent to some $x\in V(C_{i})$ in $G_{\texttt{spar}}$ , i.e., $b\in N_{G_{\texttt{spar}}}(x)$ . Hence $b$ contributes $1$ to $|N_{G_{\texttt{spar}}}(x)|$ in the sum on the left-hand side of Equation 14 which concludes the Lemma. $\hfill\blacktriangleleft$

5.5 Step 5: Finding a Maximum Weighted Subtree in $G_{\texttt{conn}}\left[V(G_{\texttt{conf}}^{\mathrm{purple}})\right]$

In this section we work in the vertex-weighted graph $G_{\texttt{conn}}\!\left[V(G_{\texttt{conf}}^{\mathrm{purple}})\right]$ , endowed with the weight function $w$ defined above (in Equation 6). Our goal is to find a subtree on at most $k$ vertices maximizing total weight (the weight of a tree is the sum of the weights of its vertices). We formalize this as the following subproblem.

Maximum-Weight $k$ -Tree:: Given a graph $G$ , a weight function $\gamma:V(G)\to\mathbb{Z}_{\geq 0}$ , and an integer $k$ , find a subtree $T_{G}\subseteq G$ with $|V(T_{G})|\leq k$ maximizing $\gamma(T_{G})\coloneqq\sum_{v\in V(T_{G})}\gamma(v)$ .

We solve this via Weighted Tree Isomorphism.

Weighted Tree Isomorphism:: Given a host graph $G$ , a tree $T$ , and a weight function $\gamma:V(G)\to\mathbb{Z}_{\geq 0}$ , find (if it exists) a subgraph $T_{G}\subseteq G$ isomorphic to $T$ and of maximum total weight $\gamma(T_{G})$ .

Proposition 14.

Weighted Tree Isomorphism can be solved in time $2^{{\mathcal{O}}(h)}\,n^{\mathcal{O}(1)}$ , where $h=|V(T)|$ and $n=|V(G)|$ .

Proposition 14 follows from standard techniques. One route is the classic color-coding framework of Alon, Yuster, and Zwick [1, Thm. 6.3], whose dynamic program extends to the weighted objective by maximizing (rather than merely detecting) over states; see the discussion following [1, Thm. 6.3] (cf. also [38]). Alternatively, representative-family techniques yield the same running time with a weight-aware state space [16].

To solve Maximum-Weight $k$ -Tree, we enumerate all non-isomorphic trees on at most $k$ vertices and, for each such tree $T$ , run Weighted Tree Isomorphism (Proposition 14). Otter [37] showed that the number of non-isomorphic (unrooted) trees on $h$ vertices is $t_{h}=2.956^{h}$ . Moreover, all non-isomorphic rooted trees on $h$ vertices can be generated in time $\mathcal{O}(t_{h}\,h)$ by the algorithm of Beyer and Hedetniemi [4].

Proposition 15 ([37, 4]).

The number of non-isomorphic trees on $h$ vertices is $t_{h}=2.956^{h}$ . Furthermore, all non-isomorphic rooted trees on $h$ vertices can be enumerated in time $\mathcal{O}(t_{h}\,h)$ .

Combining Proposition 15 with Proposition 14 yields:

Lemma 16.

Maximum-Weight $k$ -Tree can be solved in time $2^{\mathcal{O}(k)}\,n^{\mathcal{O}(1)}$ .

Proof.

There are $t_{k^{\star}}=2.956^{k^{\star}}$ , $k^{\star}\leq k$ , non-isomorphic trees on $k^{\star}$ vertices. For each such tree $T$ , Weighted Tree Isomorphism runs in $2^{\mathcal{O}(k^{\star})}\,n^{\mathcal{O}(1)}$ time (Proposition 14). Hence the total running time is $t_{k}\cdot 2^{\mathcal{O}(k)}\,n^{\mathcal{O}(1)}=2^{\mathcal{O}(k)}\,n^{% \mathcal{O}(1)}$ . $\hfill\blacktriangleleft$

5.6 Putting all the Pieces Together

By assembling all the components and present the complete algorithm as pseudocode in Algorithm 1, we now obtain the main theorem of this section, and prove it by combining the tools and ideas developed above.

Algorithm 1 AlgPartialConnRBDS.

Theorem 17.

Let $\mathcal{I}=(G_{\texttt{cov}},G_{\texttt{conn}},k,t)$ be an instance of PartialConRBDS, where $G_{\texttt{cov}}$ and $G_{\texttt{conn}}$ are the coverage and connectivity graphs, respectively. If $G_{\texttt{cov}}$ is $K_{d,d}$ -free, then for every $\varepsilon\in(0,1)$ there is an algorithm running in time $\mathcal{O}^{\star}\!\bigl(2^{\mathcal{O}(k^{2}d/\varepsilon)}\bigr)$ that either

(i)

outputs a set $S\subseteq R$ with $|S|\leq k$ , $G_{\texttt{conn}}[S]$ connected, and $|N_{G_{\texttt{cov}}}(S)|\geq(1-\varepsilon)t$ , or
(ii)

correctly concludes that no size- $k$ set dominates at least $t$ vertices in $G_{\texttt{cov}}$ .

Proof.

We first show that, if the instance is a Yes-instance, our algorithm returns a set $S\subseteq R$ with $|S|\leq k$ , $G_{\texttt{conn}}[S]$ connected, and $|N_{G_{\texttt{cov}}}(S)|\geq(1-\varepsilon)t$ . Let $S^{\star}\subseteq R$ be a size- $\leq k$ witness satisfying ( $\mathsf{P}1$ ) (i.e., $G_{\texttt{conn}}[S^{\star}]$ is connected) and ( $\mathsf{P}2$ ) (i.e., $|N_{G_{\texttt{cov}}}(S^{\star})|\geq t$ ).

Small $t$ . If $t<\tfrac{k^{2}d}{\varepsilon}$ , algorithm invokes the exact FPT algorithm of Theorem 4 to decide and, if possible, return a size- $\leq k$ connected solution covering at least $t$ vertices.

Large $t$ . Assume $t\geq\tfrac{k^{2}d}{\varepsilon}$ . The algorithm implements the purple/green separation by enumerating an $(n,p,q)$ lopsided-universal family $\mathcal{H}$ (Proposition 7) with $p=k$ and $q=k(d-1)\!\left(\tfrac{ek^{2}}{\varepsilon}\right)^{d}$ . By the defining property of such families, there exists a good $f\in\mathcal{H}$ with $S^{\star}\subseteq V_{\mathrm{purple}}$ and $N_{G_{\texttt{conf}}}(S^{\star})\subseteq V_{\mathrm{green}}$ . Fix this $f$ .

We delete all green vertices and retain only purple components of size at most $k$ (the filtering step); this preserves each connected piece $C_{i}^{\star}$ of $G_{\texttt{conf}}[S^{\star}]$ . We then define the vertex-weight function $w$ on $V(G_{\texttt{conf}}^{\mathrm{purple}})$ (equivalently, on the host $G_{\texttt{conn}}[V(G_{\texttt{conf}}^{\mathrm{purple}})]$ ), as in Step 4 (Section 5.4). Finally, let $T_{f}$ be a maximum-weight subtree on $k$ vertices in $G_{\texttt{conn}}[V(G_{\texttt{conf}}^{\mathrm{purple}})]$ , computed via Lemma 16.

We can potentially take $S\coloneqq V(T_{f})$ . Since $V(T_{f})\subseteq V(G_{\texttt{conf}}^{\mathrm{purple}})$ and $|V(T_{f})|=k$ , by Lemma 11 we have

\bigl|N_{G_{\texttt{cov}}}(V(T_{f}))\bigr|\;\geq\;\sum_{\mathfrak{f}\in V(T_{f% })}w(\mathfrak{f})\;-\;\varepsilon t.

(15)

Recall that $S^{\star}$ has $|S^{\star}|\leq k$ and $G_{\texttt{conn}}[S^{\star}]$ connected; let $T^{\star}$ be any spanning tree of $G_{\texttt{conn}}[S^{\star}]$ . Since $S^{\star}\subseteq V_{\mathrm{purple}}$ and each connected piece $C_{i}^{\star}$ has size at most $k$ , the filtering step preserves $G_{\texttt{conn}}[S^{\star}]$ , hence $T^{\star}\subseteq G_{\texttt{conn}}[V(G_{\texttt{conf}}^{\mathrm{purple}})]$ . Because $T_{f}$ is a maximum-weight $k$ -vertex tree in $G_{\texttt{conn}}[V(G_{\texttt{conf}}^{\mathrm{purple}})]$ ,

\sum_{\mathfrak{f}\in V(T_{f})}w(\mathfrak{f})\;\geq\;\sum_{v\in V(T^{\star})}% w(v)\;\geq\;\sum_{\mathfrak{s}\in S^{\star}}w(\mathfrak{s}).

(16)

Moreover, by Lemma 13 applied to $S^{\star}$ and using $|N_{G_{\texttt{cov}}}(S^{\star})|\geq t$ ,

\sum_{\mathfrak{s}\in S^{\star}}w(\mathfrak{s})\;\geq\;\bigl|N_{G_{\texttt{cov% }}}(S^{\star})\bigr|\;\geq\;t.

(17)

Substituting (16) and (17) into (15) yields

	$\displaystyle\bigl\|N_{G_{\texttt{cov}}}(V(T_{f}))\bigr\|$	$\displaystyle\geq\sum_{\mathfrak{f}\in V(T_{f})}w(\mathfrak{f})-\varepsilon t$
		$\displaystyle\geq\sum_{\mathfrak{s}\in S^{\star}}w(\mathfrak{s})-\varepsilon t$
		$\displaystyle\geq t-\varepsilon t\;=\;(1-\varepsilon)t.$

Thus $S=V(T_{f})$ satisfies $|S|\leq k$ , $G_{\texttt{conn}}[S]$ is connected, and $|N_{G_{\texttt{cov}}}(S)|\geq(1-\varepsilon)t$ .

Our algorithm outputs either $\widetilde{T}$ , the maximum-weight $k$ -vertex subtree in $G_{\texttt{conn}}[V(G_{\texttt{conf}}^{\mathrm{purple}})]$ over all colorings $f\in\mathcal{H}$ , or $\bot$ if $w(\widetilde{T})<t$ . Since there exists a good $f$ with $w(T_{f})\geq\sum_{\mathfrak{s}\in S^{\star}}w(\mathfrak{s})\geq t$ , we have $w(\widetilde{T})\geq w(T_{f})\geq t$ , and thus the algorithm never returns $\bot$ . Set $S\coloneqq V(\widetilde{T})$ . Because $V(\widetilde{T})\subseteq V(G_{\texttt{conf}}^{\mathrm{purple}})$ and $|V(\widetilde{T})|=k$ , by Lemma 11 we obtain

	$\displaystyle\bigl\|N_{G_{\texttt{cov}}}(V(\widetilde{T}))\bigr\|$	$\displaystyle\geq\sum_{\mathfrak{f}\in V(\widetilde{T})}w(\mathfrak{f})-\varepsilon t$
		$\displaystyle\geq\sum_{\mathfrak{f}\in V(T_{f})}w(\mathfrak{f})-\varepsilon t$
		$\displaystyle\geq\sum_{\mathfrak{s}\in S^{\star}}w(\mathfrak{s})-\varepsilon t$
		$\displaystyle\geq t-\varepsilon t\;=\;(1-\varepsilon)t.$

Hence $S$ satisfies the coverage guarantee. Since our guarantee is conditioned on Yes-instances and we do not require bounds for the No-instance case, this completes the description of the algorithm’s correctness and approximation analysis.

Running time.

Small- $t$ case. When $t<\tfrac{k^{2}d}{\varepsilon}$ we invoke the exact routine of Theorem 4, which runs in time

T_{\text{small}}=\mathcal{O}^{\star}\!\bigl(2^{\mathcal{O}(t)}\bigr)\;\leq\;% \mathcal{O}^{\star}\!\bigl(2^{\mathcal{O}(k^{2}d/\varepsilon)}\bigr).

Large- $t$ case. For $t\geq\tfrac{k^{2}d}{\varepsilon}$ we enumerate an $(n,p,q)$ lopsided-universal family $\mathcal{H}$ (Proposition 7) with $p=k$ and $q=k(d-1)\!\left(\tfrac{ek^{2}}{\varepsilon}\right)^{d}$ , whose size satisfies $|\mathcal{H}|\leq\left(\tfrac{1}{\varepsilon}\right)^{\mathcal{O}(dk\log k)}\log n$ . For each $f\in\mathcal{H}$ , all preprocessing – forming $G_{\texttt{conf}}^{\mathrm{purple}}$ , filtering to components of size $\leq k$ , and computing the needed sparsifiers – is polynomial in $n$ . The only exponential step per $f$ is solving Maximum-Weight $k$ -Tree in the host $G_{\texttt{conn}}[V(G_{\texttt{conf}}^{\mathrm{purple}})]$ , which takes $2^{\mathcal{O}(k)}n^{\mathcal{O}(1)}$ time (Lemma 16). Hence

T_{\text{large}}=\mathcal{O}^{\star}\!\Bigl(|\mathcal{H}|\cdot 2^{\mathcal{O}(% k)}\Bigr)=\mathcal{O}^{\star}\!\Bigl(\left(\tfrac{1}{\varepsilon}\right)^{% \mathcal{O}(dk\log k)}\cdot 2^{\mathcal{O}(k)}\Bigr).

Combined bound. Taking the worse of the two regimes and hiding polynomial factors, the overall running time is

\mathcal{O}^{\star}\!\bigl(2^{\mathcal{O}(k^{2}d/\varepsilon)}\bigr),

which matches the bound stated in Theorem 17. This conludes the proof. $\hfill\blacktriangleleft$

6 Conclusion

We introduced Partial Connected Red-Blue Dominating Set (PartialConRBDS) as a unifying model for many connectivity-constrained coverage problems that have been studied in prior polynomial-time approximation literature. The expressivity of our model comes from having two separate graphs (i) $G_{\texttt{conn}}$ for imposing structural properties on the solution (in our case, connectivity), and (ii) $G_{\texttt{cov}}$ for modeling hypergraph incidences (which we use for requiring certain amount of coverage). We hope that this will serve as a model for understanding a variety of problems from this two-layer perspective.

As for our algorithmic contributions, we began with an exact FPT algorithm parameterized by $t$ . In the realm of FPT approximation, we focused on biclique-free instances, and designed an EPAS that finds a size- $k$ connected set that dominates at least $(1-\varepsilon)t$ blue vertices; and a complementary PAS that finds a connected set of size at most $(1+\varepsilon)k$ that covers $t$ blue vertices. Our key tool is a small family of surrogate weight functions built via neighborhood sparsification procedure, which lets us reduce the search to maximum-weight $k$ -trees in $G_{\mathrm{conn}}$ . Among the lower bound results, the main takeaway is that the problem inherits strong $\mathsf{W}$ -hardness and approximation lower bounds from Max Coverage, when $G_{\texttt{cov}}$ is arbitrary. Together, these results mark a clear line between what is possible with FPT approximation and what is not, and point to a clean classification by the structure of the coverage and constraint graphs.

Future directions.

$\blacksquare$

Faster algorithms. Improve the running time (and parameter dependence) of our EPAS/PAS.
$\blacksquare$

Broader tractable classes. Identify larger families of coverage instances where the problem remains FPT (beyond biclique-free), e.g. bounded VC-dimension, or geometric incidences.
$\blacksquare$

Other constraints. Study variants where the constraint layer enforces independence/packing, degree bounds, or fault tolerance (e.g., $r$ -connectivity) instead of (or in addition to) connectivity.
$\blacksquare$

Lossy kernels. It would be ideal to have lossy kernels as in the vanilla setting [34]; however, we can show Connected Partial Vertex Cover admits no lossy kernels.

References

[1] Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. J. ACM, 42(4):844–856, 1995. doi:10.1145/210332.210337.
[2] Mitali Bafna, Karthik C. S., and Dor Minzer. Near optimal constant inapproximability under ETH for fundamental problems in parameterized complexity. In Michal Koucký and Nikhil Bansal, editors, Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025, Prague, Czechia, June 23-27, 2025, pages 2118–2129. ACM, 2025. doi:10.1145/3717823.3718257.
[3] András A. Benczúr and David R. Karger. Approximating s-t minimum cuts in Õ(n²) time. In Gary L. Miller, editor, Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996, pages 47–55. ACM, 1996. doi:10.1145/237814.237827.
[4] Terry Beyer and Sandra Mitchell Hedetniemi. Constant time generation of rooted trees. SIAM J. Comput., 9(4):706–712, 1980. doi:10.1137/0209055.
[5] Leizhen Cai, Siu Man Chan, and Siu On Chan. Random separation: A new method for solving fixed-cardinality optimization problems. In Hans L. Bodlaender and Michael A. Langston, editors, Parameterized and Exact Computation, Second International Workshop, IWPEC 2006, Zürich, Switzerland, September 13-15, 2006, Proceedings, volume 4169 of Lecture Notes in Computer Science, pages 239–250. Springer, 2006. doi:10.1007/11847250_22.
[6] Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, and Luca Trevisan. From gap-exponential time hypothesis to fixed parameter tractable inapproximability: Clique, dominating set, and more. SIAM J. Comput., 49(4):772–810, 2020. doi:10.1137/18M1166869.
[7] Yijia Chen and Bingkai Lin. The constant inapproximability of the parameterized dominating set problem. SIAM J. Comput., 48(2):513–533, 2019. doi:10.1137/17M1127211.
[8] Vincent Cohen-Addad, Anupam Gupta, Amit Kumar, Euiwoong Lee, and Jason Li. Tight FPT Approximations for $k$ -Median and $k$ -Means. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, volume 132 of LIPIcs, pages 42:1–42:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPIcs.ICALP.2019.42.
[9] Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized algorithms, volume 5. Springer, 2015. doi:10.1007/978-3-319-21275-3.
[10] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. doi:10.1007/978-3-319-21275-3.
[11] Gianlorenzo D’Angelo and Esmaeil Delfaraz. Approximation algorithms for connected maximum coverage. In Sanmay Das, Ann Nowé, and Yevgeniy Vorobeychik, editors, Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2025, Detroit, MI, USA, May 19-23, 2025, pages 538–546. International Foundation for Autonomous Agents and Multiagent Systems / ACM, 2025. doi:10.5555/3709347.3743569.
[12] Reinhard Diestel. Graph theory, volume 173. Springer Nature, 2025.
[13] Irit Dinur and David Steurer. Analytical approach to parallel repetition. In David B. Shmoys, editor, Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 624–633. ACM, 2014. doi:10.1145/2591796.2591884.
[14] Rodney G. Downey and Michael R. Fellows. Fixed-parameter tractability and completeness I: basic results. SIAM J. Comput., 24(4):873–921, 1995. doi:10.1137/S0097539792228228.
[15] Uriel Feige and Mohammad Mahdian. Finding small balanced separators. In Jon M. Kleinberg, editor, Proceedings of the 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, May 21-23, 2006, pages 375–384. ACM, 2006. doi:10.1145/1132516.1132573.
[16] Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh. Efficient computation of representative families with applications in parameterized and exact algorithms. J. ACM, 63(4):29:1–29:60, 2016. doi:10.1145/2886094.
[17] Rajiv Gandhi, Samir Khuller, and Aravind Srinivasan. Approximation algorithms for partial covering problems. J. Algorithms, 53(1):55–84, 2004. doi:10.1016/J.JALGOR.2004.04.002.
[18] Anupam Gupta, Euiwoong Lee, Jason Li, Pasin Manurangsi, and Michal Wlodarczyk. Losing treewidth by separating subsets. In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 1731–1749. SIAM, 2019. doi:10.1137/1.9781611975482.104.
[19] Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, and Kewen Wu. Parameterized inapproximability hypothesis under exponential time hypothesis. In Bojan Mohar, Igor Shinkar, and Ryan O’Donnell, editors, Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024, pages 24–35. ACM, 2024. doi:10.1145/3618260.3649771.
[20] Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, and Kewen Wu. Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH. In Michal Koucký and Nikhil Bansal, editors, Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025, Prague, Czechia, June 23-27, 2025, pages 2136–2144. ACM, 2025. doi:10.1145/3717823.3718130.
[21] Dorit S Hochbaum and Anu Pathria. Analysis of the greedy approach in problems of maximum $k$ -coverage. Naval Research Logistics (NRL), 45(6):615–627, 1998.
[22] Dorit S. Hochbaum and Xu Rao. Approximation algorithms for connected maximum coverage problem for the discovery of mutated driver pathways in cancer. Inf. Process. Lett., 158:105940, 2020. doi:10.1016/J.IPL.2020.105940.
[23] Tanmay Inamdar, Pallavi Jain, Daniel Lokshtanov, Abhishek Sahu, Saket Saurabh, and Anannya Upasana. Satisfiability to coverage in presence of fairness, matroid, and global constraints. In Karl Bringmann, Martin Grohe, Gabriele Puppis, and Ola Svensson, editors, 51st International Colloquium on Automata, Languages, and Programming, ICALP 2024, July 8-12, 2024, Tallinn, Estonia, volume 297 of LIPIcs, pages 88:1–88:18. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPIcs.ICALP.2024.88.
[24] Pallavi Jain, Lawqueen Kanesh, Fahad Panolan, Souvik Saha, Abhishek Sahu, Saket Saurabh, and Anannya Upasana. Parameterized Approximation Schemes for Biclique-Free Max $k$ -Weight SAT and Max Coverage. ACM Trans. Algorithms, August 2025. Just Accepted. doi:10.1145/3763238.
[25] Karthik C. S., Bundit Laekhanukit, and Pasin Manurangsi. On the parameterized complexity of approximating dominating set. J. ACM, 66(5):33:1–33:38, 2019. doi:10.1145/3325116.
[26] Samir Khuller, Manish Purohit, and Kanthi K. Sarpatwar. Analyzing the optimal neighborhood: Algorithms for partial and budgeted connected dominating set problems. SIAM J. Discret. Math., 34(1):251–270, 2020. doi:10.1137/18M1212094.
[27] Ioannis Lamprou, Ioannis Sigalas, and Vassilis Zissimopoulos. Improved budgeted connected domination and budgeted edge-vertex domination. Theor. Comput. Sci., 858:1–12, 2021. doi:10.1016/J.TCS.2021.01.030.
[28] Bingkai Lin. The parameterized complexity of the $k$ -biclique problem. J. ACM, 65(5):34:1–34:23, 2018. doi:10.1145/3212622.
[29] Bingkai Lin. A simple gap-producing reduction for the parameterized set cover problem. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, volume 132 of LIPIcs, pages 81:1–81:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPIcs.ICALP.2019.81.
[30] Daniel Lokshtanov, Abhishek Sahu, Saket Saurabh, Vaishali Surianarayanan, and Jie Xue. Parameterized approximation for capacitated d-hitting set with hard capacities. In Yossi Azar and Debmalya Panigrahi, editors, Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, New Orleans, LA, USA, January 12-15, 2025, pages 1565–1592. SIAM, 2025. doi:10.1137/1.9781611978322.48.
[31] Daniel Lokshtanov, Saket Saurabh, and Vaishali Surianarayanan. A parameterized approximation scheme for min $k$ -cut. SIAM J. Comput., 53(6):S20–205, 2024. doi:10.1137/20M1383197.
[32] Pasin Manurangsi. A Note on Max $k$ -Vertex Cover: Faster FPT-AS, Smaller Approximate Kernel and Improved Approximation. In Jeremy T. Fineman and Michael Mitzenmacher, editors, 2nd Symposium on Simplicity in Algorithms, SOSA 2019, January 8-9, 2019, San Diego, CA, USA, volume 69 of OASIcs, pages 15:1–15:21. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. doi:10.4230/OASIcs.SOSA.2019.15.
[33] Pasin Manurangsi. Tight running time lower bounds for strong inapproximability of maximum k-coverage, unique set cover and related problems (via t-wise agreement testing theorem). In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 62–81. SIAM, 2020. doi:10.1137/1.9781611975994.5.
[34] Pasin Manurangsi. Improved FPT approximation scheme and approximate kernel for biclique-free max $k$ -weight SAT: greedy strikes back. Theor. Comput. Sci., 1028:115033, 2025. doi:10.1016/J.TCS.2024.115033.
[35] Dániel Marx. Parameterized complexity and approximation algorithms. Comput. J., 51(1):60–78, 2008. doi:10.1093/comjnl/bxm048.
[36] Neeldhara Misra, Geevarghese Philip, Venkatesh Raman, Saket Saurabh, and Somnath Sikdar. FPT algorithms for connected feedback vertex set. J. Comb. Optim., 24(2):131–146, 2012. doi:10.1007/S10878-011-9394-2.
[37] Richard Otter. The number of trees. Annals of Mathematics, 49(3):583–599, 1948.
[38] Jürgen Plehn and Bernd Voigt. Finding minimally weighted subgraphs. In Rolf H. Möhring, editor, Graph-Theoretic Concepts in Computer Science, 16rd International Workshop, WG ’90, Berlin, Germany, June 20-22, 1990, Proceedings, volume 484 of Lecture Notes in Computer Science, pages 18–29. Springer, 1990. doi:10.1007/3-540-53832-1_28.
[39] François Sellier. Parameterized matroid-constrained maximum coverage. In Inge Li Gørtz, Martin Farach-Colton, Simon J. Puglisi, and Grzegorz Herman, editors, 31st Annual European Symposium on Algorithms, ESA 2023, September 4-6, 2023, Amsterdam, The Netherlands, volume 274 of LIPIcs, pages 94:1–94:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. doi:10.4230/LIPIcs.ESA.2023.94.
[40] Piotr Skowron and Piotr Faliszewski. Chamberlin-courant rule with approval ballots: Approximating the maxcover problem with bounded frequencies in FPT time. J. Artif. Intell. Res., 60:687–716, 2017. doi:10.1613/JAIR.5628.
[41] Daniel A. Spielman and Shang-Hua Teng. Spectral sparsification of graphs. SIAM J. Comput., 40(4):981–1025, 2011. doi:10.1137/08074489X.
[42] Michal Wlodarczyk. Parameterized inapproximability for steiner orientation by gap amplification. In Artur Czumaj, Anuj Dawar, and Emanuela Merelli, editors, 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference), volume 168 of LIPIcs, pages 104:1–104:19. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020. doi:10.4230/LIPIcs.ICALP.2020.104.

[bib.bib1] [1] Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. J. ACM, 42(4):844–856, 1995. doi:10.1145/210332.210337.

[bib.bib2] [2] Mitali Bafna, Karthik C. S., and Dor Minzer. Near optimal constant inapproximability under ETH for fundamental problems in parameterized complexity. In Michal Koucký and Nikhil Bansal, editors, Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025, Prague, Czechia, June 23-27, 2025, pages 2118–2129. ACM, 2025. doi:10.1145/3717823.3718257.

[bib.bib3] [3] András A. Benczúr and David R. Karger. Approximating s-t minimum cuts in Õ(n²) time. In Gary L. Miller, editor, Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996, pages 47–55. ACM, 1996. doi:10.1145/237814.237827.

[bib.bib4] [4] Terry Beyer and Sandra Mitchell Hedetniemi. Constant time generation of rooted trees. SIAM J. Comput., 9(4):706–712, 1980. doi:10.1137/0209055.

[bib.bib5] [5] Leizhen Cai, Siu Man Chan, and Siu On Chan. Random separation: A new method for solving fixed-cardinality optimization problems. In Hans L. Bodlaender and Michael A. Langston, editors, Parameterized and Exact Computation, Second International Workshop, IWPEC 2006, Zürich, Switzerland, September 13-15, 2006, Proceedings, volume 4169 of Lecture Notes in Computer Science, pages 239–250. Springer, 2006. doi:10.1007/11847250_22.

[bib.bib6] [6] Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, and Luca Trevisan. From gap-exponential time hypothesis to fixed parameter tractable inapproximability: Clique, dominating set, and more. SIAM J. Comput., 49(4):772–810, 2020. doi:10.1137/18M1166869.

[bib.bib7] [7] Yijia Chen and Bingkai Lin. The constant inapproximability of the parameterized dominating set problem. SIAM J. Comput., 48(2):513–533, 2019. doi:10.1137/17M1127211.

[bib.bib8] [8] Vincent Cohen-Addad, Anupam Gupta, Amit Kumar, Euiwoong Lee, and Jason Li. Tight FPT Approximations for $k$ -Median and $k$ -Means. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, volume 132 of LIPIcs, pages 42:1–42:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPIcs.ICALP.2019.42.

[bib.bib9] [9] Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized algorithms, volume 5. Springer, 2015. doi:10.1007/978-3-319-21275-3.

[bib.bib10] [10] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. doi:10.1007/978-3-319-21275-3.

[bib.bib11] [11] Gianlorenzo D’Angelo and Esmaeil Delfaraz. Approximation algorithms for connected maximum coverage. In Sanmay Das, Ann Nowé, and Yevgeniy Vorobeychik, editors, Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2025, Detroit, MI, USA, May 19-23, 2025, pages 538–546. International Foundation for Autonomous Agents and Multiagent Systems / ACM, 2025. doi:10.5555/3709347.3743569.

[bib.bib12] [12] Reinhard Diestel. Graph theory, volume 173. Springer Nature, 2025.

[bib.bib13] [13] Irit Dinur and David Steurer. Analytical approach to parallel repetition. In David B. Shmoys, editor, Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 624–633. ACM, 2014. doi:10.1145/2591796.2591884.

[bib.bib14] [14] Rodney G. Downey and Michael R. Fellows. Fixed-parameter tractability and completeness I: basic results. SIAM J. Comput., 24(4):873–921, 1995. doi:10.1137/S0097539792228228.

[bib.bib15] [15] Uriel Feige and Mohammad Mahdian. Finding small balanced separators. In Jon M. Kleinberg, editor, Proceedings of the 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, May 21-23, 2006, pages 375–384. ACM, 2006. doi:10.1145/1132516.1132573.

[bib.bib16] [16] Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh. Efficient computation of representative families with applications in parameterized and exact algorithms. J. ACM, 63(4):29:1–29:60, 2016. doi:10.1145/2886094.

[bib.bib17] [17] Rajiv Gandhi, Samir Khuller, and Aravind Srinivasan. Approximation algorithms for partial covering problems. J. Algorithms, 53(1):55–84, 2004. doi:10.1016/J.JALGOR.2004.04.002.

[bib.bib18] [18] Anupam Gupta, Euiwoong Lee, Jason Li, Pasin Manurangsi, and Michal Wlodarczyk. Losing treewidth by separating subsets. In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 1731–1749. SIAM, 2019. doi:10.1137/1.9781611975482.104.

[bib.bib19] [19] Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, and Kewen Wu. Parameterized inapproximability hypothesis under exponential time hypothesis. In Bojan Mohar, Igor Shinkar, and Ryan O’Donnell, editors, Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024, pages 24–35. ACM, 2024. doi:10.1145/3618260.3649771.

[bib.bib20] [20] Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, and Kewen Wu. Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH. In Michal Koucký and Nikhil Bansal, editors, Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025, Prague, Czechia, June 23-27, 2025, pages 2136–2144. ACM, 2025. doi:10.1145/3717823.3718130.

[bib.bib21] [21] Dorit S Hochbaum and Anu Pathria. Analysis of the greedy approach in problems of maximum $k$ -coverage. Naval Research Logistics (NRL), 45(6):615–627, 1998.

[bib.bib22] [22] Dorit S. Hochbaum and Xu Rao. Approximation algorithms for connected maximum coverage problem for the discovery of mutated driver pathways in cancer. Inf. Process. Lett., 158:105940, 2020. doi:10.1016/J.IPL.2020.105940.

[bib.bib23] [23] Tanmay Inamdar, Pallavi Jain, Daniel Lokshtanov, Abhishek Sahu, Saket Saurabh, and Anannya Upasana. Satisfiability to coverage in presence of fairness, matroid, and global constraints. In Karl Bringmann, Martin Grohe, Gabriele Puppis, and Ola Svensson, editors, 51st International Colloquium on Automata, Languages, and Programming, ICALP 2024, July 8-12, 2024, Tallinn, Estonia, volume 297 of LIPIcs, pages 88:1–88:18. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPIcs.ICALP.2024.88.

[bib.bib24] [24] Pallavi Jain, Lawqueen Kanesh, Fahad Panolan, Souvik Saha, Abhishek Sahu, Saket Saurabh, and Anannya Upasana. Parameterized Approximation Schemes for Biclique-Free Max $k$ -Weight SAT and Max Coverage. ACM Trans. Algorithms, August 2025. Just Accepted. doi:10.1145/3763238.

[bib.bib25] [25] Karthik C. S., Bundit Laekhanukit, and Pasin Manurangsi. On the parameterized complexity of approximating dominating set. J. ACM, 66(5):33:1–33:38, 2019. doi:10.1145/3325116.

[bib.bib26] [26] Samir Khuller, Manish Purohit, and Kanthi K. Sarpatwar. Analyzing the optimal neighborhood: Algorithms for partial and budgeted connected dominating set problems. SIAM J. Discret. Math., 34(1):251–270, 2020. doi:10.1137/18M1212094.

[bib.bib27] [27] Ioannis Lamprou, Ioannis Sigalas, and Vassilis Zissimopoulos. Improved budgeted connected domination and budgeted edge-vertex domination. Theor. Comput. Sci., 858:1–12, 2021. doi:10.1016/J.TCS.2021.01.030.

[bib.bib28] [28] Bingkai Lin. The parameterized complexity of the $k$ -biclique problem. J. ACM, 65(5):34:1–34:23, 2018. doi:10.1145/3212622.

[bib.bib29] [29] Bingkai Lin. A simple gap-producing reduction for the parameterized set cover problem. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, volume 132 of LIPIcs, pages 81:1–81:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPIcs.ICALP.2019.81.

[bib.bib30] [30] Daniel Lokshtanov, Abhishek Sahu, Saket Saurabh, Vaishali Surianarayanan, and Jie Xue. Parameterized approximation for capacitated d-hitting set with hard capacities. In Yossi Azar and Debmalya Panigrahi, editors, Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, New Orleans, LA, USA, January 12-15, 2025, pages 1565–1592. SIAM, 2025. doi:10.1137/1.9781611978322.48.

[bib.bib31] [31] Daniel Lokshtanov, Saket Saurabh, and Vaishali Surianarayanan. A parameterized approximation scheme for min $k$ -cut. SIAM J. Comput., 53(6):S20–205, 2024. doi:10.1137/20M1383197.

[bib.bib32] [32] Pasin Manurangsi. A Note on Max $k$ -Vertex Cover: Faster FPT-AS, Smaller Approximate Kernel and Improved Approximation. In Jeremy T. Fineman and Michael Mitzenmacher, editors, 2nd Symposium on Simplicity in Algorithms, SOSA 2019, January 8-9, 2019, San Diego, CA, USA, volume 69 of OASIcs, pages 15:1–15:21. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. doi:10.4230/OASIcs.SOSA.2019.15.

[bib.bib33] [33] Pasin Manurangsi. Tight running time lower bounds for strong inapproximability of maximum k-coverage, unique set cover and related problems (via t-wise agreement testing theorem). In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 62–81. SIAM, 2020. doi:10.1137/1.9781611975994.5.

[bib.bib34] [34] Pasin Manurangsi. Improved FPT approximation scheme and approximate kernel for biclique-free max $k$ -weight SAT: greedy strikes back. Theor. Comput. Sci., 1028:115033, 2025. doi:10.1016/J.TCS.2024.115033.

[bib.bib35] [35] Dániel Marx. Parameterized complexity and approximation algorithms. Comput. J., 51(1):60–78, 2008. doi:10.1093/comjnl/bxm048.

[bib.bib36] [36] Neeldhara Misra, Geevarghese Philip, Venkatesh Raman, Saket Saurabh, and Somnath Sikdar. FPT algorithms for connected feedback vertex set. J. Comb. Optim., 24(2):131–146, 2012. doi:10.1007/S10878-011-9394-2.

[bib.bib37] [37] Richard Otter. The number of trees. Annals of Mathematics, 49(3):583–599, 1948.

[bib.bib38] [38] Jürgen Plehn and Bernd Voigt. Finding minimally weighted subgraphs. In Rolf H. Möhring, editor, Graph-Theoretic Concepts in Computer Science, 16rd International Workshop, WG ’90, Berlin, Germany, June 20-22, 1990, Proceedings, volume 484 of Lecture Notes in Computer Science, pages 18–29. Springer, 1990. doi:10.1007/3-540-53832-1_28.

[bib.bib39] [39] François Sellier. Parameterized matroid-constrained maximum coverage. In Inge Li Gørtz, Martin Farach-Colton, Simon J. Puglisi, and Grzegorz Herman, editors, 31st Annual European Symposium on Algorithms, ESA 2023, September 4-6, 2023, Amsterdam, The Netherlands, volume 274 of LIPIcs, pages 94:1–94:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. doi:10.4230/LIPIcs.ESA.2023.94.

[bib.bib40] [40] Piotr Skowron and Piotr Faliszewski. Chamberlin-courant rule with approval ballots: Approximating the maxcover problem with bounded frequencies in FPT time. J. Artif. Intell. Res., 60:687–716, 2017. doi:10.1613/JAIR.5628.

[bib.bib41] [41] Daniel A. Spielman and Shang-Hua Teng. Spectral sparsification of graphs. SIAM J. Comput., 40(4):981–1025, 2011. doi:10.1137/08074489X.

[bib.bib42] [42] Michal Wlodarczyk. Parameterized inapproximability for steiner orientation by gap amplification. In Artur Czumaj, Anuj Dawar, and Emanuela Merelli, editors, 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference), volume 168 of LIPIcs, pages 104:1–104:19. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020. doi:10.4230/LIPIcs.ICALP.2020.104.

FPT Approximations for Connected Maximum Coverage

Abstract

Limits to parameterized tractability.

Inapproximability.

Graphical special cases.

Keywords and phrases:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

DOI:

Event:

Editor:

Series and Publisher:

1 Introduction

Connectivity Constraints.

1.1 Our Model of Connectivity-Constrained Coverage

Modeling prior problems.

1.2 Our Algorithmic Results

Theorem 1.

Theorem 2 (♠).

Neighborhood Sparsifiers: A Conceptual Contribution.

Lemma 3 (Neighborhood Sparsifiers for Kd,d-free coverage).

1.3 Potential for a Dichotomy Program

2 Technical Overview of Our Main Results

Overview of the proof of Theorem 1.

Overview of the proof of Theorem 2.

3 Preliminaries

4 FPT for PARTIALCONRBDS parameterized by 𝒕

Randomized reduction from PARTIALCONRBDS to RDSOT.

Theorem 4 (♠).

5 (𝟏,𝟏−𝜺)-approximation for PARTIALCONRBDS

5.1 Step 1: Construction of the Conflict Graph

Definition 5 (conflict graph).

Lemma 6 (Restatement of Lemma 4.1 from [24]).

Proof.

5.2 Step 2: Isolating Connected Components of 𝑺⋆ in 𝑮conf

Derandomization.

Proposition 7 ([1, 10]).

Filtering of Connected Components.

Motivation for the filtering step.

Observation 8.

5.3 Step 3: Construction of Sparsified Graph

Property 9.

Property 10.

Proof for Property 9.

Proof for Property 10.

5.4 Step 4: Introducing vertex weights to 𝑽⁢(𝑮conf𝐩𝐮𝐫𝐩𝐥𝐞)

Lemma 11.

Proof.

Definition 12 (Component-respecting set).

Lemma 13.

Proof.

5.5 Step 5: Finding a Maximum Weighted Subtree in 𝑮conn⁢[𝑽⁢(𝑮conf𝐩𝐮𝐫𝐩𝐥𝐞)]

Proposition 14.

Proposition 15 ([37, 4]).

Lemma 16.

Proof.

5.6 Putting all the Pieces Together

Theorem 17.

Proof.

Running time.

6 Conclusion

Future directions.

References

Theorem 2 ( $\spadesuit$ ).

Lemma 3 (Neighborhood Sparsifiers for $K_{d,d}$ -free coverage).

4 FPT for PARTIALCONRBDS parameterized by $𝒕$

Theorem 4 ( $\spadesuit$ ).

5 $(1,1-\varepsilon)$ -approximation for PARTIALCONRBDS

5.2 Step 2: Isolating Connected Components of $S^{\star}$ in $G_{\texttt{conf}}$

5.4 Step 4: Introducing vertex weights to $V\bigl(G_{\texttt{conf}}^{\mathrm{purple}}\bigr)$

5.5 Step 5: Finding a Maximum Weighted Subtree in $G_{\texttt{conn}}\left[V(G_{\texttt{conf}}^{\mathrm{purple}})\right]$