<?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-01610076</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-03T22:15:00+02:00"/>
      </publicationStmt>
      <sourceDesc>
        <p part="N">HAL API Platform</p>
      </sourceDesc>
    </fileDesc>
  </teiHeader>
  <text>
    <body>
      <listBibl>
        <biblFull>
          <titleStmt>
            <title xml:lang="en">Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes</title>
            <author role="aut">
              <persName>
                <forename type="first">Archontia C.</forename>
                <surname>Giannopoulou</surname>
              </persName>
              <idno type="halauthorid">699445-0</idno>
              <affiliation ref="#struct-129314"/>
            </author>
            <author role="aut">
              <persName>
                <forename type="first">Michal</forename>
                <surname>Pilipczuk</surname>
              </persName>
              <email type="md5">033f8d0581183322474c3ded2b539696</email>
              <email type="domain">mimuw.edu.pl</email>
              <idno type="idhal" notation="numeric">779066</idno>
              <idno type="halauthorid" notation="string">1246896-779066</idno>
              <idno type="ORCID">https://orcid.org/0000-0001-7891-1988</idno>
              <idno type="IDREF">https://www.idref.fr/238380246</idno>
              <idno type="VIAF">https://viaf.org/viaf/7876157342853810100002</idno>
              <affiliation ref="#struct-87510"/>
            </author>
            <author role="aut">
              <persName>
                <forename type="first">Jean-Florent</forename>
                <surname>Raymond</surname>
              </persName>
              <email type="md5">068ff8662a7205e7840203f9f710b6c0</email>
              <email type="domain">cnrs.fr</email>
              <idno type="idhal" notation="string">jean-florent-raymond</idno>
              <idno type="idhal" notation="numeric">3527</idno>
              <idno type="halauthorid" notation="string">19698-3527</idno>
              <idno type="ORCID">https://orcid.org/0000-0003-4646-7602</idno>
              <idno type="IDREF">https://www.idref.fr/226798283</idno>
              <affiliation ref="#struct-388229"/>
            </author>
            <author role="aut">
              <persName>
                <forename type="first">Dimitrios M.</forename>
                <surname>Thilikos</surname>
              </persName>
              <email type="md5">b12f47ffd4c78cdb273f5b91bb335a0e</email>
              <email type="domain">thilikos.Info</email>
              <idno type="idhal" notation="string">dimitrios-m-thilikos</idno>
              <idno type="idhal" notation="numeric">178742</idno>
              <idno type="halauthorid" notation="string">17649-178742</idno>
              <idno type="ORCID">https://orcid.org/0000-0003-0470-1800</idno>
              <idno type="IDREF">https://www.idref.fr/149337078</idno>
              <affiliation ref="#struct-425861"/>
              <affiliation ref="#struct-388229"/>
            </author>
            <author role="aut">
              <persName>
                <forename type="first">Marcin</forename>
                <surname>Wrochna</surname>
              </persName>
              <idno type="halauthorid">1061167-0</idno>
              <affiliation ref="#struct-87510"/>
            </author>
            <editor role="depositor">
              <persName>
                <forename>Jean-Florent</forename>
                <surname>Raymond</surname>
              </persName>
              <email type="md5">068ff8662a7205e7840203f9f710b6c0</email>
              <email type="domain">cnrs.fr</email>
            </editor>
            <funder ref="#projanr-42363"/>
          </titleStmt>
          <editionStmt>
            <edition n="v1" type="current">
              <date type="whenSubmitted">2017-10-04 12:55:27</date>
              <date type="whenModified">2025-02-16 22:58:10</date>
              <date type="whenReleased">2017-10-06 11:35:51</date>
              <date type="whenProduced">2017-07-10</date>
              <date type="whenEndEmbargoed">2017-10-04</date>
              <ref type="file" target="https://hal-lirmm.ccsd.cnrs.fr/lirmm-01610076v1/document">
                <date notBefore="2017-10-04"/>
              </ref>
              <ref type="file" subtype="author" n="1" target="https://hal-lirmm.ccsd.cnrs.fr/lirmm-01610076v1/file/LIPIcs-ICALP-2017-57.pdf" id="file-1610076-1652879">
                <date notBefore="2017-10-04"/>
              </ref>
            </edition>
            <respStmt>
              <resp>contributor</resp>
              <name key="312581">
                <persName>
                  <forename>Jean-Florent</forename>
                  <surname>Raymond</surname>
                </persName>
                <email type="md5">068ff8662a7205e7840203f9f710b6c0</email>
                <email type="domain">cnrs.fr</email>
              </name>
            </respStmt>
          </editionStmt>
          <publicationStmt>
            <distributor>CCSD</distributor>
            <idno type="halId">lirmm-01610076</idno>
            <idno type="halUri">https://hal-lirmm.ccsd.cnrs.fr/lirmm-01610076</idno>
            <idno type="halBibtex">giannopoulou:lirmm-01610076</idno>
            <idno type="halRefHtml">&lt;i&gt;ICALP: International Colloquium on Automata, Languages, and Programming&lt;/i&gt;, Jul 2017, Varsovie, Poland. pp.1-15, &lt;a target="_blank" href="https://dx.doi.org/10.4230/LIPIcs.ICALP.2017.57"&gt;&amp;#x27E8;10.4230/LIPIcs.ICALP.2017.57&amp;#x27E9;&lt;/a&gt;</idno>
            <idno type="halRef">ICALP: International Colloquium on Automata, Languages, and Programming, Jul 2017, Varsovie, Poland. pp.1-15, &amp;#x27E8;10.4230/LIPIcs.ICALP.2017.57&amp;#x27E9;</idno>
            <availability status="restricted">
              <licence target="https://creativecommons.org/licenses/by/4.0/">CC BY 4.0 - Attribution<ref corresp="#file-1610076-1652879"/></licence>
            </availability>
          </publicationStmt>
          <seriesStmt>
            <idno type="stamp" n="CNRS">CNRS - Centre national de la recherche scientifique</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="MIPS">Mathématiques, Informatique, Physique et Systèmes</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>
          </seriesStmt>
          <notesStmt>
            <note type="audience" n="2">International</note>
            <note type="invited" n="0">No</note>
            <note type="popular" n="0">No</note>
            <note type="peer" n="1">Yes</note>
            <note type="proceedings" n="1">Yes</note>
          </notesStmt>
          <sourceDesc>
            <biblStruct>
              <analytic>
                <title xml:lang="en">Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes</title>
                <author role="aut">
                  <persName>
                    <forename type="first">Archontia C.</forename>
                    <surname>Giannopoulou</surname>
                  </persName>
                  <idno type="halauthorid">699445-0</idno>
                  <affiliation ref="#struct-129314"/>
                </author>
                <author role="aut">
                  <persName>
                    <forename type="first">Michal</forename>
                    <surname>Pilipczuk</surname>
                  </persName>
                  <email type="md5">033f8d0581183322474c3ded2b539696</email>
                  <email type="domain">mimuw.edu.pl</email>
                  <idno type="idhal" notation="numeric">779066</idno>
                  <idno type="halauthorid" notation="string">1246896-779066</idno>
                  <idno type="ORCID">https://orcid.org/0000-0001-7891-1988</idno>
                  <idno type="IDREF">https://www.idref.fr/238380246</idno>
                  <idno type="VIAF">https://viaf.org/viaf/7876157342853810100002</idno>
                  <affiliation ref="#struct-87510"/>
                </author>
                <author role="aut">
                  <persName>
                    <forename type="first">Jean-Florent</forename>
                    <surname>Raymond</surname>
                  </persName>
                  <email type="md5">068ff8662a7205e7840203f9f710b6c0</email>
                  <email type="domain">cnrs.fr</email>
                  <idno type="idhal" notation="string">jean-florent-raymond</idno>
                  <idno type="idhal" notation="numeric">3527</idno>
                  <idno type="halauthorid" notation="string">19698-3527</idno>
                  <idno type="ORCID">https://orcid.org/0000-0003-4646-7602</idno>
                  <idno type="IDREF">https://www.idref.fr/226798283</idno>
                  <affiliation ref="#struct-388229"/>
                </author>
                <author role="aut">
                  <persName>
                    <forename type="first">Dimitrios M.</forename>
                    <surname>Thilikos</surname>
                  </persName>
                  <email type="md5">b12f47ffd4c78cdb273f5b91bb335a0e</email>
                  <email type="domain">thilikos.Info</email>
                  <idno type="idhal" notation="string">dimitrios-m-thilikos</idno>
                  <idno type="idhal" notation="numeric">178742</idno>
                  <idno type="halauthorid" notation="string">17649-178742</idno>
                  <idno type="ORCID">https://orcid.org/0000-0003-0470-1800</idno>
                  <idno type="IDREF">https://www.idref.fr/149337078</idno>
                  <affiliation ref="#struct-425861"/>
                  <affiliation ref="#struct-388229"/>
                </author>
                <author role="aut">
                  <persName>
                    <forename type="first">Marcin</forename>
                    <surname>Wrochna</surname>
                  </persName>
                  <idno type="halauthorid">1061167-0</idno>
                  <affiliation ref="#struct-87510"/>
                </author>
              </analytic>
              <monogr>
                <title level="m">44th International Colloquium on Automata, Languages, and Programming</title>
                <meeting>
                  <title>ICALP: International Colloquium on Automata, Languages, and Programming</title>
                  <date type="start">2017-07-10</date>
                  <settlement>Varsovie</settlement>
                  <country key="PL">Poland</country>
                </meeting>
                <imprint>
                  <biblScope unit="serie">Leibniz International Proceedings in Informatics (LIPIcs)</biblScope>
                  <biblScope unit="volume">80</biblScope>
                  <biblScope unit="issue">57</biblScope>
                  <biblScope unit="pp">1-15</biblScope>
                  <date type="datePub">2017</date>
                </imprint>
              </monogr>
              <idno type="doi">10.4230/LIPIcs.ICALP.2017.57</idno>
            </biblStruct>
          </sourceDesc>
          <profileDesc>
            <langUsage>
              <language ident="en">English</language>
            </langUsage>
            <textClass>
              <classCode scheme="halDomain" n="info.info-ds">Computer Science [cs]/Data Structures and Algorithms [cs.DS]</classCode>
              <classCode scheme="halTypology" n="COMM">Conference papers</classCode>
              <classCode scheme="halOldTypology" n="COMM">Conference papers</classCode>
              <classCode scheme="halTreeTypology" n="COMM">Conference papers</classCode>
            </textClass>
            <abstract xml:lang="en">
              <p>Suppose F is a finite family of graphs. We consider the following meta-problem, called F-Immersion Deletion: given a graph G and an integer k, decide whether the deletion of at most k edges of G can result in a graph that does not contain any graph from F as an immersion. This problem is a close relative of the F-Minor Deletion problem studied by Fomin et al. [FOCS 2012], where one deletes vertices in order to remove all minor models of graphs from F. We prove that whenever all graphs from F are connected and at least one graph of F is planar and subcubic, then the F-Immersion Deletion problem admits: a constant-factor approximation algorithm running in time O(m 3 · n 3 · log m); a linear kernel that can be computed in time O(m 4 · n 3 · log m); and a O(2 O(k) + m 4 · n 3 · log m)-time fixed-parameter algorithm, where n, m count the vertices and edges of the input graph. Our findings mirror those of Fomin et al. [FOCS 2012], who obtained similar results for F-Minor Deletion, under the assumption that at least one graph from F is planar. An important difference is that we are able to obtain a linear kernel for F-Immersion Deletion, while the exponent of the kernel of Fomin et al. depends heavily on the family F. In fact, this dependence is unavoidable under plausible complexity assumptions, as proven by Giannopoulou et al. [ICALP 2015]. This reveals that the kernelization complexity of F-Immersion Deletion is quite different than that of F-Minor Deletion.</p>
            </abstract>
          </profileDesc>
        </biblFull>
      </listBibl>
    </body>
    <back>
      <listOrg type="structures">
        <org type="department" xml:id="struct-129314" status="VALID">
          <orgName>Institut für Softwaretechnik und Theoretische Informatik [EECS-TUB]</orgName>
          <desc>
            <address>
              <addrLine>Sekr. FR6-1, Franklinstr. 28-29, 10587 Berlin</addrLine>
              <country key="DE"/>
            </address>
            <ref type="url">http://www.eecs.tu-berlin.de/menue/einrichtungen/institute/isti/</ref>
          </desc>
          <listRelation>
            <relation active="#struct-467192" type="direct"/>
            <relation active="#struct-86624" type="indirect"/>
          </listRelation>
        </org>
        <org type="regrouplaboratory" xml:id="struct-87510" status="VALID">
          <orgName>Faculty of Mathematics, Informatics, and Mechanics [Warsaw]</orgName>
          <orgName type="acronym">MIMUW</orgName>
          <desc>
            <address>
              <addrLine>Banacha 2, 02-097 Warsaw</addrLine>
              <country key="PL"/>
            </address>
            <ref type="url">http://www.mimuw.edu.pl/</ref>
          </desc>
          <listRelation>
            <relation active="#struct-531382" type="direct"/>
          </listRelation>
        </org>
        <org type="researchteam" xml:id="struct-388229" status="OLD">
          <orgName>Algorithmes, Graphes et Combinatoire</orgName>
          <orgName type="acronym">ALGCO</orgName>
          <date type="end">2021-12-31</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-181" type="direct"/>
            <relation name="UMR5506" active="#struct-410122" type="indirect"/>
            <relation name="UMR5506" active="#struct-441569" type="indirect"/>
          </listRelation>
        </org>
        <org type="department" xml:id="struct-425861" status="VALID">
          <orgName>Department of Mathematics [Athens]</orgName>
          <desc>
            <address>
              <addrLine>Panepistimioupolis, GR-157 84, Athens</addrLine>
              <country key="GR"/>
            </address>
            <ref type="url">http://noether.math.uoa.gr/</ref>
          </desc>
          <listRelation>
            <relation active="#struct-502478" type="direct"/>
          </listRelation>
        </org>
        <org type="laboratory" xml:id="struct-467192" status="VALID">
          <orgName>Fakultät Elektrotechnik und Informatik [TUB]</orgName>
          <desc>
            <address>
              <addrLine>Berlin</addrLine>
              <country key="DE"/>
            </address>
            <ref type="url">http://www.eecs.tu-berlin.de/</ref>
          </desc>
          <listRelation>
            <relation active="#struct-86624" type="direct"/>
          </listRelation>
        </org>
        <org type="institution" xml:id="struct-86624" status="VALID">
          <idno type="ROR">https://ror.org/03v4gjf40</idno>
          <orgName>Technical University of Berlin / Technische Universität Berlin</orgName>
          <orgName type="acronym">TUB</orgName>
          <date type="start">1946-01-01</date>
          <desc>
            <address>
              <addrLine>Straße des 17. Juni 135 10623 Berlin</addrLine>
              <country key="DE"/>
            </address>
            <ref type="url">https://www.tu.berlin/</ref>
          </desc>
        </org>
        <org type="institution" xml:id="struct-531382" status="VALID">
          <idno type="IdRef">026414554</idno>
          <idno type="ISNI">0000000419371290</idno>
          <idno type="ROR">https://ror.org/039bjqg32</idno>
          <idno type="Wikidata">Q144488</idno>
          <orgName>Uniwersytet Warszawski  [Polska] = University of Warsaw [Poland] = Université de Varsovie [Pologne]</orgName>
          <orgName type="acronym">UW</orgName>
          <date type="start">1816-01-01</date>
          <desc>
            <address>
              <addrLine>Krakowskie Przedmieście 26/28 – 00-927 – Warszawa – Pologne</addrLine>
              <country key="PL"/>
            </address>
            <ref type="url">https://www.uw.edu.pl/</ref>
          </desc>
        </org>
        <org type="laboratory" xml:id="struct-181" status="OLD">
          <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">1995-01-01</date>
          <date type="end">2021-12-31</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 name="UMR5506" active="#struct-410122" type="direct"/>
            <relation name="UMR5506" active="#struct-441569" type="direct"/>
          </listRelation>
        </org>
        <org type="institution" xml:id="struct-410122" status="OLD">
          <idno type="ISNI">0000000120970141</idno>
          <idno type="ROR">https://ror.org/051escj72</idno>
          <orgName>Université de Montpellier</orgName>
          <orgName type="acronym">UM</orgName>
          <date type="end">2021-12-31</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-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-502478" status="VALID">
          <idno type="ROR">https://ror.org/04gnjpq42</idno>
          <orgName>National and Kapodistrian University of Athens</orgName>
          <orgName type="acronym">NKUA</orgName>
          <date type="start">1837-04-14</date>
          <desc>
            <address>
              <addrLine>Athens 157 72</addrLine>
              <country key="GR"/>
            </address>
            <ref type="url">https://en.uoa.gr/</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>
      </listOrg>
    </back>
  </text>
</TEI>