Combinatorial game theory foundations applied to digraph kernels
Summary: Known complexity facts: the decision problem of the existence of a kernel in a digraph \(G=(V,E)\) is NP-complete; if all of the cycles of \(G\) have even length, then \(G\) has a kernel; and the question of the number of kernels is \(\#\)P-complete even for this restricted class of digraphs. In the opposite direction, we construct game theory tools, of independent interest, concerning strategies in the presence of draw positions, to show how to partition \(V\), in \(O(|E|)\) time, into \(3\) subsets \(S_1,S_2,S_3\) such that \(S_1\) lies in all the kernels; \(S_2\) lies in the complements of all the kernels; and on \(S_3\) the kernels may be nonunique. Thus, in particular, digraphs with a ``large number of kernels are those in which \(S_3\) is ``large; possibly \(S_1=S_2=\varnothing\). We also show that \(G\) can be decomposed, in \(O(|E|)\) time, into two induced subgraphs \(G_1\), with vertex-set \(S_1\cup S_2\), which has a unique kernel; and \(G_2\), with vertex-set \(S_3\), such that any kernel \(K\) of \(G\) is the union of the kernel of \(G_1\) and a kernel of \(G_2\). In particular, \(G\) has no kernel if and only if \(G_2\) has none. Our results hold even for some classes of infinite digraphs.
- Enumerating the kernels of a directed graph with no odd circuits
- Even kernels
- On variants of vertex geography on undirected graphs
- Kernels in directed graphs: A poison game
- Indepth combinatorial analysis of admissible sets for abstract argumentation
- Choices and kernels in bipolar valued digraphs
- Kernels in planar digraphs
- On the existence of \((k,l)\)-kernels in infinite digraphs: a survey
- A framework for data mining on combinatorial game theory
- scientific article; zbMATH DE number 3865312 (Why is no real title available?)
- scientific article; zbMATH DE number 3891402 (Why is no real title available?)
- Characterization of asymmetric CKI- and KP-digraphs with covering number at most 3
- Expressive power of digraph solvability
- scientific article; zbMATH DE number 1124608 (Why is no real title available?)
- Kernels in digraphs that are not kernel perfect
- Inductive kernels of graphs
- H-absorbence and H-independence in 3-quasi-transitive H-coloured digraphs.
- On kernels in strongly game-perfect digraphs and a characterisation of weakly game-perfect digraphs
- Kernels by monochromatic paths in digraphs with covering number 2
- Counting kernels in directed graphs with arbitrary orientations
- (k,H)-kernels in nearly tournaments
- The theorem of Richardson and its generalizations: a survey
- Argumentation frameworks, games and kernels: time for a family Reunion!
This page was built for publication: Combinatorial game theory foundations applied to digraph kernels
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1378531)
