Combinatorial game theory foundations applied to digraph kernels (Q1378531): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Latest revision as of 04:08, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Combinatorial game theory foundations applied to digraph kernels |
scientific article |
Statements
Combinatorial game theory foundations applied to digraph kernels (English)
0 references
15 February 1998
0 references
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.
0 references