Counting 4 × 4 matrix partitions of graphs
Given a symmetric matrix M ∈ {0, 1, ∗}D×D, an M-partition of a graph G is a function from V (G) to D such that no edge of G is mapped to a 0 of M and no non-edge to a 1. We give a computer-assisted proof that, when |D| = 4, the problem of counting the M-partitions of an input graph is either in FP o...
| Hauptverfasser: | , , |
|---|---|
| Format: | Journal article |
| Veröffentlicht: |
Elsevier
2016
|
| _version_ | 1826265239388160000 |
|---|---|
| author | Dyer, M Goldberg, L Richerby, D |
| author_facet | Dyer, M Goldberg, L Richerby, D |
| author_sort | Dyer, M |
| collection | OXFORD |
| description | Given a symmetric matrix M ∈ {0, 1, ∗}D×D, an M-partition of a graph G is a function from V (G) to D such that no edge of G is mapped to a 0 of M and no non-edge to a 1. We give a computer-assisted proof that, when |D| = 4, the problem of counting the M-partitions of an input graph is either in FP or is #P-complete. Tractability is proved by reduction to the related problem of counting list M-partitions; intractability is shown using a gadget construction and interpolation. We use a computer program to determine which of the two cases holds for all but a small number of matrices, which we resolve manually to establish the dichotomy. We conjecture that the dichotomy also holds for |D| > 4. More specifically, we conjecture that, for any symmetric matrix M ∈ {0, 1, ∗}D×D, the complexity of counting M-partitions is the same as the related problem of counting list M-partitions. |
| first_indexed | 2024-03-06T20:20:33Z |
| format | Journal article |
| id | oxford-uuid:2da5e909-8c95-4158-ac29-c4c8b3947e16 |
| institution | University of Oxford |
| last_indexed | 2024-03-06T20:20:33Z |
| publishDate | 2016 |
| publisher | Elsevier |
| record_format | dspace |
| spelling | oxford-uuid:2da5e909-8c95-4158-ac29-c4c8b3947e162022-03-26T12:44:10ZCounting 4 × 4 matrix partitions of graphsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:2da5e909-8c95-4158-ac29-c4c8b3947e16Symplectic Elements at OxfordElsevier2016Dyer, MGoldberg, LRicherby, DGiven a symmetric matrix M ∈ {0, 1, ∗}D×D, an M-partition of a graph G is a function from V (G) to D such that no edge of G is mapped to a 0 of M and no non-edge to a 1. We give a computer-assisted proof that, when |D| = 4, the problem of counting the M-partitions of an input graph is either in FP or is #P-complete. Tractability is proved by reduction to the related problem of counting list M-partitions; intractability is shown using a gadget construction and interpolation. We use a computer program to determine which of the two cases holds for all but a small number of matrices, which we resolve manually to establish the dichotomy. We conjecture that the dichotomy also holds for |D| > 4. More specifically, we conjecture that, for any symmetric matrix M ∈ {0, 1, ∗}D×D, the complexity of counting M-partitions is the same as the related problem of counting list M-partitions. |
| spellingShingle | Dyer, M Goldberg, L Richerby, D Counting 4 × 4 matrix partitions of graphs |
| title | Counting 4 × 4 matrix partitions of graphs |
| title_full | Counting 4 × 4 matrix partitions of graphs |
| title_fullStr | Counting 4 × 4 matrix partitions of graphs |
| title_full_unstemmed | Counting 4 × 4 matrix partitions of graphs |
| title_short | Counting 4 × 4 matrix partitions of graphs |
| title_sort | counting 4 4 matrix partitions of graphs |
| work_keys_str_mv | AT dyerm counting44matrixpartitionsofgraphs AT goldbergl counting44matrixpartitionsofgraphs AT richerbyd counting44matrixpartitionsofgraphs |