English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The existence of a polynomial kernel for Odd Cycle Transversal was anotorious open problem in parameterized complexity. Recently, this was settledby the present authors (Kratsch and Wahlstr\"om, SODA 2012), with a randomizedpolynomial kernel for the problem, using matroid theory to encode flowquestions over a set of terminals in size polynomial in the number ofterminals.  In the current work we further establish the usefulness of matroid theory tokernelization by showing applications of a result on representative sets due toLov\'asz (Combinatorial Surveys 1977) and Marx (TCS 2009). We show howrepresentative sets can be used to give a polynomial kernel for the elusiveAlmost 2-SAT problem. We further apply the representative sets tool to theproblem of finding irrelevant vertices in graph cut problems, i.e., verticeswhich can be made undeletable without affecting the status of the problem. Thisgives the first significant progress towards a polynomial kernel for theMultiway Cut problem; in particular, we get a kernel of O(k^{s+1}) vertices forMultiway Cut instances with at most s terminals. Both these kernelizationresults have significant spin-off effects, producing the first polynomialkernels for a range of related problems.  More generally, the irrelevant vertex results have implications for coveringmin-cuts in graphs. For a directed graph G=(V,E) and sets S, T \subseteq V, letr be the size of a minimum (S,T)-vertex cut (which may intersect S and T). Wecan find a set Z \subseteq V of size O(|S|*|T|*r) which contains a minimum(A,B)-vertex cut for every A \subseteq S, B \subseteq T. Similarly, for anundirected graph G=(V,E), a set of terminals X \subseteq V, and a constant s,we can find a set Z\subseteq V of size O(|X|^{s+1}) which contains a minimummultiway cut for any partition of X into at most s pairwise disjoint subsets.

Representative sets and irrelevant vertices: New tools for kernelization