A Parameterized Route to Exact Puzzles: Breaking the 2 n -Barrier for Irredundance
Identifieur interne : 001A16 ( Istex/Curation ); précédent : 001A15; suivant : 001A17A Parameterized Route to Exact Puzzles: Breaking the 2 n -Barrier for Irredundance
Auteurs : Daniel Binkele-Raible [Allemagne] ; Ljiljana Brankovic [Australie] ; Henning Fernau [Allemagne] ; Joachim Kneis [Allemagne] ; Dieter Kratsch [France] ; Alexander Langer [Allemagne] ; Mathieu Liedloff [France] ; Peter Rossmanith [Allemagne]Source :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 2010.
Abstract
Abstract: The lower and the upper irredundance numbers of a graph G, denoted ir(G) and IR(G) respectively, are conceptually linked to domination and independence numbers and have numerous relations to other graph parameters. It is a long-standing open question whether determining these numbers for a graph G on n vertices admits exact algorithms running in time less than the trivial Ω(2 n ) enumeration barrier. We solve this open problem by devising parameterized algorithms for the duals of the natural parameterizations of the problems with running times faster than $\mathcal{O}^*(4^{k})$ . For example, we present an algorithm running in time $\mathcal{O}^*(3.069^{k}))$ for determining whether IR(G) is at least n − k. Although the corresponding problem has been shown to be in FPT by kernelization techniques, this paper offers the first parameterized algorithms with an exponential dependency on the parameter in the running time. Furthermore, these seem to be the first examples of a parameterized approach leading to a solution to a problem in exponential time algorithmics where the natural interpretation as exact exponential-time algorithms fails.
Url:
DOI: 10.1007/978-3-642-13073-1_28
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: Pour aller vers cette notice dans l'étape Curation :001B33
Links to Exploration step
ISTEX:D53E1C54122748DE8921D66B3B2ABDDBDB118DD2Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">A Parameterized Route to Exact Puzzles: Breaking the 2 n -Barrier for Irredundance</title>
<author><name sortKey="Binkele Raible, Daniel" sort="Binkele Raible, Daniel" uniqKey="Binkele Raible D" first="Daniel" last="Binkele-Raible">Daniel Binkele-Raible</name>
<affiliation wicri:level="1"><mods:affiliation>FB 4—Abteilung Informatik, Universität Trier, D-54286, Trier, Germany</mods:affiliation>
<country xml:lang="fr">Allemagne</country>
<wicri:regionArea>FB 4—Abteilung Informatik, Universität Trier, D-54286, Trier</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: fernau@uni-trier.de</mods:affiliation>
<country wicri:rule="url">Allemagne</country>
</affiliation>
</author>
<author><name sortKey="Brankovic, Ljiljana" sort="Brankovic, Ljiljana" uniqKey="Brankovic L" first="Ljiljana" last="Brankovic">Ljiljana Brankovic</name>
<affiliation wicri:level="1"><mods:affiliation>The University of Newcastle, University Drive, NSW 2308, Callaghan, Australia</mods:affiliation>
<country xml:lang="fr">Australie</country>
<wicri:regionArea>The University of Newcastle, University Drive, NSW 2308, Callaghan</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: ljiljana.brankovic@newcastle.edu.au</mods:affiliation>
<country wicri:rule="url">Australie</country>
</affiliation>
</author>
<author><name sortKey="Fernau, Henning" sort="Fernau, Henning" uniqKey="Fernau H" first="Henning" last="Fernau">Henning Fernau</name>
<affiliation wicri:level="1"><mods:affiliation>FB 4—Abteilung Informatik, Universität Trier, D-54286, Trier, Germany</mods:affiliation>
<country xml:lang="fr">Allemagne</country>
<wicri:regionArea>FB 4—Abteilung Informatik, Universität Trier, D-54286, Trier</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: raible@uni-trier.de</mods:affiliation>
<country wicri:rule="url">Allemagne</country>
</affiliation>
</author>
<author><name sortKey="Kneis, Joachim" sort="Kneis, Joachim" uniqKey="Kneis J" first="Joachim" last="Kneis">Joachim Kneis</name>
<affiliation wicri:level="1"><mods:affiliation>Department of Computer Science, RWTH Aachen University, Germany</mods:affiliation>
<country xml:lang="fr">Allemagne</country>
<wicri:regionArea>Department of Computer Science, RWTH Aachen University</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: kneis@cs.rwth-aachen.de</mods:affiliation>
<country wicri:rule="url">Allemagne</country>
</affiliation>
</author>
<author><name sortKey="Kratsch, Dieter" sort="Kratsch, Dieter" uniqKey="Kratsch D" first="Dieter" last="Kratsch">Dieter Kratsch</name>
<affiliation wicri:level="1"><mods:affiliation>Laboratoire d’Informatique Théorique et Appliquée, Université Paul Verlaine - Metz, 57045, Metz Cedex 01, France</mods:affiliation>
<country xml:lang="fr">France</country>
<wicri:regionArea>Laboratoire d’Informatique Théorique et Appliquée, Université Paul Verlaine - Metz, 57045, Metz Cedex 01</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: kratsch@univ-metz.fr</mods:affiliation>
<country wicri:rule="url">France</country>
</affiliation>
</author>
<author><name sortKey="Langer, Alexander" sort="Langer, Alexander" uniqKey="Langer A" first="Alexander" last="Langer">Alexander Langer</name>
<affiliation wicri:level="1"><mods:affiliation>Department of Computer Science, RWTH Aachen University, Germany</mods:affiliation>
<country xml:lang="fr">Allemagne</country>
<wicri:regionArea>Department of Computer Science, RWTH Aachen University</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: langer@cs.rwth-aachen.de</mods:affiliation>
<country wicri:rule="url">Allemagne</country>
</affiliation>
</author>
<author><name sortKey="Liedloff, Mathieu" sort="Liedloff, Mathieu" uniqKey="Liedloff M" first="Mathieu" last="Liedloff">Mathieu Liedloff</name>
<affiliation wicri:level="1"><mods:affiliation>Laboratoire d’Informatique Fondamentale d’Orléans, Université d’Orléans, 45067, Orléans Cedex 2, France</mods:affiliation>
<country xml:lang="fr">France</country>
<wicri:regionArea>Laboratoire d’Informatique Fondamentale d’Orléans, Université d’Orléans, 45067, Orléans Cedex 2</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: liedloff@univ-orleans.fr</mods:affiliation>
<country wicri:rule="url">France</country>
</affiliation>
</author>
<author><name sortKey="Rossmanith, Peter" sort="Rossmanith, Peter" uniqKey="Rossmanith P" first="Peter" last="Rossmanith">Peter Rossmanith</name>
<affiliation wicri:level="1"><mods:affiliation>Department of Computer Science, RWTH Aachen University, Germany</mods:affiliation>
<country xml:lang="fr">Allemagne</country>
<wicri:regionArea>Department of Computer Science, RWTH Aachen University</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: rossmani@cs.rwth-aachen.de</mods:affiliation>
<country wicri:rule="url">Allemagne</country>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">ISTEX</idno>
<idno type="RBID">ISTEX:D53E1C54122748DE8921D66B3B2ABDDBDB118DD2</idno>
<date when="2010" year="2010">2010</date>
<idno type="doi">10.1007/978-3-642-13073-1_28</idno>
<idno type="url">https://api.istex.fr/document/D53E1C54122748DE8921D66B3B2ABDDBDB118DD2/fulltext/pdf</idno>
<idno type="wicri:Area/Istex/Corpus">001B33</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001B33</idno>
<idno type="wicri:Area/Istex/Curation">001A16</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">A Parameterized Route to Exact Puzzles: Breaking the 2 n -Barrier for Irredundance</title>
<author><name sortKey="Binkele Raible, Daniel" sort="Binkele Raible, Daniel" uniqKey="Binkele Raible D" first="Daniel" last="Binkele-Raible">Daniel Binkele-Raible</name>
<affiliation wicri:level="1"><mods:affiliation>FB 4—Abteilung Informatik, Universität Trier, D-54286, Trier, Germany</mods:affiliation>
<country xml:lang="fr">Allemagne</country>
<wicri:regionArea>FB 4—Abteilung Informatik, Universität Trier, D-54286, Trier</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: fernau@uni-trier.de</mods:affiliation>
<country wicri:rule="url">Allemagne</country>
</affiliation>
</author>
<author><name sortKey="Brankovic, Ljiljana" sort="Brankovic, Ljiljana" uniqKey="Brankovic L" first="Ljiljana" last="Brankovic">Ljiljana Brankovic</name>
<affiliation wicri:level="1"><mods:affiliation>The University of Newcastle, University Drive, NSW 2308, Callaghan, Australia</mods:affiliation>
<country xml:lang="fr">Australie</country>
<wicri:regionArea>The University of Newcastle, University Drive, NSW 2308, Callaghan</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: ljiljana.brankovic@newcastle.edu.au</mods:affiliation>
<country wicri:rule="url">Australie</country>
</affiliation>
</author>
<author><name sortKey="Fernau, Henning" sort="Fernau, Henning" uniqKey="Fernau H" first="Henning" last="Fernau">Henning Fernau</name>
<affiliation wicri:level="1"><mods:affiliation>FB 4—Abteilung Informatik, Universität Trier, D-54286, Trier, Germany</mods:affiliation>
<country xml:lang="fr">Allemagne</country>
<wicri:regionArea>FB 4—Abteilung Informatik, Universität Trier, D-54286, Trier</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: raible@uni-trier.de</mods:affiliation>
<country wicri:rule="url">Allemagne</country>
</affiliation>
</author>
<author><name sortKey="Kneis, Joachim" sort="Kneis, Joachim" uniqKey="Kneis J" first="Joachim" last="Kneis">Joachim Kneis</name>
<affiliation wicri:level="1"><mods:affiliation>Department of Computer Science, RWTH Aachen University, Germany</mods:affiliation>
<country xml:lang="fr">Allemagne</country>
<wicri:regionArea>Department of Computer Science, RWTH Aachen University</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: kneis@cs.rwth-aachen.de</mods:affiliation>
<country wicri:rule="url">Allemagne</country>
</affiliation>
</author>
<author><name sortKey="Kratsch, Dieter" sort="Kratsch, Dieter" uniqKey="Kratsch D" first="Dieter" last="Kratsch">Dieter Kratsch</name>
<affiliation wicri:level="1"><mods:affiliation>Laboratoire d’Informatique Théorique et Appliquée, Université Paul Verlaine - Metz, 57045, Metz Cedex 01, France</mods:affiliation>
<country xml:lang="fr">France</country>
<wicri:regionArea>Laboratoire d’Informatique Théorique et Appliquée, Université Paul Verlaine - Metz, 57045, Metz Cedex 01</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: kratsch@univ-metz.fr</mods:affiliation>
<country wicri:rule="url">France</country>
</affiliation>
</author>
<author><name sortKey="Langer, Alexander" sort="Langer, Alexander" uniqKey="Langer A" first="Alexander" last="Langer">Alexander Langer</name>
<affiliation wicri:level="1"><mods:affiliation>Department of Computer Science, RWTH Aachen University, Germany</mods:affiliation>
<country xml:lang="fr">Allemagne</country>
<wicri:regionArea>Department of Computer Science, RWTH Aachen University</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: langer@cs.rwth-aachen.de</mods:affiliation>
<country wicri:rule="url">Allemagne</country>
</affiliation>
</author>
<author><name sortKey="Liedloff, Mathieu" sort="Liedloff, Mathieu" uniqKey="Liedloff M" first="Mathieu" last="Liedloff">Mathieu Liedloff</name>
<affiliation wicri:level="1"><mods:affiliation>Laboratoire d’Informatique Fondamentale d’Orléans, Université d’Orléans, 45067, Orléans Cedex 2, France</mods:affiliation>
<country xml:lang="fr">France</country>
<wicri:regionArea>Laboratoire d’Informatique Fondamentale d’Orléans, Université d’Orléans, 45067, Orléans Cedex 2</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: liedloff@univ-orleans.fr</mods:affiliation>
<country wicri:rule="url">France</country>
</affiliation>
</author>
<author><name sortKey="Rossmanith, Peter" sort="Rossmanith, Peter" uniqKey="Rossmanith P" first="Peter" last="Rossmanith">Peter Rossmanith</name>
<affiliation wicri:level="1"><mods:affiliation>Department of Computer Science, RWTH Aachen University, Germany</mods:affiliation>
<country xml:lang="fr">Allemagne</country>
<wicri:regionArea>Department of Computer Science, RWTH Aachen University</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: rossmani@cs.rwth-aachen.de</mods:affiliation>
<country wicri:rule="url">Allemagne</country>
</affiliation>
</author>
</analytic>
<monogr></monogr>
<series><title level="s">Lecture Notes in Computer Science</title>
<imprint><date>2010</date>
</imprint>
<idno type="ISSN">0302-9743</idno>
<idno type="eISSN">1611-3349</idno>
<idno type="ISSN">0302-9743</idno>
</series>
<idno type="istex">D53E1C54122748DE8921D66B3B2ABDDBDB118DD2</idno>
<idno type="DOI">10.1007/978-3-642-13073-1_28</idno>
<idno type="ChapterID">28</idno>
<idno type="ChapterID">Chap28</idno>
</biblStruct>
</sourceDesc>
<seriesStmt><idno type="ISSN">0302-9743</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass></textClass>
<langUsage><language ident="en">en</language>
</langUsage>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Abstract: The lower and the upper irredundance numbers of a graph G, denoted ir(G) and IR(G) respectively, are conceptually linked to domination and independence numbers and have numerous relations to other graph parameters. It is a long-standing open question whether determining these numbers for a graph G on n vertices admits exact algorithms running in time less than the trivial Ω(2 n ) enumeration barrier. We solve this open problem by devising parameterized algorithms for the duals of the natural parameterizations of the problems with running times faster than $\mathcal{O}^*(4^{k})$ . For example, we present an algorithm running in time $\mathcal{O}^*(3.069^{k}))$ for determining whether IR(G) is at least n − k. Although the corresponding problem has been shown to be in FPT by kernelization techniques, this paper offers the first parameterized algorithms with an exponential dependency on the parameter in the running time. Furthermore, these seem to be the first examples of a parameterized approach leading to a solution to a problem in exponential time algorithmics where the natural interpretation as exact exponential-time algorithms fails.</div>
</front>
</TEI>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/Istex/Curation
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001A16 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Curation/biblio.hfd -nk 001A16 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Wicri/Rhénanie |area= UnivTrevesV1 |flux= Istex |étape= Curation |type= RBID |clé= ISTEX:D53E1C54122748DE8921D66B3B2ABDDBDB118DD2 |texte= A Parameterized Route to Exact Puzzles: Breaking the 2 n -Barrier for Irredundance }}
![]() | This area was generated with Dilib version V0.6.31. | ![]() |