TY - GEN
T1 - On listing, sampling, and counting the chordal graphs with edge constraints
AU - Kijima, Shuji
AU - Kiyomi, Masashi
AU - Okamoto, Yoshio
AU - Uno, Takeaki
N1 - Funding Information:
The authors thank the anonymous referee for valuable comments. The authors are supported by Grant-in-Aid for Scientific Research. The third author is also supported by JSPS Global COE Program ‘‘Computationism as a Foundation for the Sciences’’.
PY - 2008
Y1 - 2008
N2 - We discuss the problems to list, sample, and count the chordal graphs with edge constraints. The objects we look at are chordal graphs sandwiched by a given pair of graphs where we assume at least one of the input pair is chordal. The setting is a natural generalization of chordal completions and deletions. For the listing problem, we give an efficient algorithm running in polynomial time per output with polynomial space. As for the sampling problem, we give two clues that seem to imply that a random sampling is not easy. The first clue is that we show #P-completeness results for counting problems. The second clue is that we give an instance for which a natural Markov chain suffers from an exponential mixing time. These results provide a unified viewpoint from algorithms theory to problems arising from various areas such as statistics, data mining, and numerical computation.
AB - We discuss the problems to list, sample, and count the chordal graphs with edge constraints. The objects we look at are chordal graphs sandwiched by a given pair of graphs where we assume at least one of the input pair is chordal. The setting is a natural generalization of chordal completions and deletions. For the listing problem, we give an efficient algorithm running in polynomial time per output with polynomial space. As for the sampling problem, we give two clues that seem to imply that a random sampling is not easy. The first clue is that we show #P-completeness results for counting problems. The second clue is that we give an instance for which a natural Markov chain suffers from an exponential mixing time. These results provide a unified viewpoint from algorithms theory to problems arising from various areas such as statistics, data mining, and numerical computation.
UR - http://www.scopus.com/inward/record.url?scp=48249112899&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=48249112899&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-69733-6_45
DO - 10.1007/978-3-540-69733-6_45
M3 - Conference contribution
AN - SCOPUS:48249112899
SN - 3540697322
SN - 9783540697329
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 458
EP - 467
BT - Computing and Combinatorics - 14th Annual International Conference, COCOON 2008, Proceedings
T2 - 14th Annual International Conference on Computing and Combinatorics, COCOON 2008
Y2 - 27 June 2008 through 29 June 2008
ER -