Pith. sign in

REVIEW 2 major objections 5 minor 58 references

On Kernelization with Access to NP-Oracles

T0 review · 2 major / 5 minor · reviewed 2026-08-05 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper introduces P^NP-kernels, polynomial-time preprocessing with an NP-oracle, and proves that a decidable parameterized problem lies in FPT^NP exactly when it admits one; it then extends OR-cross-composition lower bounds and proves a

desk verdict Solid new notion and lower-bound framework, but Section 7's positive results are under-proved—Theorem 15's proof literally stops mid-sentence. read the letter →

arxiv 2508.10550 v1 pith:3RCDZ33I submitted 2025-08-14 cs.CC

Hendrik Molter , Meirav Zehavi This is my paper · ORCID
classification cs.CC MSC 68Q1768Q2768Q2568R10
keywords kernelizationparameterizedcomplexitySAT-solveroracleP^NP-kernelOR-cross-compositionFPT^NPdiscoveryproblemspolynomialhierarchy
topics The Hierarchy Problem
open problems The Hierarchy Problem
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Kernelization normally demands that a preprocessing routine run in polynomial time. This paper relaxes the demand: the preprocessor may make polynomially many calls to an NP-oracle (a SAT-solver or ILP-solver) and must still output an equivalent instance whose size depends only on the parameter. The paper's central conceptual claim is that this relaxation is the exact oracle analogue of classical kernelization: a decidable parameterized problem is solvable by a fixed-parameter algorithm with NP-oracle access ($\mathrm{FPT}^{\mathrm{NP}}$) if and only if it admits such a kernel, called a $\mathrm{P}^{\mathrm{NP}}$-kernel. For polynomial-size compression, the paper adapts OR-cross-composition lower bounds to prove that some problems above NP, such as $\exists\forall$-DNF, still have no polynomial $\mathrm{P}^{\mathrm{NP}}$-kernel unless the polynomial hierarchy collapses. On the positive side, a meta-theorem shows that every graph, Boolean, or set-system problem with a polynomial kernel has a 'discovery' version that admits a polynomial $\mathrm{P}^{\mathrm{NP}}$-kernel.

What carries the argument

The central object is the $\mathrm{P}^{\mathrm{NP}}$-kernel: a polynomial-time oracle algorithm that maps $(x,r)$ to an equivalent $(x',r')$ with $|x'|+r' \le f(r)$; it is polynomial when $f(r)=r^{O(1)}$. The machinery that carries the negative results is the $\mathrm{P}^{\mathrm{NP}}$-OR-cross-composition, which combines $t$ instances into one instance while allowing oracle calls during the construction, transferring classical OR-composition lower bounds to the oracle setting. The positive results are carried by the discovery-problem wrapper: use the oracle to reveal the hidden graph, formula, or set system, kernelize the revealed instance, and re-encode the kernel output using constant-siz

What would settle it

Run the re-encoding step of the discovery meta-theorem on a polynomial kernel that changes the vertex set of a graph, and check whether every adjacency in the kernel output can be expressed with constant-size SAT instances; if any adjacency requires a larger gadget, the meta-theorem's construction fails at the stated level of generality. Independently, a polynomial $\mathrm{P}^{\mathrm{NP}}$-kernel for $\exists\forall$-DNF parameterized by the number of variables would contradict the paper's lower-bound framework unless the polynomial hierarchy collapses.

Watch

Extended reading notes

Core claim

Let $L$ be a decidable parameterized problem. The paper defines a $\mathrm{P}^{\mathrm{NP}}$-kernel as a polynomial-time algorithm with oracle access to an NP-complete problem that maps $(x,r)$ to an equivalent $(x',r')$ with $|x'|+r' \le f(r)$, and a polynomial $\mathrm{P}^{\mathrm{NP}}$-kernel when $f(r)=r^{O(1)}$. Its central discovery is the exact correspondence $L \in \mathrm{FPT}^{\mathrm{NP}}$ if and only if $L$ admits a $\mathrm{P}^{\mathrm{NP}}$-kernel, matching the classical theorem that decidable FPT equals kernelizable. Since many natural problems above NP, such as problems hard for the second level of the polynomial hierarchy or PSPACE-hard problems, are in $\mathrm{FPT}^{\mathr

Load-bearing premise

The discovery-problem results assume that the polynomial kernel for the underlying problem can be applied to the oracle-revealed instance and that the kernel output can be re-encoded as a discovery instance using only constant-size SAT instances; if a kernel changes the vertex set or parameterization, or the re-encoding needs larger SAT gadgets, the claimed $\mathrm{P}^{\mathrm{NP}}$-kernel does not follow.

Editorial extensions

If this is right

  • Every decidable problem in $\mathrm{FPT}^{\mathrm{NP}}$ automatically has a $\mathrm{P}^{\mathrm{NP}}$-kernel, so membership in $\mathrm{FPT}^{\mathrm{NP}}$ and kernelizability coincide at the non-polynomial level.
  • Problems above NP can now have a well-defined preprocessing theory: a problem like $\exists\forall$-DNF cannot be compressed to polynomial size by an NP-oracle preprocessing routine unless the polynomial hierarchy collapses.
  • Classical OR-cross-composition lower bounds transfer to the oracle model, giving a formal method to prove that some $\mathrm{FPT}^{\mathrm{NP}}$ problems are not efficiently compressible even with SAT-solver help.
  • Discovery versions inherit polynomial $\mathrm{P}^{\mathrm{NP}}$-kernels from ordinary polynomial kernels; in particular, Discovery Vertex Cover Reconfiguration parameterized by $k$ has a polynomial $\mathrm{P}^{\mathrm{NP}}$-kernel despite being PSPACE-hard.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Editorial inference: the equivalence theorem suggests a practical design rule: any fixed-parameter algorithm with SAT-oracle access can be converted into a preprocessing routine automatically, so the open engineering question becomes whether the resulting kernel size can be made polynomial.
  • Editorial inference: the discovery meta-theorem's re-encoding step is the fragile point; if an underlying polynomial kernel changes the vertex set or parameterization, the proof as written may not cover it, so the theorem's generality depends on kernels that preserve the discovery format.
  • Editorial inference: the $\mathrm{P}^{\mathrm{NP}}$-OR-cross-composition technique should transfer to other problems already known to lie in $\mathrm{FPT}^{\mathrm{NP}}$, such as planning or belief revision, potentially yielding new no-polynomial-$\mathrm{P}^{\mathrm{NP}}$-kernel results under the same polynomial-hierarchy assumption.
  • Editorial inference: a natural testable extension is to count oracle calls rather than treating polynomially many as free, giving a finer-grained preprocessing hierarchy between classical kernels and $\mathrm{P}^{\mathrm{NP}}$-kernels.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. This paper introduces P^NP-kernelization, a relaxation of classical kernelization in which the preprocessing algorithm is a polynomial-time machine with oracle access to an NP-complete problem. The central conceptual result (Theorem 2) is that a decidable parameterized problem admits a P^NP-kernel if and only if it belongs to FPT^NP. The paper also develops a lower-bound framework based on OR-cross-compositions in the oracle setting, and applies it to rule out polynomial P^NP-kernels for problems such as ∃∀-DNF and Weighted Clique-Free Vertex Deletion under standard complexity assumptions. Finally, Section 7 studies "discovery problems": it claims a polynomial P^NP-kernel for Discovery Vertex Cover Reconfiguration parameterized by k (Theorem 15) and a general meta-theorem (Theorem 16) saying that the discovery versions of graph, Boolean, and set-system problems inherit polynomial P^NP-kernels from ordinary polynomial kernels.

Significance. The notion of P^NP-kernel is a natural and potentially useful extension of kernelization, especially for problems above NP where SAT/ILP solvers are already used in practice. The equivalence with FPT^NP (Theorem 2) is clean and gives the new notion the same foundational status as ordinary kernels have for FPT. The OR-cross-composition framework appears technically sound and extends an established lower-bound technique to the oracle setting. If the discovery-problem results are fully proved, the meta-theorem would be a convenient tool for transferring polynomial kernels to a class of problems whose inputs are only implicitly given. However, the current manuscript contains a significant missing proof in the discovery section, so the positive results in Section 7 are not yet established as written.

major comments (2)
  1. [§7, Theorem 15] The proof of Theorem 15 is incomplete. It ends immediately after the sentence "we use a kernelization algorithm by Damaschke and Molokov [13] that produces a graph G' of size O(k^2)"; there is no continuation. To prove a polynomial P^NP-kernel for Discovery Vertex Cover Reconfiguration, one must output an instance of the same discovery problem, not merely a graph G'. The proof must specify how the kernel output is converted into SAT instances for the vertex pairs, how the start and target minimal vertex covers S'', T'' are defined, how the parameters k'' and ℓ'' are set, and why the reconfiguration sequence and minimality conditions are preserved. As written, the claimed positive answer is unsupported. The ambiguity about which problem the Damaschke–Molokov algorithm kernelizes (Vertex Cover, Vertex Cover Reconfiguration, or minimal hitting sets) makes the gap more serious.
  2. [§7, Theorem 16] The proof of the meta-theorem relies on the phrase "by using trivial yes- and no-instances (of constant size) of Satisfiability in a straightforward manner." This is too compressed for a proof of a generally stated theorem. The authors should spell out how an arbitrary output I'' of the kernelization algorithm for L is re-encoded as an instance of Discovery L: what the new vertex/variable/set universe is, how the per-pair SAT instances are constructed, and how the parameter in the discovery instance is obtained (the kernel may output a parameter k'' different from the original k). This is likely a fixable presentation gap, but as written it is not fully verifiable.
minor comments (5)
  1. [Abstract] Typographical issue: "variousNP" should read "various NP".
  2. [§2 / Definitions] The notation "PNP" is used throughout; please define it explicitly as P^NP at first use. The same applies to the hyphenated word "P^NP-kernel".
  3. [§7, Theorem 14 proof] The proof contains the typo "no-instace" (should be "no-instance"). Also, the first sentence "From this we immediately get the first result" should mention that an explicitly given graph can be encoded by constant-size SAT instances, so the reduction is polynomial.
  4. [Bibliography] In reference [20], "Prodeedings" should be "Proceedings".
  5. [§7, Theorem 16] The theorem is stated for graph, Boolean, and set-system problems, but the discovery definitions for these classes are given only informally in a bullet list. It would help to give a formal definition of the parameterized discovery problem for each class, including what the parameter k is.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; central equivalence is proved directly and applications rest on external results.

full rationale

The central claim (Theorem 2: decidable parameterized problem is in FPT^NP iff it admits a P^NP-kernel) is proved by direct construction rather than by assuming the conclusion: if f(r)<|x| the instance is solved in polynomial time with the NP-oracle and a trivial kernel is output, while if f(r)>|x| the original instance is already bounded in the parameter; conversely, a P^NP-kernel followed by a decidable solver for the small instance yields an FPT^NP algorithm. The definitions of P^NP-kernel and FPT^NP are distinct, so this is not a self-definitional reduction. The lower-bound framework uses standard external OR-composition machinery (Dell–van Melkebeek, Fortnow–Santhanam) and the constructions are self-contained; no fitted parameter is renamed as a prediction. The meta-theorem (Theorem 16) is a valid reduction: the NP-oracle materializes the hidden object, an external polynomial kernel for L compresses it, and the result is re-encoded using constant-size trivial SAT instances. No load-bearing self-citation was found: the authors cite their own textbook [23] and related papers [47,48] only for background and context, not to force the central claim. The one notable weakness is an omitted proof in Theorem 15: the proof stops after 'we use a kernelization algorithm by Damaschke and Molokov [13] that produces a graph G′ of size O(k^2)...' and never specifies how G′ is converted back into a Discovery Vertex Cover Reconfiguration instance, nor how minimality of S,T and the length parameter ℓ are preserved. This is a completeness gap and a correctness risk, but it is not a circular step: the missing re-encoding is neither a fitted input called a prediction, nor a self-citation imported as a uniqueness theorem, nor a definitional identity. Under the review rule for omitted proofs, this gap is flagged here and weighed as a non-circular drawback, so it does not raise the circularity score.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No empirical parameters are fitted. The paper introduces definitions (P^NP-kernel, discovery problems) but these are formal definitions, not entities with independent evidence requirements.

assumptions (4)
  • domain assumption The polynomial hierarchy does not collapse.
    Standard assumption underlying OR-composition lower bounds; if false, negative results are void.
  • domain assumption NP-oracle queries can be made adaptively and polynomially many times.
    Definition of P^NP and FPT^NP; standard in oracle complexity.
  • standard math Existence of NP-complete problems such as Satisfiability.
    Used to encode oracle and discovery instances; textbook result.
  • domain assumption Parameterized problems considered are decidable.
    The equivalence theorem and kernels require the problem to be decidable to solve the reduced instance.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On Kernelization with Access to NP-Oracles." pith.science (2026). https://pith.science/paper/3RCDZ33I

@misc{pith2026250810550,
  author       = {Pith},
  title        = {Pith review of: On Kernelization with Access to NP-Oracles},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/3RCDZ33I}},
  note         = {Machine review of arXiv:2508.10550}
}
read the original abstract

Kernelization is the standard framework to analyze preprocessing routines mathematically. Here, in terms of efficiency, we demand the preprocessing routine to run in time polynomial in the input size. However, today, various NP-complete problems are already solved very fast in practice; in particular, SAT-solvers and ILP-solvers have become extremely powerful and used frequently. Still, this fails to capture the wide variety of computational problems that lie at higher levels of the polynomial hierarchy. Thus, for such problems, it is natural to relax the definition of kernelization to permit the preprocessing routine to make polynomially many calls to a SAT-solver, rather than run, entirely, in polynomial time. Our conceptual contribution is the introduction of a new notion of a kernel that harnesses the power of SAT-solvers for preprocessing purposes, and which we term a P^NP-Kernel. Technically, we investigate various facets of this notion, by proving both positive and negative results, including a lower-bounds framework to reason about the negative results. Here, we consider both satisfiability and graph problems. Additionally, we present a meta-theorem for so-called "discovery problems". This work falls into a long line of research on extensions of the concept of kernelization, including lossy kernels [Lokshtanov et al., STOC '17], dynamic kernels [Alman et al., ACM TALG '20], counting kernels [Lokshtanov et al., ICTS '24], and streaming kernels [Fafianie and Kratsch, MFCS '14].

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

58 extracted references · 58 canonical work pages

  1. [13]

    Damaschke and L

    P. Damaschke and L. Molokov. The union of minimal hitting sets: Parameterized combinatorial bounds and counting.Journal of Discrete Algorithms, 7(4):391–401, 2009. 21

    work page 2009

  2. [1]

    |x′| + r′ ≤ f (r), for some computable functionf, and

    work page

  3. [2]

    Analogous to the case of kernels and fixed-parameter tractable problems, we get the following

    (x′, r′) ∈ L if and only if(x, r) ∈ L. Analogous to the case of kernels and fixed-parameter tractable problems, we get the following. Theorem 2.A decidable parameterized problemL is inFPTNP if and only if it admits aPNP-kernel. Proof. Assume that L is in FPTNP. Then there is an FPT-algorithm that has oracle access to an NP-complete problem that solves eac...

    work page

  4. [3]

    |x′| + r′ ∈ rO(1), and

    work page

  5. [4]

    classical

    (x′, r′) ∈ L if and only if(x, r) ∈ L. Wefurthergiveadefinitionof(polynomial)compressionsintheoraclesetting, whichisanalogous to the “classical” (polynomial) compression [23]. A decidable parameterized problemL admits a (resp. polynomial) PNP-compression into a problem R ⊆ {0, 1}∗ if there is a PNP-algorithm that transforms each instance(x, r) ∈ {0, 1}∗ ×...

    work page

  6. [5]

    |y| ∈rO(1)), and

    |y| ≤f (r), for some computable functionf, (resp. |y| ∈rO(1)), and

    work page

  7. [6]

    y ∈ R if and only if(x, r) ∈ L. 8 ϕ1 = a1 ∨ a2, ϕ 2 = b1 ∨ b2, ϕ 3 = c1 ∨ c2, ϕ 4 = d1 ∨ d2 ϕ′ 1 = (a1 ∧ z1 ∧ ¬z2) ∨ (a2 ∧ z1 ∧ ¬z2), ϕ ′ 2 = (b1 ∧ ¬z1 ∧ z2) ∨ (b2 ∧ ¬z1 ∧ z2), ϕ′ 3 = (c1 ∧ z1 ∧ z2) ∨ (c2 ∧ z1 ∧ z2), ϕ ′ 4 = (d1 ∧ ¬z1 ∧ ¬z2) ∨ (d2 ∧ ¬z1 ∧ ¬z2) ϕ� = ϕ′ 1 ∨ ϕ′ 2 ∨ ϕ′ 3 ∨ ϕ′ 4 Figure 1: Example of thePNP-OR-cross-composition presented in the...

    work page

  8. [7]

    selection vertices

    The selection vertices form a clique, none of the edges are depicted except between pairs of selection vertices of which exactly one needs to be deleted. In the example, we have that the first and second bit of the binary representation ofi is a zero, the third is a one, and the last is a one as well. Now assume we are givent R-equivalent instancesx1, . ....

    work page

Show all 58 references
  1. [12]

    Cygan, F

    M. Cygan, F. V. Fomin, Ł. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. Parameterized Algorithms. Springer, 2015. 2, 5

    2015

  2. [14]

    H. Dell. AND-compression of NP-complete problems: Streamlined proof and minor observa- tions. Algorithmica, 75(2):403–423, 2016. 7, 11

    2016

  3. [15]

    Dell and D

    H. Dell and D. van Melkebeek. Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses.Journal of the ACM, 61(4):23:1–23:27, 2014. 3, 7, 9

    2014

  4. [16]

    R. G. Downey and M. R. Fellows. Fixed-parameter tractability and completeness II: On com- pleteness for W[1].Theoretical Computer Science, 141(1&2):109–131, 1995. 16

    1995

  5. [17]

    R. G. Downey and M. R. Fellows.Fundamentals of Parameterized Complexity. Springer, 2013. 2, 5, 16

    2013

  6. [18]

    A. Drucker. New limits to classical and quantum instance compression. SIAM Journal on Computing, 44(5):1443–1479, 2015. 7, 11

    2015

  7. [19]

    Endriss, R

    U. Endriss, R. de Haan, and S. Szeider. Parameterized complexity results for agenda safety in judgment aggregation. InProceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 127–136. ACM, 2015. 2

    2015

  8. [20]

    Fafianie and S

    S. Fafianie and S. Kratsch. Streaming kernelization. InProdeedings of the 39thInternational Symposium on Mathematical Foundations of Computer Science (MFCS),volume8635of Lecture Notes in Computer Science, pages 275–286. Springer, Springer, 2014. 5

    2014

  9. [21]

    M. R. Fellows. The lost continent of polynomial time: Preprocessing and kernelization. In Proceedings of the 2nd International Workshop on Parameterized and Exact Computation (IW- PEC), volume 4169 of Lecture Notes in Computer Science, pages 276–277. Springer, 2006. 1

    2006

  10. [22]

    Flum and M

    J. Flum and M. Grohe.Parameterized Complexity Theory, volume XIV ofTexts in Theoretical Computer Science. An EATCS Series. Springer, 2006. 2, 5

    2006

  11. [23]

    F. V. Fomin, D. Lokshtanov, S. Saurabh, and M. Zehavi.Kernelization: Theory of Parame- terized Preprocessing. Cambridge University Press, 2019. 2, 3, 5, 6, 7, 8, 9, 10, 21

    2019

  12. [24]

    Fortnow and R

    L. Fortnow and R. Santhanam. Infeasibility of instance compression and succinct PCPs for NP. Journal of Computer and System Sciences, 77(1):91–106, 2011. 2, 3, 7, 9

    2011

  13. [25]

    Onthekernelsizeofcliquecoverreductionsforrandomintersection graphs

    T.FriedrichandC.Hercher. Onthekernelsizeofcliquecoverreductionsforrandomintersection graphs. Journal of Discrete Algorithms, 34:128–136, 2015. 5

    2015

  14. [26]

    M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. 5, 22

    1979

  15. [27]

    C. P. Gomes, H. Kautz, A. Sabharwal, and B. Selman. Satisfiability solvers.Foundations of Artificial Intelligence, 3:89–134, 2008. 2 25

    2008

  16. [28]

    Gong and X

    W. Gong and X. Zhou. A survey of SAT solver. In Proceedings of the 1st International Conference on Applied Mathematics and Computer Science (ICAMCS), volume 1836. AIP Publishing, 2017. 2

    2017

  17. [29]

    Guo and R

    J. Guo and R. Niedermeier. Invitation to data reduction and problem kernelization.SIGACT News, 38(1):31–45, 2007. 2

    2007

  18. [30]

    R. de Haan. Parameterized complexity results for the kemeny rule in judgment aggregation. In Proceedings of the 22nd European Conference on Artificial Intelligence (ECAI), volume 285 of Frontiers in Artificial Intelligence and Applications, pages 1502–1510. IOS Press, 2016. 2

    2016

  19. [31]

    de Haan.Parameterized Complexity in the Polynomial Hierarchy

    R. de Haan.Parameterized Complexity in the Polynomial Hierarchy. Springer, 2019. 2, 3, 6, 9

    2019

  20. [32]

    de Haan and S

    R. de Haan and S. Szeider. The parameterized complexity of reasoning problems beyond NP. In Proceedings of the 14th International Conference on Principles of Knowledge Representation and Reasoning (KR). AAAI Press, 2014. 2

    2014

  21. [33]

    de Haan and S

    R. de Haan and S. Szeider. Fixed-parameter tractable reductions to SAT. InProceedings of the 17th International Conference on Theory and Applications of Satisfiability Testing (SAT), pages 85–102. Springer, 2014. 2, 6

    2014

  22. [34]

    de Haan and S

    R. de Haan and S. Szeider. Machine characterizations for parameterized complexity classes beyond para-NP. In Proceedings of the 41st International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), volume 8939 ofLecture Notes in Com- puter Scienc...

    2015

  23. [35]

    de Haan and S

    R. de Haan and S. Szeider. Parameterized complexity results for symbolic model checking of temporal logics. InProceedings of the 15th International Conference on Principles of Knowledge Representation and Reasoning (KR), pages 453–462. AAAI Press, 2016. 2

    2016

  24. [36]

    de Haan and S

    R. de Haan and S. Szeider. Parameterized complexity classes beyond para-NP. Journal of Computer and System Sciences, 87:16–57, 2017. 2, 6

    2017

  25. [37]

    de Haan and S

    R. de Haan and S. Szeider. A compendium of parameterized problems at higher levels of the polynomial hierarchy.Algorithms, 12(9):188, 2019. 2, 6

    2019

  26. [38]

    de Haan, M

    R. de Haan, M. Kronegger, and A. Pfandler. Fixed-parameter tractable reductions to SAT for planning. In Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI), pages 2897–2903. AAAI Press, 2015. 2

    2015

  27. [39]

    T. Ito, E. D. Demaine, N. J. Harvey, C. H. Papadimitriou, M. Sideri, R. Uehara, and Y. Uno. On the complexity of reconfiguration problems. Theoretical Computer Science, 412(12-14): 1054–1065, 2011. 19, 20

    2011

  28. [40]

    Jünger, T

    M. Jünger, T. M. Liebling, D. Naddef, G. L. Nemhauser, W. R. Pulleyblank, G. Reinelt, G. Rinaldi, and L. A. Wolsey.50 Years of integer programming 1958-2008: From the early years to the state-of-the-art. Springer Science & Business Media, 2009. 2

    1958

  29. [41]

    R. M. Karp. Reducibility among combinatorial problems. InComplexity of computer compu- tations, pages 85–103. 1972. 13, 20, 22 26

    1972

  30. [42]

    S. Kratsch. Recent developments in kernelization: A survey.Bulletin of the EATCS, 113, 2014. 2

    2014

  31. [43]

    H. W. Lenstra Jr. Integer programming with a fixed number of variables.Math. Oper. Res., 8 (4):538–548, 1983. 2

    1983

  32. [44]

    Lokshtanov

    D. Lokshtanov. Kernelization: An overview. In Proceedings of the 18th International Sym- posium on Fundamentals of Computation Theory (FCT), volume 6914 of Lecture Notes in Computer Science, pages 39–40. Springer, 2011. 2

    2011

  33. [45]

    Lokshtanov, N

    D. Lokshtanov, N. Misra, and S. Saurabh. Kernelization - Preprocessing with a guarantee. In The Multivariate Algorithmic Revolution and Beyond - Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday, volume 7370 of Lecture Notes in Computer Science, pages...

    2012

  34. [46]

    Lokshtanov, F

    D. Lokshtanov, F. Panolan, M. S. Ramanujan, and S. Saurabh. Lossy kernelization. InProceed- ings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 224–237. ACM, 2017. 5

    2017

  35. [47]

    Lokshtanov, P

    D. Lokshtanov, P. Misra, F. Panolan, M. S. Ramanujan, S. Saurabh, and M. Zehavi. Meta- theorems for parameterized streaming algorithms‡. In Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 712–739, 2024. 5

    2024

  36. [48]

    Lokshtanov, P

    D. Lokshtanov, P. Misra, S. Saurabh, and M. Zehavi. Kernelization of counting problems. In Proceeding of the 15th Innovations in Theoretical Computer Science Conference (ITCS), volume 287 ofLIPIcs, pages 77:1–77:23. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,

  37. [49]

    Malik and L

    S. Malik and L. Zhang. Boolean satisfiability from theoretical hardness to practical success. Communications of the ACM, 52(8):76–82, 2009. 2

    2009

  38. [50]

    J. A. Montoya and M. Müller. Parameterized random complexity. Theory of Computing Systems, 52(2):221–270, 2013. 16

    2013

  39. [51]

    A. E. Mouawad, N. Nishimura, V. Raman, N. Simjour, and A. Suzuki. On the parameterized complexity of reconfiguration problems.Algorithmica, 78(1):274–297, 2017. 19, 20, 21, 22

    2017

  40. [52]

    A. E. Mouawad, N. Nishimura, V. Raman, and S. Siebertz. Vertex cover reconfiguration and beyond. Algorithms, 11(2):20, 2018. 19, 22

    2018

  41. [53]

    Niedermeier

    R. Niedermeier. Invitation to Fixed-Parameter Algorithms. Oxford University Press, 2006. 2, 5

    2006

  42. [54]

    Pfandler, S

    A. Pfandler, S. Rümmele, J. P. Wallner, and S. Woltran. On the parameterized complex- ity of belief revision. In Proceedings of the 24h International Joint Conference on Artificial Intelligence (IJCAI), pages 3149–3155. AAAI Press, 2015. 2

    2015

  43. [55]

    van Rooij, M

    I. van Rooij, M. Blokpoel, J. Kwisthout, and T. Wareham.Cognition and intractability: A guide to classical and parameterized complexity analysis. Cambridge University Press, 2019. 2, 5 27

    2019

  44. [56]

    Rutenburg

    V. Rutenburg. Propositional truth maintenance systems: Classification and complexity analy- sis. Annals of Mathematics and Artificial Intelligence, 10(3):207–231, 1994. 16, 17

    1994

  45. [57]

    Saikko, J

    P. Saikko, J. P. Wallner, and M. Järvisalo. Implicit hitting set algorithms for reasoning be- yond NP. In Proceedings of the 15th International Conference on Principles of Knowledge Representation and Reasoning (KR), pages 104–113. AAAI Press, 2016. 2

    2016

  46. [58]

    K. A. Sakallah and J. Marques-Silva. Anatomy and empirical evaluation of modern SAT solvers. Bulletin of the EATCS, 103:96–121, 2011. 2

    2011

  47. [59]

    Schrijver.Theory of linear and integer programming

    A. Schrijver.Theory of linear and integer programming. John Wiley & Sons, 1998. 2

    1998

  48. [60]

    L. J. Stockmeyer. The polynomial-time hierarchy. Theoretical Computer Science, 3(1):1–22,

  49. [61]

    H. A. Taha. Integer programming: theory, applications, and computations. Academic Press,

  50. [62]

    L. A. Wolsey and G. L. Nemhauser.Integer and combinatorial optimization. John Wiley & Sons, 2014. 2 28

    2014

Pith tools

Reviewed August 5, 2026 · model on record in the stance chip above.