|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'928
Articles rated: 2609
25 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Counting list matrix partitions of graphs | | Andreas Göbel
; Leslie Ann Goldberg
; Colin McQuillan
; David Richerby
; Tomoyuki Yamakami
; | | Date: |
21 Jun 2013 | | Abstract: | A list M-partition of a graph G is associated with a symmetric D-by-D matrix
over {0,1,*}. It is a partition of the vertices of G into D parts which are
associated with the rows of M. The part of each vertex is chosen from a given
list in such a way that no edge of G is mapped to a 0 in M and no non-edge of G
is mapped to a 1. Many important graph-theoretic structures can be represented
as list M-partitions including graph colourings, split graphs and homogeneous
sets. Thus, there has been quite a bit of work on determining for which
matrices computations involving list M-partitions are tractable. This paper
focuses on the problem of counting list M-partitions, given a graph G and given
lists for each vertex of G. We give an algorithm that solves this problem in
polynomial time for every (fixed) matrix M for which the problem is tractable.
Thus, we identify the tractable cases. The algorithm relies on data structures
such as sparse-dense partitions and subcube decompositions to reduce each
problem instance to a sequence of problem instances in which the lists have a
certain useful structure that restricts access to portions of M in which the
interactions of 0s and 1s is controlled. We show how to solve the resulting
restricted instances by converting them into particular counting constraint
satisfaction problems (#CSPs) which we show how to solve using a constraint
satisfaction technique known as "arc-consistency". For every matrix M for which
our algorithm fails, we show that the problem of counting list M-partitions is
#P-complete. Furthermore, we give an explicit characterisation of the dichotomy
theorem - counting list M-partitions is tractable (in FP) if and only if the
matrix M has a structure called a derectangularising sequence. Finally, we show
that the meta-problem of determining whether a given matrix has a
derectangularising sequence is NP-complete. | | Source: | arXiv, 1306.5176 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER