Counting Kernels in Directed Graphs with Arbitrary Orientations
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2022
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909205585199104 |
|---|---|
| author | Jartoux, Bruno |
| author_facet | Jartoux, Bruno |
| contents | A kernel of a directed graph is a subset of vertices that is both independent and absorbing (every vertex not in the kernel has an out-neighbour in the kernel). Not all directed graphs contain kernels, and computing a kernel or deciding that none exist is NP-complete even on low-degree planar digraphs. The existing polynomial-time algorithms for this problem all restrict both the undirected structure and the edge orientations of the input: for example, to chordal graphs without bidirectional edges (Pass-Lanneau, Igarashi and Meunier, Discrete Appl Math 2020) or to permutation graphs where each clique has a sink (Abbas and Saoula, 4OR 2005). By contrast, we count the kernels of a fuzzy circular interval graph in polynomial time, regardless of its edge orientations, and return a kernel when one exists. (Fuzzy circular graphs were introduced by Chudnovsky and Seymour in their structure theorem for claw-free graphs.) We also consider kernels on cographs, where we establish NP-hardness in general but linear running times on the subclass of threshold graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2202_04476 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Counting Kernels in Directed Graphs with Arbitrary Orientations Jartoux, Bruno Discrete Mathematics Combinatorics 05C69 (Primary) 05C20, 68R10 (Secondary) G.2.2; G.2.1; F.2.2 A kernel of a directed graph is a subset of vertices that is both independent and absorbing (every vertex not in the kernel has an out-neighbour in the kernel). Not all directed graphs contain kernels, and computing a kernel or deciding that none exist is NP-complete even on low-degree planar digraphs. The existing polynomial-time algorithms for this problem all restrict both the undirected structure and the edge orientations of the input: for example, to chordal graphs without bidirectional edges (Pass-Lanneau, Igarashi and Meunier, Discrete Appl Math 2020) or to permutation graphs where each clique has a sink (Abbas and Saoula, 4OR 2005). By contrast, we count the kernels of a fuzzy circular interval graph in polynomial time, regardless of its edge orientations, and return a kernel when one exists. (Fuzzy circular graphs were introduced by Chudnovsky and Seymour in their structure theorem for claw-free graphs.) We also consider kernels on cographs, where we establish NP-hardness in general but linear running times on the subclass of threshold graphs. |
| title | Counting Kernels in Directed Graphs with Arbitrary Orientations |
| topic | Discrete Mathematics Combinatorics 05C69 (Primary) 05C20, 68R10 (Secondary) G.2.2; G.2.1; F.2.2 |
| url | https://arxiv.org/abs/2202.04476 |