Explore our many areas of focus

Explore all research areas

Applied AI & sciences

Earth AI

Health AI

Science AI

Sustainability & crisis resilience

Foundational ML & algorithms

Algorithms & theory

Information retrieval

Machine intelligence

Machine perception

Natural language processing

People, systems & quantum AI

Human-computer interaction and visualization

Learn More

Building a collaborative ecosystem

Datasets

Access high-quality datasets to accelerate your research.

Tools & services

Explore our latest AI models and products.

Open source

Discover open-source code and collaborate with the community.

Shaping the future together

See all programs

Faculty programs

Participating in the academic research community through meaningful engagement with university faculty.

Student programs

Supporting the next generation of researchers through a wide range of programming.

Locations

Find your place in our global offices and research labs.

Translating discovery into real-world impact

People

Our researchers drive advancements in computer science through both fundamental and applied research.

Teams

Collaborative groups tackling the world's most challenging AI problems.

Research

Explore our many areas of focus

Explore all research areas

Applied AI & sciences

Earth AI

Health AI

Science AI

Sustainability & crisis resilience

Foundational ML & algorithms

Algorithms & theory

Information retrieval

Machine intelligence

Machine perception

Natural language processing

People, systems & quantum AI

Human-computer interaction and visualization

Learn More

Resources

Building a collaborative ecosystem

Datasets

Access high-quality datasets to accelerate your research.

Tools & services

Explore our latest AI models and products.

Open source

Discover open-source code and collaborate with the community.

Conferences & events

Careers

Shaping the future together

See all programs

Faculty programs

Participating in the academic research community through meaningful engagement with university faculty.

Student programs

Supporting the next generation of researchers through a wide range of programming.

Locations

Find your place in our global offices and research labs.

Blog

About

Translating discovery into real-world impact

People

Our researchers drive advancements in computer science through both fundamental and applied research.

Teams

Collaborative groups tackling the world's most challenging AI problems.

Google Research

Google AI

Learn about all our AI

Google DeepMind

Explore the frontier of AI

Google Labs

Try our AI experiments

Conferences & events

Blog

Home
Publications

NP-Completeness of graph decomposition problems

Edith Cohen

Michael Tarsi

J. Complexity, 7 (1991), pp. 200-212

Google Scholar

Abstract

Meet the teams driving innovation

Our teams advance the state of the art through research, systems engineering, and collaboration across Google.

See our teams

Explore our other initiatives

Google AI

Discover how Google AI is committed to enriching knowledge and solving complex challenges

Products
Build
Research
Responsibility
Societal Impact
About

Google Cloud

High-performance infrastructure for cloud computing, data analytics & machine learning

Overview
Solutions
Products
Pricing
Resources

Google DeepMind

Our mission is to build AI responsibly to benefit humanity

Models
Research
Science
About

Google Labs

Explore the future of AI responsibly with Google Labs

About
Experiments
Stay connected

About Google

Google Products

Privacy

Terms