Scholarlink

<p>The computational complexity of the graph isomorphism problem is considered to be a major open problem in theoretical computer science. It is known that testing isomorphism of chordal graphs is polynomial-time equivalent to the general graph isomorphism problem. Every chordal graph can be represented as the intersection graph of some subtrees of a representing tree, and the leafage of a chordal graph is defined to be the minimum number of leaves in a representing tree for it. We prove that chordal graph isomorphism is fixed parameter tractable with leafage as parameter. In the process, we introduce the problem of isomorphism testing for higher-order hypergraphs and show that finding the automorphism group of an order-<InlineEquation ID="IEq1"> <EquationSource Format="TEX">\({k}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi>k</mi> </math></EquationSource> </InlineEquation> hypergraph of size <i>s</i> with vertex color classes of size at most <i>b</i> can be done in time <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\((b!\,s)^{O(k)}\)</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mrow> <mo stretchy="false">(</mo> <mi>b</mi> <mo>!</mo> <mspace width="0.166667em" /> <mi>s</mi> <mo stretchy="false">)</mo> </mrow> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mi>k</mi> <mo stretchy="false">)</mo> </mrow> </msup> </math></EquationSource> </InlineEquation>.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Testing Isomorphism of Chordal Graphs of Bounded Leafage is Fixed-Parameter Tractable

  • 期刊论文

  • 发表日期：

    2026年3月17日

查看全文
  • Vikraman Arvind,
  • Roman Nedela,
  • Ilia Ponomarenko,
  • Peter Zeman

摘要

The computational complexity of the graph isomorphism problem is considered to be a major open problem in theoretical computer science. It is known that testing isomorphism of chordal graphs is polynomial-time equivalent to the general graph isomorphism problem. Every chordal graph can be represented as the intersection graph of some subtrees of a representing tree, and the leafage of a chordal graph is defined to be the minimum number of leaves in a representing tree for it. We prove that chordal graph isomorphism is fixed parameter tractable with leafage as parameter. In the process, we introduce the problem of isomorphism testing for higher-order hypergraphs and show that finding the automorphism group of an order- \({k}\) k hypergraph of size s with vertex color classes of size at most b can be done in time \((b!\,s)^{O(k)}\) ( b ! s ) O ( k ) .