Conference item icon

Conference item

Counting subgraphs in somewhere dense graphs

Abstract:

We study the problems of counting copies and induced copies of a small pattern graph H in a large host graph G. Recent work fully classified the complexity of those problems according to structural restrictions on the patterns H. In this work, we address the more challenging task of analysing the complexity for restricted patterns and restricted hosts. Specifically we ask which families of allowed patterns and hosts imply fixed-parameter tractability, i.e., the existence of an algorithm ru...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed

Actions


Access Document


Files:
Publisher copy:
10.4230/LIPIcs.ITCS.2023.27

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Author
Publisher:
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Host title:
14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Series:
Leibniz International Proceedings in Informatics (LIPIcs)
Series number:
251
Pages:
27:1-27:14
Place of publication:
Dagstuhl, Germany
Publication date:
2023-02-01
Acceptance date:
2022-10-30
Event title:
14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Event location:
Cambridge, Massachusetts, USA
Event website:
http://itcs-conf.org/index.html
Event start date:
2022-12-11
Event end date:
2023-01-13
DOI:
ISSN:
1868-8969
ISBN:
9783959772631
Language:
English
Keywords:
Pubs id:
1298951
Local pid:
pubs:1298951
Deposit date:
2022-11-03

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP