Approximating minimum-cost edge-covers of crossing biset-families (Q397064)

Let \(V\) be a set. Then, a pair \((S,S^{+})\) of subsets of \(V\) with \(S\subseteq S^{+}\) is a biset on \(V\). A family \(\mathcal F\) of bisets on a set \(V\) is crossing if \((X\cap Y,X^{+}\cap Y^{+}),(X\cup Y,X^{+}\cup Y^{+})\in\mathcal F\) for all \((X,X^{+}),(Y,Y^{+})\in \mathcal F\) with \(X\cap Y\neq\emptyset\) and \(X^{+}\cup Y^{+}\neq V\), \(\mathcal F\) is \(k\)-regular if \((X\cap Y,X^{+}\cap Y^{+}),(X\cup Y,X^{+}\cup Y^{+})\in \mathcal F\) for all \((X,X^{+}),(Y,Y^{+})\in\mathcal F\) with \(X\cap Y\neq\emptyset\) and \(| V\setminus (X\cup Y)| \geq k+1\). For a family \( \mathcal F\) of bisets on \(V\) the family \(\{(V\setminus S^{+},V\setminus S)\mid (S,S^{+})\in \mathcal F \}\) is a co-family of \(\mathcal F\). A directed edge \((x,y)\) covers a biset \((S,S^{+})\) if \(x\in S\) and \(y\in V\setminus S^{+}\). A biset-family edge-cover problem is: for a given directed graph \((V,E)\), a cost function \(c:E\to \mathbb R\) and a family \(\mathcal F\) of bisets on \(V\) find a minimum cost set \(J\subseteq E\) such that every biset in \(\mathcal F\) is covered by an edge from \(J\). The paper presents an \(O(\log| V|)\)-approximation polynomial time algorithm solving the biset-family edge-cover problem for crossing families of bisets. Moreover, if both \(\mathcal F\) and the co-family of \(\mathcal F\) are \(k\)-regular and \(| S^{+}\setminus S| =k\) for every \((S,S^{+})\in \mathcal F\) then the ratio of the algorithm is \(O(\log\frac {| V| }{| V| -k})\). Some consequences for other network problems -- e.g. for the \(k\)-connected subgraph problem, the subset \(k\)-connected subgraph problem etc. -- are derived and discussed. Finally, some open problem are formulated and discussed.