Polynomial Time Learnability of Graph Pattern Languages Defined by Cographs

Takayoshi SHOUDAI; Yuta YOSHIMURA; Yusuke SUZUKI; Tomoyuki UCHIDA; Tetsuhiro MIYAHARA

doi:10.1587/transinf.2017FCP0005

Polynomial Time Learnability of Graph Pattern Languages Defined by Cographs

Takayoshi SHOUDAI, Yuta YOSHIMURA, Yusuke SUZUKI, Tomoyuki UCHIDA, Tetsuhiro MIYAHARA

Full Text Views

0

Share
Cite this

Summary :

A cograph (complement reducible graph) is a graph which can be generated by disjoint union and complement operations on graphs, starting with a single vertex graph. Cographs arise in many areas of computer science and are studied extensively. With the goal of developing an effective data mining method for graph structured data, in this paper we introduce a graph pattern expression, called a cograph pattern, which is a special type of cograph having structured variables. Firstly, we show that a problem whether or not a given cograph pattern g matches a given cograph G is NP-complete. From this result, we consider the polynomial time learnability of cograph pattern languages defined by cograph patterns having variables labeled with mutually different labels, called linear cograph patterns. Secondly, we present a polynomial time matching algorithm for linear cograph patterns. Next, we give a polynomial time algorithm for obtaining a minimally generalized linear cograph pattern which explains given positive data. Finally, we show that the class of linear cograph pattern languages is polynomial time inductively inferable from positive data.

Publication: IEICE TRANSACTIONS on Information Vol.E101-D No.3 pp.582-592

Publication Date: 2018/03/01

Publicized: 2017/12/19

Online ISSN: 1745-1361

DOI: 10.1587/transinf.2017FCP0005

Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science — Frontiers of Theoretical Computer Science —)

Category

Authors

Takayoshi SHOUDAI
  Kyushu International University
Yuta YOSHIMURA
  Kyushu University
Yusuke SUZUKI
  Hiroshima City University
Tomoyuki UCHIDA
  Hiroshima City University
Tetsuhiro MIYAHARA
  Hiroshima City University

Keyword

graph pattern matching, cograph pattern, polynomial time algorithm, inductive inference, computational learning theory

Cite this

Copy

Takayoshi SHOUDAI, Yuta YOSHIMURA, Yusuke SUZUKI, Tomoyuki UCHIDA, Tetsuhiro MIYAHARA, "Polynomial Time Learnability of Graph Pattern Languages Defined by Cographs" in IEICE TRANSACTIONS on Information, vol. E101-D, no. 3, pp. 582-592, March 2018, doi: 10.1587/transinf.2017FCP0005.
Abstract: A cograph (complement reducible graph) is a graph which can be generated by disjoint union and complement operations on graphs, starting with a single vertex graph. Cographs arise in many areas of computer science and are studied extensively. With the goal of developing an effective data mining method for graph structured data, in this paper we introduce a graph pattern expression, called a cograph pattern, which is a special type of cograph having structured variables. Firstly, we show that a problem whether or not a given cograph pattern g matches a given cograph G is NP-complete. From this result, we consider the polynomial time learnability of cograph pattern languages defined by cograph patterns having variables labeled with mutually different labels, called linear cograph patterns. Secondly, we present a polynomial time matching algorithm for linear cograph patterns. Next, we give a polynomial time algorithm for obtaining a minimally generalized linear cograph pattern which explains given positive data. Finally, we show that the class of linear cograph pattern languages is polynomial time inductively inferable from positive data.
URL: https://globals.ieice.org/en_transactions/information/10.1587/transinf.2017FCP0005/_p

Copy

@ARTICLE{e101-d_3_582,
author={Takayoshi SHOUDAI, Yuta YOSHIMURA, Yusuke SUZUKI, Tomoyuki UCHIDA, Tetsuhiro MIYAHARA, },
journal={IEICE TRANSACTIONS on Information},
title={Polynomial Time Learnability of Graph Pattern Languages Defined by Cographs},
year={2018},
volume={E101-D},
number={3},
pages={582-592},
abstract={A cograph (complement reducible graph) is a graph which can be generated by disjoint union and complement operations on graphs, starting with a single vertex graph. Cographs arise in many areas of computer science and are studied extensively. With the goal of developing an effective data mining method for graph structured data, in this paper we introduce a graph pattern expression, called a cograph pattern, which is a special type of cograph having structured variables. Firstly, we show that a problem whether or not a given cograph pattern g matches a given cograph G is NP-complete. From this result, we consider the polynomial time learnability of cograph pattern languages defined by cograph patterns having variables labeled with mutually different labels, called linear cograph patterns. Secondly, we present a polynomial time matching algorithm for linear cograph patterns. Next, we give a polynomial time algorithm for obtaining a minimally generalized linear cograph pattern which explains given positive data. Finally, we show that the class of linear cograph pattern languages is polynomial time inductively inferable from positive data.},
keywords={},
doi={10.1587/transinf.2017FCP0005},
ISSN={1745-1361},
month={March},}

Copy

TY - JOUR
TI - Polynomial Time Learnability of Graph Pattern Languages Defined by Cographs
T2 - IEICE TRANSACTIONS on Information
SP - 582
EP - 592
AU - Takayoshi SHOUDAI
AU - Yuta YOSHIMURA
AU - Yusuke SUZUKI
AU - Tomoyuki UCHIDA
AU - Tetsuhiro MIYAHARA
PY - 2018
DO - 10.1587/transinf.2017FCP0005
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E101-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2018
AB - A cograph (complement reducible graph) is a graph which can be generated by disjoint union and complement operations on graphs, starting with a single vertex graph. Cographs arise in many areas of computer science and are studied extensively. With the goal of developing an effective data mining method for graph structured data, in this paper we introduce a graph pattern expression, called a cograph pattern, which is a special type of cograph having structured variables. Firstly, we show that a problem whether or not a given cograph pattern g matches a given cograph G is NP-complete. From this result, we consider the polynomial time learnability of cograph pattern languages defined by cograph patterns having variables labeled with mutually different labels, called linear cograph patterns. Secondly, we present a polynomial time matching algorithm for linear cograph patterns. Next, we give a polynomial time algorithm for obtaining a minimally generalized linear cograph pattern which explains given positive data. Finally, we show that the class of linear cograph pattern languages is polynomial time inductively inferable from positive data.
ER -