<?xml version="1.0" encoding="utf-8"?>
<TEI xmlns="http://www.tei-c.org/ns/1.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:hal="http://hal.archives-ouvertes.fr/" xmlns:gml="http://www.opengis.net/gml/3.3/" xmlns:gmlce="http://www.opengis.net/gml/3.3/ce" version="1.1" xsi:schemaLocation="http://www.tei-c.org/ns/1.0 http://api.archives-ouvertes.fr/documents/aofr-sword.xsd">
  <teiHeader>
    <fileDesc>
      <titleStmt>
        <title>HAL TEI export of lirmm-03991247</title>
      </titleStmt>
      <publicationStmt>
        <distributor>CCSD</distributor>
        <availability status="restricted">
          <licence target="https://creativecommons.org/publicdomain/zero/1.0/">CC0 1.0 - Universal</licence>
        </availability>
        <date when="2026-05-22T14:58:32+02:00"/>
      </publicationStmt>
      <sourceDesc>
        <p part="N">HAL API Platform</p>
      </sourceDesc>
    </fileDesc>
  </teiHeader>
  <text>
    <body>
      <listBibl>
        <biblFull>
          <titleStmt>
            <title xml:lang="en">Introducing lop-Kernels: A Framework for Kernelization Lower Bounds</title>
            <author role="aut">
              <persName>
                <forename type="first">Júlio</forename>
                <surname>Araújo</surname>
              </persName>
              <email type="md5">d1208d849ab2bd42b39badab68028045</email>
              <email type="domain">sophia.inria.fr</email>
              <idno type="idhal" notation="numeric">1227556</idno>
              <idno type="halauthorid" notation="string">2058899-1227556</idno>
              <idno type="ORCID">https://orcid.org/0000-0001-7074-2753</idno>
              <affiliation ref="#struct-117182"/>
            </author>
            <author role="aut">
              <persName>
                <forename type="first">Marin</forename>
                <surname>Bougeret</surname>
              </persName>
              <email type="md5">866ea4828811774358e36f187ffc2c9c</email>
              <email type="domain">imag.fr</email>
              <idno type="idhal" notation="string">marin-bougeret</idno>
              <idno type="idhal" notation="numeric">10167</idno>
              <idno type="halauthorid" notation="string">17678-10167</idno>
              <idno type="ORCID">https://orcid.org/0000-0002-9910-4656</idno>
              <idno type="IDREF">https://www.idref.fr/197511686</idno>
              <affiliation ref="#struct-1100628"/>
            </author>
            <author role="aut">
              <persName>
                <forename type="first">Victor</forename>
                <surname>Campos</surname>
              </persName>
              <idno type="idhal" notation="numeric">1227557</idno>
              <idno type="halauthorid" notation="string">450907-1227557</idno>
              <idno type="ORCID">https://orcid.org/0000-0002-2730-4640</idno>
              <affiliation ref="#struct-117182"/>
            </author>
            <author role="aut">
              <persName>
                <forename type="first">Ignasi</forename>
                <surname>Sau</surname>
              </persName>
              <email type="md5">0cf496e357a0f831666492fefcf2203b</email>
              <email type="domain">gmail.com</email>
              <idno type="idhal" notation="string">ignasi-sau</idno>
              <idno type="idhal" notation="numeric">7331</idno>
              <idno type="halauthorid" notation="string">2727823-7331</idno>
              <idno type="ORCID">https://orcid.org/0000-0002-8981-9287</idno>
              <idno type="IDREF">https://www.idref.fr/137767420</idno>
              <affiliation ref="#struct-1100628"/>
            </author>
            <editor role="depositor">
              <persName>
                <forename>Cathy</forename>
                <surname>Tuchming</surname>
              </persName>
              <email type="md5">e0c2c835abeebdc0d858ec4887082bbc</email>
              <email type="domain">lirmm.fr</email>
            </editor>
            <funder ref="#projanr-42363"/>
            <funder ref="#projanr-43303"/>
            <funder ref="#projanr-51748"/>
            <funder ref="#projanr-51688"/>
            <funder>Júlio Araújo: CNPq-Pq 304478/2018-0, CAPES-PrInt 88887.466468/2019-00 and CAPES-STIC-AmSud 88881.569474/2020-01.Victor Campos: FUNCAP - PNE-011200061.01.00/16.</funder>
          </titleStmt>
          <editionStmt>
            <edition n="v1" type="current">
              <date type="whenSubmitted">2023-10-17 12:10:35</date>
              <date type="whenModified">2025-12-02 03:04:06</date>
              <date type="whenReleased">2025-01-14 11:12:38</date>
              <date type="whenProduced">2022-11</date>
              <ref type="externalLink" target="http://arxiv.org/pdf/2102.02484"/>
            </edition>
            <respStmt>
              <resp>contributor</resp>
              <name key="103115">
                <persName>
                  <forename>Cathy</forename>
                  <surname>Tuchming</surname>
                </persName>
                <email type="md5">e0c2c835abeebdc0d858ec4887082bbc</email>
                <email type="domain">lirmm.fr</email>
              </name>
            </respStmt>
          </editionStmt>
          <publicationStmt>
            <distributor>CCSD</distributor>
            <idno type="halId">lirmm-03991247</idno>
            <idno type="halUri">https://hal-lirmm.ccsd.cnrs.fr/lirmm-03991247</idno>
            <idno type="halBibtex">araujo:lirmm-03991247</idno>
            <idno type="halRefHtml">&lt;i&gt;Algorithmica&lt;/i&gt;, 2022, 84 (11), pp.3365-3406. &lt;a target="_blank" href="https://dx.doi.org/10.1007/s00453-022-00979-z"&gt;&amp;#x27E8;10.1007/s00453-022-00979-z&amp;#x27E9;&lt;/a&gt;</idno>
            <idno type="halRef">Algorithmica, 2022, 84 (11), pp.3365-3406. &amp;#x27E8;10.1007/s00453-022-00979-z&amp;#x27E9;</idno>
            <availability status="restricted"/>
          </publicationStmt>
          <seriesStmt>
            <idno type="stamp" n="CNRS">CNRS - Centre national de la recherche scientifique</idno>
            <idno type="stamp" n="UNIV-MONTP3">Université de Montpellier Paul-Valéry</idno>
            <idno type="stamp" n="UNIV-PERP">Université Perpignan Via Domitia</idno>
            <idno type="stamp" n="ALGCO" corresp="LIRMM">Algorithmes, Graphes et Combinatoire</idno>
            <idno type="stamp" n="LIRMM">Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier</idno>
            <idno type="stamp" n="UNIV-MONTPELLIER">Université de Montpellier</idno>
            <idno type="stamp" n="ANR">ANR</idno>
            <idno type="stamp" n="UM-2015-2021" corresp="UNIV-MONTPELLIER">Université de Montpellier (2015-2021)</idno>
            <idno type="stamp" n="UM-EPE" corresp="UNIV-MONTPELLIER">Université de Montpellier - EPE</idno>
          </seriesStmt>
          <notesStmt>
            <note type="audience" n="2">International</note>
            <note type="popular" n="0">No</note>
            <note type="peer" n="1">Yes</note>
          </notesStmt>
          <sourceDesc>
            <biblStruct>
              <analytic>
                <title xml:lang="en">Introducing lop-Kernels: A Framework for Kernelization Lower Bounds</title>
                <author role="aut">
                  <persName>
                    <forename type="first">Júlio</forename>
                    <surname>Araújo</surname>
                  </persName>
                  <email type="md5">d1208d849ab2bd42b39badab68028045</email>
                  <email type="domain">sophia.inria.fr</email>
                  <idno type="idhal" notation="numeric">1227556</idno>
                  <idno type="halauthorid" notation="string">2058899-1227556</idno>
                  <idno type="ORCID">https://orcid.org/0000-0001-7074-2753</idno>
                  <affiliation ref="#struct-117182"/>
                </author>
                <author role="aut">
                  <persName>
                    <forename type="first">Marin</forename>
                    <surname>Bougeret</surname>
                  </persName>
                  <email type="md5">866ea4828811774358e36f187ffc2c9c</email>
                  <email type="domain">imag.fr</email>
                  <idno type="idhal" notation="string">marin-bougeret</idno>
                  <idno type="idhal" notation="numeric">10167</idno>
                  <idno type="halauthorid" notation="string">17678-10167</idno>
                  <idno type="ORCID">https://orcid.org/0000-0002-9910-4656</idno>
                  <idno type="IDREF">https://www.idref.fr/197511686</idno>
                  <affiliation ref="#struct-1100628"/>
                </author>
                <author role="aut">
                  <persName>
                    <forename type="first">Victor</forename>
                    <surname>Campos</surname>
                  </persName>
                  <idno type="idhal" notation="numeric">1227557</idno>
                  <idno type="halauthorid" notation="string">450907-1227557</idno>
                  <idno type="ORCID">https://orcid.org/0000-0002-2730-4640</idno>
                  <affiliation ref="#struct-117182"/>
                </author>
                <author role="aut">
                  <persName>
                    <forename type="first">Ignasi</forename>
                    <surname>Sau</surname>
                  </persName>
                  <email type="md5">0cf496e357a0f831666492fefcf2203b</email>
                  <email type="domain">gmail.com</email>
                  <idno type="idhal" notation="string">ignasi-sau</idno>
                  <idno type="idhal" notation="numeric">7331</idno>
                  <idno type="halauthorid" notation="string">2727823-7331</idno>
                  <idno type="ORCID">https://orcid.org/0000-0002-8981-9287</idno>
                  <idno type="IDREF">https://www.idref.fr/137767420</idno>
                  <affiliation ref="#struct-1100628"/>
                </author>
              </analytic>
              <monogr>
                <idno type="halJournalId" status="VALID">10334</idno>
                <idno type="issn">0178-4617</idno>
                <idno type="eissn">1432-0541</idno>
                <title level="j">Algorithmica</title>
                <imprint>
                  <publisher>Springer Verlag</publisher>
                  <biblScope unit="volume">84</biblScope>
                  <biblScope unit="issue">11</biblScope>
                  <biblScope unit="pp">3365-3406</biblScope>
                  <date type="datePub">2022-11</date>
                </imprint>
              </monogr>
              <idno type="arxiv">2102.02484</idno>
              <idno type="doi">10.1007/s00453-022-00979-z</idno>
            </biblStruct>
          </sourceDesc>
          <profileDesc>
            <langUsage>
              <language ident="en">English</language>
            </langUsage>
            <textClass>
              <keywords scheme="author">
                <term xml:lang="en">Parameterized complexity</term>
                <term xml:lang="en">Kernelization lower bound</term>
                <term xml:lang="en">Maximum minimal vertex cover</term>
                <term xml:lang="en">Erdős–Hajnal property</term>
                <term xml:lang="en">Induced subgraphs</term>
                <term xml:lang="en">Polynomial kernel</term>
              </keywords>
              <classCode scheme="halDomain" n="info.info-ds">Computer Science [cs]/Data Structures and Algorithms [cs.DS]</classCode>
              <classCode scheme="halTypology" n="ART">Journal articles</classCode>
              <classCode scheme="halOldTypology" n="ART">Journal articles</classCode>
              <classCode scheme="halTreeTypology" n="ART">Journal articles</classCode>
            </textClass>
            <abstract xml:lang="en">
              <p>In the Maximum Minimal Vertex Cover (MMVC) problem, we are given a graph G and a positive integer k, and the objective is to decide whether G contains a minimal vertex cover of size at least k. Motivated by the kernelization of MMVC with parameter k, our main contribution is to introduce a simple general framework to obtain kernelization lower bounds for a certain type of kernels for optimization problems, which we call lop-kernels. Informally, this type of kernels is required to preserve large optimal solutions in the reduced instance, and captures the vast majority of existing kernels in the literature.As a consequence of this framework, we show that the trivial quadratic kernel for MMVC is essentially optimal, answering a question of Boria et al. [Discret. Appl. Math. 2015], and that the known cubic kernel for Maximum Minimal Feedback Vertex Set is also essentially optimal. We present further applications for Tree Deletion Set and for Maximum Independent Set on Kt-free graphs.Back to the MMVC problem, given the (plausible) non-existence of subquadratic kernels for MMVC on general graphs, we provide subquadratic kernels on H-free graphs for several graphs H, such as the bull, the paw, or the complete graphs, by making use of the Erdős-Hajnal property. Finally, we prove that MMVC does not admit polynomial kernels parameterized by the size of a minimum vertex cover of the input graph, even on bipartite graphs, unless NP ⊆ coNP/poly.</p>
            </abstract>
          </profileDesc>
        </biblFull>
      </listBibl>
    </body>
    <back>
      <listOrg type="structures">
        <org type="institution" xml:id="struct-117182" status="VALID">
          <idno type="ISNI">0000 0001 2160 0329</idno>
          <idno type="ROR">https://ror.org/03srtnf24</idno>
          <orgName>Universidade Federal do Ceará = Federal University of Ceará</orgName>
          <orgName type="acronym">UFC</orgName>
          <desc>
            <address>
              <addrLine>Av. da Universidade, 2853 - Benfica, Fortaleza - CE, CEP 60020-181</addrLine>
              <country key="BR"/>
            </address>
            <ref type="url">http://www.ufc.br/</ref>
          </desc>
        </org>
        <org type="researchteam" xml:id="struct-1100628" status="VALID">
          <orgName>Algorithmes, Graphes et Combinatoire</orgName>
          <orgName type="acronym">LIRMM | ALGCO</orgName>
          <date type="start">2022-01-01</date>
          <desc>
            <address>
              <addrLine>LIRMM, 161 rue Ada, 34000 Montpellier</addrLine>
              <country key="FR"/>
            </address>
            <ref type="url">https://www.lirmm.fr/equipes/ALGCO/</ref>
          </desc>
          <listRelation>
            <relation active="#struct-1100620" type="direct"/>
            <relation active="#struct-101475" type="indirect"/>
            <relation active="#struct-300009" type="indirect"/>
            <relation name="UMR5506" active="#struct-441569" type="indirect"/>
            <relation name="UMR5506" active="#struct-1100589" type="indirect"/>
            <relation active="#struct-1219853" type="indirect"/>
          </listRelation>
        </org>
        <org type="laboratory" xml:id="struct-1100620" status="VALID">
          <idno type="IdRef">139590827</idno>
          <idno type="ISNI">0000000405990488</idno>
          <idno type="RNSR">199111950H</idno>
          <idno type="ROR">https://ror.org/013yean28</idno>
          <orgName>Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier</orgName>
          <orgName type="acronym">LIRMM</orgName>
          <date type="start">2022-01-01</date>
          <desc>
            <address>
              <addrLine>161 rue Ada - 34095 Montpellier</addrLine>
              <country key="FR"/>
            </address>
            <ref type="url">https://www.lirmm.fr</ref>
          </desc>
          <listRelation>
            <relation active="#struct-101475" type="direct"/>
            <relation active="#struct-300009" type="direct"/>
            <relation name="UMR5506" active="#struct-441569" type="direct"/>
            <relation name="UMR5506" active="#struct-1100589" type="direct"/>
            <relation active="#struct-1219853" type="direct"/>
          </listRelation>
        </org>
        <org type="institution" xml:id="struct-101475" status="VALID">
          <idno type="ROR">https://ror.org/03am2jy38</idno>
          <orgName>Université de Perpignan Via Domitia</orgName>
          <orgName type="acronym">UPVD</orgName>
          <desc>
            <address>
              <addrLine>52 avenue Paul Alduy - 66860 Perpignan Cedex 9</addrLine>
              <country key="FR"/>
            </address>
            <ref type="url">http://www.univ-perp.fr/</ref>
          </desc>
        </org>
        <org type="institution" xml:id="struct-300009" status="VALID">
          <idno type="ROR">https://ror.org/02kvxyf05</idno>
          <orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
          <orgName type="acronym">Inria</orgName>
          <desc>
            <address>
              <addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
              <country key="FR"/>
            </address>
            <ref type="url">http://www.inria.fr/en/</ref>
          </desc>
        </org>
        <org type="regroupinstitution" xml:id="struct-441569" status="VALID">
          <idno type="IdRef">02636817X</idno>
          <idno type="ISNI">0000000122597504</idno>
          <idno type="ROR">https://ror.org/02feahw73</idno>
          <orgName>Centre National de la Recherche Scientifique</orgName>
          <orgName type="acronym">CNRS</orgName>
          <date type="start">1939-10-19</date>
          <desc>
            <address>
              <country key="FR"/>
            </address>
            <ref type="url">https://www.cnrs.fr/</ref>
          </desc>
        </org>
        <org type="regroupinstitution" xml:id="struct-1100589" status="VALID">
          <idno type="ROR">https://ror.org/051escj72</idno>
          <orgName>Université de Montpellier</orgName>
          <orgName type="acronym">UM</orgName>
          <date type="start">2022-01-01</date>
          <desc>
            <address>
              <addrLine>163 rue Auguste Broussonnet - 34090 Montpellier</addrLine>
              <country key="FR"/>
            </address>
            <ref type="url">http://www.umontpellier.fr/</ref>
          </desc>
        </org>
        <org type="regroupinstitution" xml:id="struct-1219853" status="VALID">
          <idno type="IdRef">282217916</idno>
          <orgName>Université de Montpellier Paul-Valéry</orgName>
          <orgName type="acronym">UMPV</orgName>
          <date type="start">2025-01-01</date>
          <desc>
            <address>
              <addrLine>Université de Montpellier Paul-Valéry Route de Mende 34199 Montpellier Cedex 5</addrLine>
              <country key="FR"/>
            </address>
            <ref type="url">https://www.univ-montp3.fr/fr</ref>
          </desc>
        </org>
      </listOrg>
      <listOrg type="projects">
        <org type="anrProject" xml:id="projanr-42363" status="VALID">
          <idno type="anr">ANR-16-CE40-0028</idno>
          <orgName>DE-MO-GRAPH</orgName>
          <desc>Décomposition de Modèles Graphiques</desc>
          <date type="start">2016</date>
        </org>
        <org type="anrProject" xml:id="projanr-43303" status="VALID">
          <idno type="anr">ANR-17-CE23-0010</idno>
          <orgName>ESIGMA</orgName>
          <desc>Efficacité et structure pour les applications de la fouille de graphes</desc>
          <date type="start">2017</date>
        </org>
        <org type="anrProject" xml:id="projanr-51748" status="VALID">
          <idno type="anr">ANR-20-CE48-0008</idno>
          <orgName>ELIT</orgName>
          <desc>Un Parcours par les Limites de l'Efficacité</desc>
          <date type="start">2020</date>
        </org>
        <org type="anrProject" xml:id="projanr-51688" status="VALID">
          <idno type="anr">ANR-20-CE92-0027</idno>
          <orgName>UTMA</orgName>
          <desc>Théories Unifiantes dans les Algorithmes Multivarieés</desc>
          <date type="start">2020</date>
        </org>
      </listOrg>
    </back>
  </text>
</TEI>