research-article

Monadic second order logic on graphs with local cardinality constraints

Author:

Stefan SzeiderAuthors Info & Claims

ACM Transactions on Computational Logic (TOCL), Volume 12, Issue 2

Article No.: 12, Pages 1 - 21

https://doi.org/10.1145/1877714.1877718

Published: 27 January 2011 Publication History

Abstract

We introduce the class of MSO-LCC problems, which are problems of the following form. Given a graph G and for each vertex v of G a set α(v) of non-negative integers. Is there a set S of vertices or edges of G such that, (1) S satisfies a fixed property expressible in monadic second order logic, and (2) for each vertex v of G the number of vertices/edges in S adjacent/incident with v belongs to the set α(v)? We demonstrate that several hard combinatorial problems such as Lovász's General Factor Problem can be naturally formulated as MSO-LCC problems. Our main result is the polynomial-time tractability of MSO-LCC problems for graphs of bounded treewidth. We obtain this result by means of a tree-automata approach. By way of contrast we show that a more general class of MSO-LCC problems, where cardinality constraints are applied to second-order variables that are arbitrarily quantified, does not admit polynomial-time tractability for graphs of bounded treewidth unless P=NP.

References

[1]

Arnborg, S., Corneil, D. G., and Proskurowski, A. 1987. Complexity of finding embeddings in a k-tree. SIAM J. Algebraic Discrete Meth. 8, 2, 277--284.

Digital Library

[2]

Arnborg, S., Lagergren, J., and Seese, D. 1991. Easy problems for tree-decomposable graphs. J. Algorithms 12, 2, 308--340.

Digital Library

[3]

Asahiro, Y., Miyano, E., and Ono, H. 2008. Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree. In Proceedings of Computing: The Australasian Theory Symposium (CATS). J. Harland and P. Manyem, Eds., Conferences in Research and Practice in Information Technology, vol. 77, Australian Computer Society, Sydney, 97--106.

Digital Library

[4]

Bodlaender, H. L. 1996. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25, 6, 1305--1317.

Digital Library

[5]

Bodlaender, H. L. 1998. A partial k-arboretum of graphs with bounded treewidth. Theoret. Comput. Sci. 209, 1-2, 1--45.

Digital Library

[6]

Bodlaender, H. L. and Fomin, F. V. 2005. Equitable colorings of bounded treewidth graphs. Theoret. Comput. Sci. 349, 1, 22--30.

Digital Library

[7]

Cornuéjols, G. 1988. General factors of graphs. J. Combin. Theory Ser. B 45, 2, 185--198.

Digital Library

[8]

Courcelle, B. 1987. Recognizability and second-order definability for sets of finite graphs. Tech. rep. I-8634, Université de Bordeaux.

[9]

Courcelle, B. 1990. Graph rewriting: an algebraic and logic approach. In Handbook of Theoretical Computer Science, vol. B. Elsevier Science Publishers, North-Holland, Amsterdam, 193--242.

Digital Library

[10]

Downey, R. G. and Fellows, M. R. 1999. Parameterized Complexity. Monographs in Computer Science. Springer-Verlag, Berlin.

[11]

Flum, J. and Grohe, M. 2006. Parameterized Complexity Theory. Texts in Theoretical Computer Science, An EATCS Series, vol. XIV, Springer-Verlag, Berlin.

Digital Library

[12]

Frick, M. and Grohe, M. 2004. The complexity of first-order and monadic second-order logic revisited. Ann. Pure App. Logic 130, 1-3, 3--31.

[13]

Garey, M. R. and Johnson, D. R. 1979. Computers and Intractability. W. H. Freeman and Company, New York.

Digital Library

[14]

Grohe, M. 2007. Logic, graphs, and algorithms. In Logic and Automata: History and Perspectives, J. Flum, E. Grädel, and T. Wilke, Eds., Texts in Logic and Games, vol. 2, Amsterdam University Press, 357--422.

[15]

Kloks, T. 1994. Treewidth: Computations and Approximations. Springer-Verlag, Berlin.

[16]

Kostochka, A. V., Nakprasit, K., and Pemmaraju, S. V. 2005. On equitable coloring of d-degenerate graphs. SIAM J. Discrete Math. 19, 1, 83--95.

Digital Library

[17]

Lih, K.-W. 1998. The equitable coloring of graphs. In Handbook of Combinatorial Optimization, vol. 3, Kluwer Academic Publishers, Boston, MA, 543--566.

[18]

Lovász, L. 1970. The factorization of graphs. In Combinatorial Structures and their Applications (Proceedings of the Calgary International Conformation). Gordon and Breach, New York, 243--246.

[19]

Lovász, L. 1972. The factorization of graphs. II. Acta Math. Acad. Sci. Hungar. 23, 223--246.

[20]

Meyer, W. 1973. Equitable coloring. Amer. Math. Monthly 80, 920--922.

[21]

Niedermeier, R. 2006. Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and its Applications. Oxford University Press, Oxford.

[22]

Rose, D. J. 1974. On simple characterizations of k-trees. Discrete Math. 7, 317--322.

Digital Library

[23]

Samer, M. and Szeider, S. 2009. Tractable cases of the extended global cardinality constraint. Constraints. Springer Online.

Digital Library

[24]

Thatcher, J. W. and Wright, J. B. 1968. Generalized finite automata theory with an application to a decision problem of second-order logic. Math. Syst. Theory 2, 57--81.

[25]

Tutte, W. T. 1952. The factors of graphs. Canadian J. Math. 4, 314--328.

Cited By

Gima TOtachi Y(2024)Extended MSO Model Checking via Small Vertex IntegrityAlgorithmica10.1007/s00453-023-01161-986:1(147-170)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1007/s00453-023-01161-9
Gima THanaka TKiyomi MKobayashi YOtachi Y(2022)Exploring the gap between treedepth and vertex cover through vertex integrityTheoretical Computer Science10.1016/j.tcs.2022.03.021918:C(60-76)Online publication date: 29-May-2022
https://dl.acm.org/doi/10.1016/j.tcs.2022.03.021
Markakis EPapasotiropoulos G(2021)An Approval-Based Model for Single-Step Liquid DemocracyAlgorithmic Game Theory10.1007/978-3-030-85947-3_24(360-375)Online publication date: 21-Sep-2021
https://dl.acm.org/doi/10.1007/978-3-030-85947-3_24
Show More Cited By

Index Terms

Monadic second order logic on graphs with local cardinality constraints
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms
2. Theory of computation
  1. Logic

Recommendations

Parameterized complexity of finding small degree-constrained subgraphs

In this article we study the parameterized complexity of problems consisting in finding degree-constrained subgraphs, taking as the parameter the number of vertices of the desired subgraph. Namely, given two positive integers d and k, we study the ...
Lower Bounds for the Complexity of Monadic Second-Order Logic
LICS '10: Proceedings of the 2010 25th Annual IEEE Symposium on Logic in Computer Science

Courcelle's famous theorem from 1990 states that any property of graphs definable in monadic second-order logic (MSO_2) can be decided in linear time on any class of graphs of bounded tree-width, or in other words, MSO_2 is fixed-parameter tractable in ...
Graph-based data clustering with overlaps

We introduce overlap cluster graph modification problems where, other than in most previous works, the clusters of the target graph may overlap. More precisely, the studied graph problems ask for a minimum number of edge modifications such that the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Computational Logic

ACM Transactions on Computational Logic Volume 12, Issue 2

January 2011

317 pages

ISSN:1529-3785

EISSN:1557-945X

DOI:10.1145/1877714

Issue’s Table of Contents

Copyright © 2011 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 27 January 2011

Accepted: 01 April 2010

Revised: 01 January 2010

Received: 01 April 2009

Published in TOCL Volume 12, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

European Research Council

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
180
Total Downloads

Downloads (Last 12 months)10
Downloads (Last 6 weeks)1

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Gima TOtachi Y(2024)Extended MSO Model Checking via Small Vertex IntegrityAlgorithmica10.1007/s00453-023-01161-986:1(147-170)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1007/s00453-023-01161-9
Gima THanaka TKiyomi MKobayashi YOtachi Y(2022)Exploring the gap between treedepth and vertex cover through vertex integrityTheoretical Computer Science10.1016/j.tcs.2022.03.021918:C(60-76)Online publication date: 29-May-2022
https://dl.acm.org/doi/10.1016/j.tcs.2022.03.021
Markakis EPapasotiropoulos G(2021)An Approval-Based Model for Single-Step Liquid DemocracyAlgorithmic Game Theory10.1007/978-3-030-85947-3_24(360-375)Online publication date: 21-Sep-2021
https://dl.acm.org/doi/10.1007/978-3-030-85947-3_24
Gima THanaka TKiyomi MKobayashi YOtachi Y(2021)Exploring the Gap Between Treedepth and Vertex Cover Through Vertex IntegrityAlgorithms and Complexity10.1007/978-3-030-75242-2_19(271-285)Online publication date: 4-May-2021
https://doi.org/10.1007/978-3-030-75242-2_19
Araújo JSales CSau ISilva A(2018)Weighted proper orientations of trees and graphs of bounded treewidthTheoretical Computer Science10.1016/j.tcs.2018.11.013Online publication date: Nov-2018
https://doi.org/10.1016/j.tcs.2018.11.013
Knop DKoutecký MMasařík TToufar T(2017)Simplified Algorithmic Metatheorems Beyond MSO: Treewidth and Neighborhood DiversityGraph-Theoretic Concepts in Computer Science10.1007/978-3-319-68705-6_26(344-357)Online publication date: 2-Nov-2017
https://doi.org/10.1007/978-3-319-68705-6_26
Bonnet ÉEscoffier BPaschos VTourniaire É(2015)Multi-parameter Analysis for Local Graph Partitioning ProblemsAlgorithmica10.1007/s00453-014-9920-671:3(566-580)Online publication date: 1-Mar-2015
https://dl.acm.org/doi/10.1007/s00453-014-9920-6
Fellows MJansen BRosamond F(2013)Towards fully multivariate algorithmicsEuropean Journal of Combinatorics10.1016/j.ejc.2012.04.00834:3(541-566)Online publication date: 1-Apr-2013
https://dl.acm.org/doi/10.1016/j.ejc.2012.04.008
PICHLER RRÜMMELE SSZEIDER SWOLTRAN S(2012)Tractable answer-set programming with weight constraints: bounded treewidth is not enoughTheory and Practice of Logic Programming10.1017/S147106841200009914:2(141-164)Online publication date: 17-Jul-2012
https://doi.org/10.1017/S1471068412000099
Gutin GKim ESoleimanfallah ASzeider SYeo A(2011)Parameterized Complexity Results for General Factors in Bipartite Graphs with an Application to Constraint ProgrammingAlgorithmica10.1007/s00453-011-9548-864:1(112-125)Online publication date: 27-Jul-2011
https://doi.org/10.1007/s00453-011-9548-8

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents