Back to Search
Start Over
On the Complexity of Finding Large Odd Induced Subgraphs and Odd Colorings.
- Source :
-
Algorithmica . Aug2021, Vol. 83 Issue 8, p2351-2373. 23p. - Publication Year :
- 2021
-
Abstract
- 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 mos (G) and χ odd (G) , respectively. We prove that deciding whether χ odd (G) ≤ q is polynomial-time solvable if q ≤ 2 , and NP-complete otherwise. We provide algorithms in time 2 O (rw) · n O (1) and 2 O (q · rw) · n O (1) to compute mos (G) and to decide whether χ odd (G) ≤ q on n-vertex graphs of rank-width at most 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. [ABSTRACT FROM AUTHOR]
- Subjects :
- *SUBGRAPHS
*ODD numbers
*ALGORITHMS
Subjects
Details
- Language :
- English
- ISSN :
- 01784617
- Volume :
- 83
- Issue :
- 8
- Database :
- Academic Search Index
- Journal :
- Algorithmica
- Publication Type :
- Academic Journal
- Accession number :
- 151526925
- Full Text :
- https://doi.org/10.1007/s00453-021-00830-x