On the complexity of finding large odd induced subgraphs and odd colorings

Autor: Rémy Belmonte, Ignasi Sau
Přispěvatelé: University of Electro-Communications [Tokyo] (UEC), 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), Work supported by French projects DEMOGRAPH (ANR-16-CE40-0028), ESIGMA (ANR-17-CE23-0010), and ELIT (ANR-20-CE48-0008-01), the program 'Exploration Japon 2017' of the French embassy in Japan, and the JSPS KAKENHI grant number JP18K11157., ANR-16-CE40-0028,DE-MO-GRAPH,Décomposition de Modèles Graphiques(2016), ANR-17-CE23-0010,ESIGMA,Efficacité et structure pour les applications de la fouille de graphes(2017), ANR-19-CE48-0008,CIAO,Cryptographie, isogenies et variété abéliennes surpuissantes(2019), ANR-20-CE48-0008,ELIT,Un Parcours par les Limites de l'Efficacité(2020)
Jazyk: angličtina
Rok vydání: 2020
Předmět:
odd subgraph
single-exponential algorithm
General Computer Science
0211 other engineering and technologies
Induced subgraph
Parameterized complexity
0102 computer and information sciences
02 engineering and technology
G.2.2
odd coloring
rank-width
01 natural sciences
Combinatorics
Mathematics::Probability
Computer Science - Data Structures and Algorithms
0202 electrical engineering
electronic engineering
information engineering
Partition (number theory)
Mathematics - Combinatorics
[MATH]Mathematics [math]
Exponential Time Hypothesis
parameterized complexity
Physics
Exponential time hypothesis
Applied Mathematics
021107 urban & regional planning
020206 networking & telecommunications
Graph
Computer Science Applications
Mathematics::Logic
Computer Science - Computational Complexity
05C15
010201 computation theory & mathematics
F.2.2
Zdroj: Algorithmica
Algorithmica, Springer Verlag, 2021, 83 (8), pp.2351-2373. ⟨10.1007/s00453-021-00830-x⟩
Graph-Theoretic Concepts in Computer Science 46th International Workshop, WG 2020, Leeds, UK, June 24–26, 2020, Revised Selected Papers
46th International Workshop on Graph-Theoretic Concepts in Computer Science (WG)
46th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), Jun 2020, Leeds, United Kingdom. pp.67-79, ⟨10.1007/978-3-030-60440-0_6⟩
Graph-Theoretic Concepts in Computer Science ISBN: 9783030604394
WG
ISSN: 0178-4617
1432-0541
DOI: 10.1007/s00453-021-00830-x⟩
Popis: We study the complexity of the problems of finding, given a graph $G$, a largest induced subgraph of $G$ with all degrees odd (called an odd subgraph), and the smallest number of odd subgraphs that partition $V(G)$. We call these parameters ${\sf mos}(G)$ and $\chi_{{\sf odd}}(G)$, respectively. We prove that deciding whether $\chi_{{\sf odd}}(G) \leq q$ is polynomial-time solvable if $q \leq 2$, and NP-complete otherwise. We provide algorithms in time $2^{O({\sf rw})} \cdot n^{O(1)}$ and $2^{O(q \cdot {\sf rw})} \cdot n^{O(1)}$ to compute ${\sf mos}(G)$ and to decide whether $\chi_{{\sf odd}}(G) \leq q$ on $n$-vertex graphs of rank-width at most ${\sf rw}$, respectively, and we prove that the dependency on rank-width is asymptotically optimal under the ETH. Finally, we give some tight bounds for these parameters on restricted graph classes or in relation to other parameters.
Comment: 24 pages, 8 figures
Databáze: OpenAIRE
Externí odkaz: