Stefan Kratsch

SODA Conference 2023 Conference Paper

Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints

• Eun Jung Kim 0002
• Stefan Kratsch
• Marcin Pilipczuk
• Magnus Wahlström

We study the parameterized problem of satisfying “almost all” constraints of a given formula F over a fixed, finite Boolean constraint language Γ, with or without weights. More precisely, for each finite Boolean constraint language Γ, we consider the following two problems. In MIN SAT(T), the input is a formula F over Γ and an integer k, and the task is to find an assignment α: V ( F ) → {0, 1} that satisfies all but at most k constraints of F, or determine that no such assignment exists. In WEIGHTED MIN SAT(Γ), the input additionally contains a weight function ω: F → ℤ + and an integer W, and the task is to find an assignment α such that (1) α satisfies all but at most k constraints of F, and (2) the total weight of the violated constraints is at most W. We give a complete dichotomy for the fixed-parameter tractability of these problems: We show that for every Boolean constraint language Γ, either WEIGHTED MIN SAT(Γ) is FPT; or WEIGHTED MIN SAT(Γ) is W[1]-hard but MIN SAT(Γ) is FPT; or MIN SAT (Γ) is W[1]-hard. This generalizes recent work of Kim et al. (SODA 2021) which did not consider weighted problems, and only considered languages Γ that cannot express implications ( u → v ) (as is used to, e. g. , model digraph cut problems). Our result generalizes and subsumes multiple previous results, including the FPT algorithms for WEIGHTED Almost 2-SAT, weighted and unweighted ℓ-CHAIN SAT, and COUPLED MIN-CUT, as well as weighted and directed versions of the latter. The main tool used in our algorithms is the recently developed method of directed flow-augmentation (Kim et al. , STOC 2022). * This research is a part of a project that have received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme Grant Agreement 714704 (M. Pilipczuk). Eun Jung Kim is supported by the grant from French National Research Agency under JCJC program (ASSK: ANR-18-CE40-0025-01). The full version of the paper can be accessed at https: //arxiv. org/abs/2207. 07422.

MFCS Conference 2023 Conference Paper

Tight Algorithmic Applications of Clique-Width Generalizations

• Vera Chekan
• Stefan Kratsch

In this work, we study two natural generalizations of clique-width introduced by Martin Fürer. Multi-clique-width (mcw) allows every vertex to hold multiple labels [ITCS 2017], while for fusion-width (fw) we have a possibility to merge all vertices of a certain label [LATIN 2014]. Fürer has shown that both parameters are upper-bounded by treewidth thus making them more appealing from an algorithmic perspective than clique-width and asked for applications of these parameters for problem solving. First, we determine the relation between these two parameters by showing that mcw ≤ fw + 1. Then we show that when parameterized by multi-clique-width, many problems (e. g. , Connected Dominating Set) admit algorithms with the same running time as for clique-width despite the exponential gap between these two parameters. For some problems (e. g. , Hamiltonian Cycle) we show an analogous result for fusion-width: For this we present an alternative view on fusion-width by introducing so-called glue-expressions which might be interesting on their own. All algorithms obtained in this work are tight up to (Strong) Exponential Time Hypothesis.

STOC Conference 2022 Conference Paper

Directed flow-augmentation

• Eun Jung Kim 0002
• Stefan Kratsch
• Marcin Pilipczuk
• Magnus Wahlström

We show a flow-augmentation algorithm in directed graphs: There exists a randomized polynomial-time algorithm that, given a directed graph G , two integers s , t ∈ V ( G ), and an integer k , adds (randomly) to G a number of arcs such that for every minimal st -cut Z in G of size at most k , with probability 2 − poly ( k ) the set Z becomes a minimum st -cut in the resulting graph. The directed flow-augmentation tool allows us to prove (randomized) fixed-parameter tractability of a number of problems parameterized by the cardinality of the deletion set, whose parameterized complexity status was repeatedly posed as open problems: Chain SAT, defined by Chitnis, Egri, and Marx [ESA’13, Algorithmica’17], a number of weighted variants of classic directed cut problems, such as Weighted st -Cut, Weighted Directed Feedback Vertex Set, or Weighted Almost 2-SAT. By proving that Chain SAT is (randomized) FPT, we confirm a conjecture of Chitnis, Egri, and Marx that, for any graph H , if the List H -Coloring problem is polynomial-time solvable, then the corresponding vertex-deletion problem is fixed-parameter tractable (with the remark that our algorithms are randomized).

SODA Conference 2021 Conference Paper

Optimal Discretization is Fixed-parameter Tractable

• Stefan Kratsch
• Tomás Masarík
• Irene Muzi
• Marcin Pilipczuk
• Manuel Sorge

Given two disjoint sets W 1 and W 2 of points in the plane, the O ptimal D iscretization problem asks for the minimum size of a family of horizontal and vertical lines that separate W 1 from W 2, that is, in every region into which the lines partition the plane there are either only points of W 1, or only points of W 2, or the region is empty. Equivalently, O ptimal D iscretization can be phrased as a task of discretizing continuous variables: We would like to discretize the range of x -coordinates and the range of y -coordinates into as few segments as possible, maintaining that no pair of points from W 1 × W 2 are projected onto the same pair of segments under this discretization. We provide a fixed-parameter algorithm for the problem, parameterized by the number of lines in the solution. Our algorithm works in time, where k is the bound on the number of lines to find and n is the number of points in the input. Our result answers in positive a question of Bonnet, Giannopolous, and Lampis [IPEC 2017] and of Froese (PhD thesis, 2018) and is in contrast with the known intractability of two closely related generalizations: the Rectangle Stabbing problem and the generalization in which the selected lines are not required to be axis-parallel.

SODA Conference 2021 Conference Paper

Solving hard cut problems via flow-augmentation

• Eun Jung Kim 0002
• Stefan Kratsch
• Marcin Pilipczuk
• Magnus Wahlström

We present a new technique for designing fixed-parameter algorithms for graph cut problems in undirected graphs, which we call flow augmentation. Our technique is applicable to problems that can be phrased as a search for an (edge) ( s, t )-cut of cardinality at most k in an undirected graph G with designated terminals s and t. More precisely, we consider problems where an (unknown) solution is a set Z ⊆ E ( G ) of size at most k such that in G – Z, s and t are in distinct connected components, every edge of Z connects two distinct connected components of G – Z, and if we define the set Z s, t ⊆ Z as those edges e ∊ Z for which there exists an ( s, t )-path P e with E ( P e ) ∩ Z = { e }, then Z s, t separates s from t. We prove that in the above scenario one can in randomized time k (1) (| V ( G )| + | E ( G )|) add a number of edges to the graph so that with probably at least 2 – ( k log k ) no added edge connects two components of G – Z, and Z s, t becomes a minimum cut between s and t. This additional property becomes a handy lever in applications. For example, consider the question of an ( s, t )-cut of cardinality at most k and of minimum possible weight (assuming edge weights in G ). While the problem is NP-hard in general, it easily reduces to the maximum flow / minimum cut problem if we additionally assume that k is the minimum possible cardinality of an ( s, t )-cut in G. Hence, we immediately obtain that the aforementioned problem admits an 2 ( k log k ) n (1) -time randomized fixed-parameter algorithm. We apply our method to obtain a randomized fixed-parameter algorithm for a notorious “hard nut” graph cut problem we call Coupled Min-Cut. This problem emerges out of the study of FPT algorithms for Min CSP problems (see below), and was unamenable to other techniques for parameterized algorithms in graph cut problems, such as Randomized Contractions, Treewidth Reduction or Shadow Removal. In fact, we go one step further. To demonstrate the power of the approach, we consider more generally the Boolean Min CSP(Γ)-problems, a. k. a. Min SAT(Γ), parameterized by the solution cost. This is a framework of optimization problems that includes problems such as Almost 2-SAT and the notorious i -Chain SAT problem. We are able to show that every problem Min SAT(Γ) is either (1) FPT, (2) W[1]-hard, or (3) able to express the soft constraint ( u → v ), and thereby also the min-cut problem in directed graphs. All the W[1]-hard cases were known or immediate, and the main new result is an FPT algorithm for a generalization of Coupled Min-Cut. In other words, flow-augmentation is powerful enough to let us solve every fixed-parameter tractable problem in the class, except those that explicitly encompass directed graph cuts.

TCS Journal 2020 Journal Article

Bipartite graphs of small readability

• Rayan Chikhi
• Vladan Jovičić
• Stefan Kratsch
• Paul Medvedev
• Martin Milanič
• Sofya Raskhodnikova
• Nithin Varma

We study a parameter of bipartite graphs called readability, introduced by Chikhi et al. (Discrete Applied Mathematics, 2016) and motivated by applications of overlap graphs in bioinformatics. The behavior of the parameter is poorly understood. The complexity of computing it is open and it is not known whether the decision version of the problem is in NP. The only known upper bound on the readability of a bipartite graph (following from a work of Braga and Meidanis, LATIN 2002) is exponential in the maximum degree of the graph. Graphs that arise in bioinformatics applications have low readability. In this paper, we focus on graph families with readability o ( n ), where n is the number of vertices. We show that the readability of n-vertex bipartite chain graphs is between Ω ( log ⁡ n ) and O ( n ). We give an efficiently testable characterization of bipartite graphs of readability at most 2 and completely determine the readability of grids, showing in particular that their readability never exceeds 3. As a consequence, we obtain a polynomial time algorithm to determine the readability of induced subgraphs of grids. One of the highlights of our techniques is the appearance of Euler's totient function in the analysis of the readability of bipartite chain graphs. We also develop a new technique for proving lower bounds on readability, which is applicable to dense graphs with a large number of distinct degrees.

TCS Journal 2018 Journal Article

Parameterized complexity of team formation in social networks

• Robert Bredereck
• Jiehua Chen
• Falk Hüffner
• Stefan Kratsch

Given a task that requires some skills and a social network of individuals with different skills, the Team Formation problem asks to find a team of individuals that together can perform the task, while minimizing communication costs. Since the problem is NP-hard, we identify the source of intractability by analyzing its parameterized complexity with respect to parameters such as the total number of skills k, the team size l, the communication cost budget b, and the maximum vertex degree Δ. We show that the computational complexity strongly depends on the communication cost measure: when using the weight of a minimum spanning tree of the subgraph formed by the selected team, we obtain fixed-parameter tractability for example with respect to the parameter k. In contrast, when using the diameter as measure, the problem is intractable with respect to any single parameter; however, combining Δ with either b or l yields fixed-parameter tractability.

MFCS Conference 2016 Conference Paper

Preprocessing Under Uncertainty: Matroid Intersection

• Stefan Fafianie
• Eva-Maria C. Hols
• Stefan Kratsch
• Vuong Anh Quyen

We continue the study of preprocessing under uncertainty that was initiated independently by Assadi et al. (FSTTCS 2015) and Fafianie et al. (STACS 2016). Here, we are given an instance of a tractable problem with a large static/known part and a small part that is dynamic/uncertain, and ask if there is an efficient algorithm that computes an instance of size polynomial in the uncertain part of the input, from which we can extract an optimal solution to the original instance for all (usually exponentially many) instantiations of the uncertain part. In the present work, we focus on the Matroid Intersection problem. Amongst others we present a positive preprocessing result for the important case of finding a largest common independent set in two linear matroids. Motivated by an application for intersecting two gammoids we also revisit Maximum Flow. There we tighten a lower bound of Assadi et al. and give an alternative positive result for the case of low uncertain capacity that yields a Maximum Flow instance as output rather than a matrix.

I&C Journal 2015 Journal Article

Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth

• Hans L. Bodlaender
• Marek Cygan
• Stefan Kratsch
• Jesper Nederlof

It is well known that many local graph problems, like Vertex Cover and Dominating Set, can be solved in time 2 O ( tw ) | V | O ( 1 ) for graphs G = ( V, E ) with a given tree decomposition of width tw. However, for nonlocal problems, like the fundamental class of connectivity problems, for a long time we did not know how to do this faster than tw O ( tw ) | V | O ( 1 ). Recently, Cygan et al. (FOCS 2011) presented Monte Carlo algorithms for a wide range of connectivity problems running in time c tw | V | O ( 1 ) for a small constant c, e. g. , for Hamiltonian Cycle and Steiner Tree. Naturally, this raises the question whether randomization is necessary to achieve this runtime; furthermore, it is desirable to also solve counting and weighted versions (the latter without incurring a pseudo-polynomial cost in the runtime in terms of the weights). We present two new approaches rooted in linear algebra, based on matrix rank and determinants, which provide deterministic c tw | V | O ( 1 ) time algorithms, also for weighted and counting versions. For example, in this time we can solve Traveling Salesman or count the number of Hamiltonian cycles. The rank based ideas provide a rather general approach for speeding up even straightforward dynamic programming formulations by identifying “small” sets of representative partial solutions; we focus on the case of expressing connectivity via sets of partitions, but the essential ideas should have further applications. The determinant-based approach uses the Matrix Tree Theorem for deriving closed formulas for counting versions of connectivity problems; we show how to evaluate those formulas via dynamic programming.

SODA Conference 2014 Conference Paper

Point Line Cover: The Easy Kernel is Essentially Tight

• Stefan Kratsch
• Geevarghese Philip
• Saurabh Ray

The input to the NP-hard Point Line Cover problem (PLC) consists of a set of n points on the plane and a positive integer k, and the question is whether there exists a set of at most k lines which pass through all points in. By straightforward reduction rules one can efficiently reduce any input to one with at most k 2 points. We show that this easy reduction is already essentially tight under standard assumptions. More precisely, unless the polynomial hierarchy collapses to its third level, for any ∊ > 0, there is no polynomial-time algorithm that reduces every instance (, k ) of PLC to an equivalent instance with ( k 2– ∊ ) points. This answers, in the negative, an open problem posed by Lokshtanov (PhD Thesis, 2009). Our proof uses the notion of a kernel from parameterized complexity, and the machinery for deriving lower bounds on the size of kernels developed by Dell and van Melkebeek (STOC 2010). It has two main ingredients: We first show, by reduction from Vertex Cover, that—unless the polynomial hierarchy collapses—PLC has no kernel of total size ( k 2– ∊ ) bits. This does not directly imply the claimed lower bound on the number of points, since the best known polynomial-time encoding of a PLC instance with n points requires ω ( n 2 ) bits. To get around this hurdle we build on work of Goodman, Pollack and Sturmfels (STOC 1989) and devise an oracle communication protocol of cost ( n log n ) for PLC; its main building blocks are a bound of ( n O ( n ) ) for the order types of n points that are not necessarily in general position and an explicit (albeit slow) algorithm that enumerates a superset of size n O(n) of all possible order types of n points. This protocol, together with the lower bound on the total size (which also holds for such protocols), yields the stated lower bound on the number of points. While a number of essentially tight polynomial lower bounds on total sizes of kernels are known, our result is—to the best of our knowledge—the first to show a nontrivial lower bound for structural/secondary parameters.

I&C Journal 2013 Journal Article

Data reduction for graph coloring problems

• Bart M.P. Jansen
• Stefan Kratsch

This paper studies the kernelization complexity of graph coloring problems with respect to certain structural parameterizations of the input instances. We are interested in how well polynomial-time data reduction can provably shrink instances of coloring problems, in terms of the chosen parameter. It is well known that deciding 3-colorability is already NP-complete, hence parameterizing by the requested number of colors is not fruitful. Instead, we pick up on a research thread initiated by Cai (DAM, 2003) who studied coloring problems parameterized by the modification distance of the input graph to a graph class on which coloring is polynomial-time solvable; for example parameterizing by the number k of vertex-deletions needed to make the graph chordal. We obtain various upper and lower bounds for kernels of such parameterizations of q-Coloring, complementing Caiʼs study of the time complexity with respect to these parameters. Our results show that the existence of polynomial kernels for q-Coloring parameterized by the vertex-deletion distance to a graph class F is strongly related to the existence of a function f ( q ) which bounds the number of vertices which are needed to preserve the no-answer to an instance of q-List Coloring on F.

STOC Conference 2013 Conference Paper

Fast hamiltonicity checking via bases of perfect matchings

• Marek Cygan
• Stefan Kratsch
• Jesper Nederlof

For an even integer t ≥ 2, the Matching Connectivity matrix H t is a matrix that has rows and columns both labeled by all perfect matchings of the complete graph K t on t vertices; an entry H t [M 1 ,M 2 ] is 1 if M 1 ∪ M 2 is a Hamiltonian cycle and 0 otherwise. Motivated by the computational study of the Hamiltonicity problem, we present three results on the structure of H t : We first show that H t has rank exactly 2 t/2-1 over GF(2) via an appropriate factorization that explicitly provides families of matchings X t forming bases for H t . Second, we show how to quickly change representation between such bases. Third, we notice that the sets of matchings X t induce permutation matrices within H t . We use the factorization to derive an 1.888 n n O(1) time Monte Carlo algorithm that solves the Hamiltonicity problem in directed bipartite graphs. Our algorithm as well counts the number of Hamiltonian cycles modulo two in directed bipartite or undirected graphs in the same time bound. Moreover, we use the fast basis change algorithm from the second result to present a Monte Carlo algorithm that given an undirected graph on n vertices along with a path decomposition of width at most pw decides Hamiltonicity in (2+√2) pw n O(1) time. Finally, we use the third result to show that for every ε >0 this cannot be improved to (2+√2-ε) pw n O(1) time unless the Strong Exponential Time Hypothesis fails, i.e., a faster algorithm for this problem would imply the breakthrough result of an O((2-ε') n ) time algorithm for CNF-Sat.

TCS Journal 2013 Journal Article

Kernel bounds for path and cycle problems

• Hans L. Bodlaender
• Bart M.P. Jansen
• Stefan Kratsch

Connectivity problems like k -Path and k -Disjoint Paths relate to many important milestones in parameterized complexity, namely the Graph Minors Project, color coding, and the recent development of techniques for obtaining kernelization lower bounds. This work explores the existence of polynomial kernels for various path and cycle problems, by considering nonstandard parameterizations. We show polynomial kernels when the parameters are a given vertex cover, a modulator to a cluster graph, or a (promised) max leaf number. We obtain lower bounds via cross-composition, e. g. , for Hamiltonian Cycle and related problems when parameterized by a modulator to an outerplanar graph.

TCS Journal 2013 Journal Article

Parameterized complexity of vertex deletion into perfect graph classes

• Pinar Heggernes
• Pim van ’t Hof
• Bart M.P. Jansen
• Stefan Kratsch
• Yngve Villanger

Vertex deletion problems are at the heart of parameterized complexity. For a graph class F, the F -Deletion problem takes as input a graph G and an integer k. The question is whether it is possible to delete at most k vertices from G such that the resulting graph belongs to F. Whether Perfect Deletion is fixed-parameter tractable, and whether Chordal Deletion admits a polynomial kernel, when parameterized by k, have been stated as open questions in previous work. We show that Perfect Deletion and Weakly Chordal Deletion are W [ 2 ] -hard when parameterized by k. In search of positive results, we study a restricted variant of the F -Deletion problem. In this restricted variant, the deleted vertices must be taken from a specified set X, and we parameterize by | X |. We show that for Perfect Deletion and Weakly Chordal Deletion, although this restriction immediately ensures fixed-parameter tractability, it is not enough to yield polynomial kernels, unless NP ⊆ coNP / poly. On the positive side, for Chordal Deletion, the restriction enables us to obtain a kernel with O ( | X | 4 ) vertices.

AAAI Conference 2012 Conference Paper

A Multivariate Complexity Analysis of Lobbying in Multiple Referenda

• Robert Bredereck
• Jiehua Chen
• Sepp Hartung
• Rolf Niedermeier
• Ondřej Suchý
• Stefan Kratsch

We extend work by Christian et al. [Review of Economic Design 2007] on lobbying in multiple referenda by first providing a more fine-grained analysis of the computational complexity of the NP-complete LOBBYING problem. Herein, given a binary matrix, the columns represent issues to vote on and the rows correspond to voters making a binary vote on each issue. An issue is approved if a majority of votes has a 1 in the corresponding column. The goal is to get all issues approved by modifying a minimum number of rows to all-1-rows. In our multivariate complexity analysis, we present a more holistic view on the nature of the computational complexity of LOBBYING, providing both (parameterized) tractability and intractability results, depending on various problem parameterizations to be adopted. Moreover, we show non-existence results concerning efficient and effective preprocessing for LOB- BYING and introduce natural variants such as RESTRICTED LOBBYING and PARTIAL LOBBYING.

SODA Conference 2012 Conference Paper

Co-nondeterminism in compositions: a kernelization lower bound for a Ramsey-type problem

• Stefan Kratsch

Until recently, techniques for obtaining lower bounds for kernelization were one of the most sought after tools in the field of parameterized complexity. Now, after a strong influx of techniques, we are in the fortunate situation of having tools available that are even stronger than what has been required in their applications so far. Based on a result of Fortnow and Santhanam (STOC 2008, JCSS 2011), Bodlaender et al. (ICALP 2008, JCSS 2009) showed that, unless NP ⊆ coNP/poly, the existence of a deterministic polynomial-time composition algorithm, i. e. , an algorithm which outputs an instance of bounded parameter value which is yes if and only if one of t input instances is yes, rules out the existence of polynomial kernels for a problem. Dell and van Melkebeek (STOC 2010) continued this line of research and, amongst others, were able to rule out kernels of size O ( k d − ∊ ) for certain problems, assuming NP ⊆ coNP/poly. It is an immediate consequence of their work that even the existence of a co-nondeterministic composition rules out polynomial kernels. However, in contrast to the numerous applications of deterministic composition, the added power of co-nondeterminism has not yet been harnessed to obtain kernelization lower bounds. In this work we present the first example of how co-nondeterminism can help to make a composition algorithm. We study the existence of polynomial kernels for a Ramsey-type problem: Given a graph G and an integer k, the question is whether G contains an independent set or a clique of size at least k. It was asked by Rod Downey whether this problem admits a polynomial kernelization, and such a result would greatly speed up the computation of Ramsey numbers. We provide a co-nondeterministic composition based on embedding t instances into a single host graph H. The crux is that the host graph H needs to observe a bound of ℓ ∊ O (log t ) on both its maximum independent set and maximum clique size, while also having a cover of its vertex set by independent sets and cliques all of size ℓ; the co-nondeterministic composition is build around the search for such graphs. Thus we show that, unless NP ⊆ coNP/poly (and the polynomial hierarchy collapses), the problem does not admit a kernelization with polynomial size guarantee.

SODA Conference 2012 Conference Paper

Compression via matroids: a randomized polynomial kernel for odd cycle transversal

• Stefan Kratsch
• Magnus Wahlström

FOCS Conference 2012 Conference Paper

Representative Sets and Irrelevant Vertices: New Tools for Kernelization

• Stefan Kratsch
• Magnus Wahlström

The existence of a polynomial kernel for Odd Cycle Transversal was a notorious open problem in parameterized complexity. Recently, this was settled by the present authors (Kratsch and Wahlstrom, SODA 2012), with a randomized polynomial kernel for the problem, using matroid theory to encode How questions over a set of terminals in size polynomial in the number of terminals (rather than the total graph size, which may be superpolynomially larger). In the current work we further establish the usefulness of matroid theory to kernelization by showing applications of a result on representative sets due to Lovasz (Combinatorial Surveys 1977) and Marx (TCS 2009). We show how representative sets can be used to give a polynomial kernel for the elusive Almost 2-sat problem (where the task is to remove at most k clauses to make a 2-CNF formula satisfiable), solving a major open problem in kernelization. We further apply the representative sets tool to the problem of finding irrelevant vertices in graph cut problems, that is, vertices which can be made undeletable without affecting the status of the problem. This gives the first significant progress towards a polynomial kernel for the Multiway Cut problem; in particular, we get a polynomial kernel for Multiway Cut instances with a bounded number of terminals. Both these kernelization results have significant spin-off effects, producing the first polynomial kernels for a range of related problems. More generally, the irrelevant vertex results have implications for covering min-cuts in graphs. In particular, given a directed graph and a set of terminals, we can find a set of size polynomial in the number of terminals (a cut-covering set) which contains a minimum vertex cut for every choice of sources and sinks from the terminal set. Similarly, given an undirected graph and a set of terminals, we can find a set of vertices, of size polynomial in the number of terminals, which contains a minimum multiway cut for every partition of the terminals into a bounded number of sets. Both results are polynomial time. We expect this to have further applications; in particular, we get direct, reduction rule-based kernelizations for all problems above, in contrast to the indirect compression-based kernel previously given for Odd Cycle Transversal. All our results are randomized, with failure probabilities which can be made exponentially small in the size of the input, due to needing a representation of a matroid to apply the representative sets tool.

MFCS Conference 2010 Conference Paper

Parameterized Complexity and Kernelizability of Max Ones and Exact Ones Problems

• Stefan Kratsch
• Dániel Marx
• Magnus Wahlström

Abstract For a finite set \(\it\Gamma\) of Boolean relations, Max Ones SAT( \(\it\Gamma\) ) and Exact Ones SAT( \(\it\Gamma\) ) are generalized satisfiability problems where every constraint relation is from \(\it\Gamma\), and the task is to find a satisfying assignment with at least/exactly k variables set to 1, respectively. We study the parameterized complexity of these problems, including the question whether they admit polynomial kernels. For Max Ones SAT( \(\it\Gamma\) ), we give a classification into 5 different complexity levels: polynomial-time solvable, admits a polynomial kernel, fixed-parameter tractable, solvable in polynomial time for fixed k, and NP-hard already for k = 1. For Exact Ones SAT( \(\it\Gamma\) ), we refine the classification obtained earlier by having a closer look at the fixed-parameter tractable cases and classifying the sets \(\it\Gamma\) for which Exact Ones SAT( \(\it\Gamma\) ) admits a polynomial kernel.