Search

Your search keyword '"W[1]-hard"' showing total 2 results
Start Over Descriptor "W[1]-hard" Publisher hal ccsd
2 results on '"W[1]-hard"'

1. On the Parameterized Complexity of Relaxations of Clique

Author

Baril, Ambroise, Castillon, Antoine, Oijid, Nacim, Knowledge representation, reasonning (ORPAILLEUR), Department of Natural Language Processing & Knowledge Discovery (LORIA - NLPKD), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Graphes, AlgOrithmes et AppLications (GOAL), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS), Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon, Liris, Loria, CRIStAL, Knowledge representation, reasonning [ORPAILLEUR], Graphes, AlgOrithmes et AppLications [GOAL], Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL], Laboratoire d'InfoRmatique en Image et Systèmes d'information [LIRIS], and Université Claude Bernard Lyon 1 [UCBL]

Subjects
clique, W[1]-hard, γ-complete subgraph, [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], s-club, complexity, s-clique, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
Abstract

We investigate the parameterized complexity of several problems formalizing cluster identification in graphs. In other words we ask whether a graph contains a large enough and sufficiently connected subgraph. We study here three relaxations of Clique: s-Club and s-Clique, in which the relaxation is focused on the distances in respectively the cluster and the original graph, and γ-Complete Subgraph in which the relaxation is made on the minimal degree in the cluster. As these three problems are known to be NP-hard, we study here their parameterized complexities. We prove that s-Club and s-Clique are NP-hard even restricted to graphs of degeneracy ≤ 3 whenever s ≥ 3, and to graphs of degeneracy ≤ 2 whenever s ≥ 5, which is a strictly stronger result than its W[1]-hardness parameterized by the degeneracy. We also obtain that these problems are solvable in polynomial time on graphs of degeneracy 1. Concerning γ-Complete Subgraph, we prove that it is W[1]-hard parameterized by both the degeneracy, which implies the W[1]-hardness parameterized by the number of vertices in the γ-complete-subgraph, and the number of elements outside the γ-complete subgraph.

Published
2023

2. Ruling out FPT algorithms for Weighted Coloring on forests

Author

Júlio Araújo, Julien Baste, Ignasi Sau, Universidade Federal do Ceará = Federal University of Ceará (UFC), Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), ANR-16-CE40-0028,DE-MO-GRAPH,Décomposition de Modèles Graphiques(2016), Universidade Federal do Ceará ( UFC ), Algorithmes, Graphes et Combinatoire ( ALGCO ), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier ( LIRMM ), and Université de Montpellier ( UM ) -Centre National de la Recherche Scientifique ( CNRS ) -Université de Montpellier ( UM ) -Centre National de la Recherche Scientifique ( CNRS )

Subjects
FOS: Computer and information sciences, [ MATH ] Mathematics [math], Weight function, General Computer Science, Minimum weight, Parameterized complexity, 0102 computer and information sciences, 02 engineering and technology, G.2.2, Computational Complexity (cs.CC), 01 natural sciences, Theoretical Computer Science, Combinatorics, W[1]-hard, 020204 information systems, Computer Science - Data Structures and Algorithms, FOS: Mathematics, 0202 electrical engineering, electronic engineering, information engineering, Discrete Mathematics and Combinatorics, Partition (number theory), Mathematics - Combinatorics, Data Structures and Algorithms (cs.DS), [MATH]Mathematics [math], ComputingMilieux_MISCELLANEOUS, Mathematics, parameterized complexity, Connected component, Discrete mathematics, forests, Exponential time hypothesis, Applied Mathematics, 05 social sciences, max-coloring, 050301 education, F.2.2, Graph, Computer Science - Computational Complexity, 05C15, 010201 computation theory & mathematics, Combinatorics (math.CO), weighted coloring, 0503 education, Algorithm
Abstract

Given a graph $G$, a proper $k$-coloring of $G$ is a partition $c = (S_i)_{i\in [1,k]}$ of $V(G)$ into $k$ stable sets $S_1,\ldots, S_{k}$. Given a weight function $w: V(G) \to \mathbb{R}^+$, the weight of a color $S_i$ is defined as $w(i) = \max_{v \in S_i} w(v)$ and the weight of a coloring $c$ as $w(c) = \sum_{i=1}^{k}w(i)$. Guan and Zhu [Inf. Process. Lett., 1997] defined the weighted chromatic number of a pair $(G,w)$, denoted by $\sigma(G,w)$, as the minimum weight of a proper coloring of $G$. For a positive integer $r$, they also defined $\sigma(G,w;r)$ as the minimum of $w(c)$ among all proper $r$-colorings $c$ of $G$. The complexity of determining $\sigma(G,w)$ when $G$ is a tree was open for almost 20 years, until Ara\'ujo et al. [SIAM J. Discrete Math., 2014] recently proved that the problem cannot be solved in time $n^{o(\log n)}$ on $n$-vertex trees unless the Exponential Time Hypothesis (ETH) fails. The objective of this article is to provide hardness results for computing $\sigma(G,w)$ and $\sigma(G,w;r)$ when $G$ is a tree or a forest, relying on complexity assumptions weaker than the ETH. Namely, we study the problem from the viewpoint of parameterized complexity, and we assume the weaker hypothesis $FPT \neq W[1]$. Building on the techniques of Ara\'ujo et al., we prove that when $G$ is a forest, computing $\sigma(G,w)$ is $W[1]$-hard parameterized by the size of a largest connected component of $G$, and that computing $\sigma(G,w;r)$ is $W[2]$-hard parameterized by $r$. Our results rule out the existence of $FPT$ algorithms for computing these invariants on trees or forests for many natural choices of the parameter., Comment: 14 pages, 4 figures

Published
2018
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results