ﻻ يوجد ملخص باللغة العربية
We present two new combinatorial tools for the design of parameterized algorithms. The first is a simple linear time randomized algorithm that given as input a $d$-degenerate graph $G$ and an integer $k$, outputs an independent set $Y$, such that for every independent set $X$ in $G$ of size at most $k$, the probability that $X$ is a subset of $Y$ is at least $left({(d+1)k choose k} cdot k(d+1)right)^{-1}$.The second is a new (deterministic) polynomial time graph sparsification procedure that given a graph $G$, a set $T = {{s_1, t_1}, {s_2, t_2}, ldots, {s_ell, t_ell}}$ of terminal pairs and an integer $k$, returns an induced subgraph $G^star$ of $G$ that maintains all the inclusion minimal multicuts of $G$ of size at most $k$, and does not contain any $(k+2)$-vertex connected set of size $2^{{cal O}(k)}$. In particular, $G^star$ excludes a clique of size $2^{{cal O}(k)}$ as a topological minor. Put together, our new tools yield new randomized fixed parameter tractable (FPT) algorithms for Stable $s$-$t$ Separator, Stable Odd Cycle Transversal and Stable Multicut on general graphs, and for Stable Directed Feedback Vertex Set on $d$-degenerate graphs, resolving two problems left open by Marx et al. [ACM Transactions on Algorithms, 2013]. All of our algorithms can be derandomized at the cost of a small overhead in the running time.
We show algorithms for computing representative families for matroid intersections and use them in fixed-parameter algorithms for set packing, set covering, and facility location problems with multiple matroid constraints. We complement our tractability results by hardness results.
We study two variants of textsc{Maximum Cut}, which we call textsc{Connected Maximum Cut} and textsc{Maximum Minimal Cut}, in this paper. In these problems, given an unweighted graph, the goal is to compute a maximum cut satisfying some connectivity
An enumeration kernel as defined by Creignou et al. [Theory Comput. Syst. 2017] for a parameterized enumeration problem consists of an algorithm that transforms each instance into one whose size is bounded by the parameter plus a solution-lifting alg
Covering problems are fundamental classical problems in optimization, computer science and complexity theory. Typically an input to these problems is a family of sets over a finite universe and the goal is to cover the elements of the universe with a
In the 1970s, Lovasz built a bridge between graphs and alternating matrix spaces, in the context of perfect matchings (FCT 1979). A similar connection between bipartite graphs and matrix spaces plays a key role in the recent resolutions of the non-co