The existence of a polynomial kernel for Odd Cycle Transversal was notorious open problem in parameterized complexity. Recently, this settled by the present authors (Kratsch and Wahlstrom, SODA 2012), with randomized problem, using matroid theory to encode How questions over set terminals size number (rather than total graph size, which may be superpolynomially larger). In current work we further establish usefulness kernelization showing applications result on representative sets due Lovasz...

The field of exact exponential time algorithms for non-deterministic polynomial-time hard problems has thrived since the mid-2000s. While exhaustive search remains asymptotically fastest known algorithm some basic problems, non-trivial have been found a myriad including G raph C oloring , H amiltonian P ath D ominating S et and 3-CNF-S at . In instances, improving these further seems to be out reach. CNF-S problem is canonical example which trivial runs in O (2 n ), where number variables...

The Odd Cycle Transversal problem (OCT) asks whether a given undirected graph can be made bipartite by deleting at most k of its vertices. In breakthrough result, Reed, Smith, and Vetta (Operations Research Letters, 2004) gave O (4 kmn) time algorithm for it; this also implies that instances the reduced to so-called kernel size ). Since then, existence polynomial OCT (i.e., kernelization with bounded polynomially in ) has turned into one main open questions study kernelization, even special...

The field of exact exponential time algorithms for NP-hard problems has thrived over the last decade. While exhaustive search remains asymptotically fastest known algorithm some basic problems, difficult and non-trivial have been found a myriad including GRAPH COLORING, HAMILTONIAN PATH, DOMINATING SET 3-CNF-SAT. In instances, improving these further seems to be out reach. CNF-SAT problem is canonical example which trivial runs in O(2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML"...

The field of kernelization studies polynomial-time preprocessing routines for hard problems in the framework parameterized complexity. In this article, we show that, unless polynomial hierarchy collapses to its third level, following do not admit a algorithm that reduces size an instance parameter: ---Edge Clique Cover, by number cliques, ---Directed Edge/Vertex Multiway Cut, cutset, even case two terminals, ---Edge/Vertex Multicut, and --- k -Way cutset.

A recent trend in parameterized algorithms is the application of polytope tools to fixed-parameter tractable (FPT) [e.g., Cygan et al., FOCS 2011, 52nd Annual Symposium on Foundations Computer Science, IEEE, pp. 150--159; Narayanaswamy STACS 2012, Theoretical Aspects 338--349]. Although this approach has yielded significant speedups for a range important problems, it requires underlying have very restrictive properties, including half-integrality and Nemhauser--Trotter-style persistence...

The Odd Cycle Transversal problem (OCT) asks whether a given graph can be made bipartite by deleting at most k of its vertices. In breakthrough result Reed, Smith, and Vetta (Operations Research Letters, 2004) gave O(4kkmn) time algorithm for it, the first with polynomial runtime uniform degree every fixed k. It is known that this implies polynomial-time compression turns OCT instances into equivalent size O(4k), so-called kernelization. Since then existence kernel OCT, i.e., kernelization...

The Multicut problem, given a graph G, set of terminal pairs $\mathcal{T}=\{(s_i,t_i)\ |\ 1\leq i\leq r\}$, and an integer $p$, asks whether one can find cutset consisting at most $p$ nonterminal vertices that separates all the pairs, i.e., after removing cutset, $t_i$ is not reachable from $s_i$ for each $1\leq r$. fixed-parameter tractability in undirected graphs, parameterized by size only, has been recently proved Marx Razgon [SIAM J. Comput., 43 (2014), pp. 355--388] and, independently,...

We continue the development of matroid-based techniques for kernelization, initiated by present authors [47]. significantly extend usefulness matroid theory in kernelization showing applications a result on representative sets due to Lovász [51] and Marx [53]. As first result, we show how can be used derive polynomial kernel elusive ALMOST 2- SAT problem (where task is remove at most k clauses make CNF formula satisfiable), solving major open kernelization. This also yields new O(√log...

Given a graph $G$ and an integer $k$, the $H$-free Edge Deletion problem asks whether there exists set of at most $k$ edges whose deletion makes free induced copies $H$. Significant attention has been given to kernelizability aspects this -- i.e., for which graphs $H$ does admit "efficient preprocessing" procedure, known as polynomial kernelization, where instance $I$ with parameter is reduced equivalent $I'$ size value are bounded polynomially in $k$? Although such routines many class...

Matroids, particularly linear ones, have been a powerful tool in parameterized complexity for algorithms and kernelization. They sped up or replaced dynamic programming. Delta-matroids generalize matroids by encapsulating structures such as non-maximum matchings general graphs various path-packing topological configurations. Linear delta-matroids (represented skew-symmetric matrices) offer significant expressive power enable algorithms. We investigate aspects of problems defined over with...

Checking whether a system of linear equations is consistent basic computational problem with ubiquitous applications. When dealing inconsistent systems, one may seek an assignment that minimises the number unsatisfied equations. This NP -hard and UGC-hard to approximate within any constant even for two-variable over two-element field. We study this from point view parameterized complexity, parameter being consider defined family commutative domains (i.e. rings without zero divisors)...

We present a new algorithm for estimating the star discrepancy of arbitrary point sets. Similar to approximation Winker and Fang [SIAM J. Numer. Anal. 34 (1997), 2028--2042] it is based on optimization threshold accepting. Our improvements include, amongst others, non-uniform sampling strategy which more suited higher-dimensional inputs, rounding steps transform axis-parallel boxes, be tested, into \emph{critical test boxes}. These critical boxes provably yield higher values, contain box...

A recent trend in parameterized algorithms is the application of polytope tools (specifically, LP-branching) to FPT (e.g., Cygan et al., 2011; Narayanaswamy 2012). Though list work this direction short, results are already interesting, yielding significant speedups for a range important problems. However, existing approaches require underlying have very restrictive properties, including half-integrality and Nemhauser-Trotter-style persistence properties. To date, these properties essentially...

We show an algorithm that, given n -vertex graph G and a parameter k , in time 2 O ( log ) (1) finds tree decomposition of with the following properties: — every adhesion is size at most bag i )-unbreakable for 1 ⩽ . Here, set X ⊆ V b if separation A B order we have | \cap or ∩ The resulting has arguably best possible bounds unbreakability guarantees. Furthermore, parametric factor running bound significantly smaller than previous similar constructions. These improvements allow us to present...

In the Odd Cycle Transversal (OCT) problem we are given a graph G on n vertices and an integer k, objective is to determine whether there exists vertex set O in of size at most k such that - bipartite. Reed, Smith Vetta [Oper. Res. Lett., 2004] gave algorithm for OCT with running time 3^kn^{O(1)}. Assuming exponential hypothesis Impagliazzo, Paturi Zane, can not be improved 2^{o(k)}n^{O(1)}. We show admits randomized O(n^{O(1)} + 2^{O(sqrt{k} log k)}n) when input planar. As byproduct also...