Parameterized Complexity of Independent Set in H-Free Graphs

Autor: Édouard Bonnet, Pierre Charbit, Rémi Watrigant, Nicolas Bousquet, Stéphan Thomassé
Přispěvatelé: Centre National de la Recherche Scientifique (CNRS), Université de Lyon, Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), École normale supérieure - Lyon (ENS Lyon), Modèles de calcul, Complexité, Combinatoire (MC2), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Optimisation Combinatoire (G-SCOP_OC ), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Networks, Graphs and Algorithms (GANG), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Institut Universitaire de France (IUF), Ministère de l'Education nationale, de l’Enseignement supérieur et de la Recherche (M.E.N.E.S.R.), Université Claude Bernard Lyon 1 (UCBL), ANR-10-LABX-0070,MILYON,Community of mathematics and fundamental computer science in Lyon(2010), ANR-17-CE40-0015,DISTANCIA,Théorie métrique des graphes(2017), Optimisation Combinatoire (G-SCOP_OC), Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA), Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA)-Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA)-Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité), École normale supérieure de Lyon (ENS de Lyon), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), OC (G-SCOP_OC), Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP)-Institut National Polytechnique de Grenoble (INPG)-Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP)-Institut National Polytechnique de Grenoble (INPG)-Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS), ANR-11-IDEX-0007-02/10-LABX-0070,MILYON,Community of mathematics and fundamental computer science in Lyon(2011)
Jazyk: angličtina
Rok vydání: 2018
Předmět:
FOS: Computer and information sciences
Polynomial
General Computer Science
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]
Induced subgraph
Parameterized complexity
0102 computer and information sciences
02 engineering and technology
Computational Complexity (cs.CC)
[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
01 natural sciences
Combinatorics
Computer Science - Data Structures and Algorithms
0202 electrical engineering
electronic engineering
information engineering
Data Structures and Algorithms (cs.DS)
[MATH]Mathematics [math]
Finite set
ComputingMilieux_MISCELLANEOUS
Mathematics
Disjoint union
000 Computer science
knowledge
general works
H-Free Graphs
Parameterized Algorithms
Applied Mathematics
Independent Set
Parametrized complexity
16. Peace & justice
Computer Science Applications
Computer Science - Computational Complexity
010201 computation theory & mathematics
Independent set
Theory of computation
Computer Science
Iterative compression
020201 artificial intelligence & image processing
MathematicsofComputing_DISCRETEMATHEMATICS
Zdroj: IPEC 2018-13th International Symposium on Parameterized and Exact Computation
IPEC 2018-13th International Symposium on Parameterized and Exact Computation, Aug 2018, Helsinki, Finland. ⟨10.4230/LIPIcs.CVIT.2016.23⟩
Algorithmica
Algorithmica, Springer Verlag, 2020, 82 (8), pp.2360-2394. ⟨10.1007/s00453-020-00730-6⟩
Algorithmica, Springer Verlag, 2020, Parameterized and Exact Computation, IPEC 2018, 82 (8), pp.2360-2394. ⟨10.1007/s00453-020-00730-6⟩
Algorithmica, 2020, Parameterized and Exact Computation, IPEC 2018, 82 (8), pp.2360-2394. ⟨10.1007/s00453-020-00730-6⟩
ISSN: 0178-4617
1432-0541
DOI: 10.4230/LIPIcs.CVIT.2016.23⟩
Popis: In this paper, we investigate the complexity of Maximum Independent Set (MIS) in the class of $H$-free graphs, that is, graphs excluding a fixed graph as an induced subgraph. Given that the problem remains $NP$-hard for most graphs $H$, we study its fixed-parameter tractability and make progress towards a dichotomy between $FPT$ and $W[1]$-hard cases. We first show that MIS remains $W[1]$-hard in graphs forbidding simultaneously $K_{1, 4}$, any finite set of cycles of length at least $4$, and any finite set of trees with at least two branching vertices. In particular, this answers an open question of Dabrowski et al. concerning $C_4$-free graphs. Then we extend the polynomial algorithm of Alekseev when $H$ is a disjoint union of edges to an $FPT$ algorithm when $H$ is a disjoint union of cliques. We also provide a framework for solving several other cases, which is a generalization of the concept of \emph{iterative expansion} accompanied by the extraction of a particular structure using Ramsey's theorem. Iterative expansion is a maximization version of the so-called \emph{iterative compression}. We believe that our framework can be of independent interest for solving other similar graph problems. Finally, we present positive and negative results on the existence of polynomial (Turing) kernels for several graphs $H$.
An extended abstract appeared in the proceedings of IPEC 2018
Databáze: OpenAIRE
Externí odkaz: