Publication

Tree Projections: Game Characterization and Computational Aspects

2009
Book Chapters

Abstract

The notion of tree projection provides a natural generalization for various structural decomposition methods, which have been proposed in the literature in order to single out classes of nearly-acyclic (hyper)graphs. In this paper, the mathematical properties of the notion of tree projection are overviewed, and the complexity of the basic tree projection problem (of deciding the existence of a tree projection) is depicted. In more details, a game-theoretic characterization (in terms of the Robber and Captain game [15]) for tree projections is described, which also serves to provide simple arguments for the membership in NP of the tree projection problem. Eventually, the main ideas proposed in [14] and underlying the proof of NP-hardness of the tree projection problem are discussed.

Official source

https://infoscience.epfl.ch/entities/publication/db3c1d4a-0495-487c-a9ac-b5b4d7199796

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

2009
Book Chapters

Abstract

Official source

https://infoscience.epfl.ch/entities/publication/db3c1d4a-0495-487c-a9ac-b5b4d7199796

About this result

Related concepts (32)

NP-hardness

In computational complexity theory, NP-hardness (non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard problem is the subset sum problem. A more precise specification is: a problem H is NP-hard when every problem L in NP can be reduced in polynomial time to H; that is, assuming a solution for H takes 1 unit time, Hs solution can be used to solve L in polynomial time.

NP (complexity)

In computational complexity theory, NP (nondeterministic polynomial time) is a complexity class used to classify decision problems. NP is the set of decision problems for which the problem instances, where the answer is "yes", have proofs verifiable in polynomial time by a deterministic Turing machine, or alternatively the set of problems that can be solved in polynomial time by a nondeterministic Turing machine. NP is the set of decision problems solvable in polynomial time by a nondeterministic Turing machine.

NP-completeness

In computational complexity theory, a problem is NP-complete when: It is a decision problem, meaning that for any input to the problem, the output is either "yes" or "no". When the answer is "yes", this can be demonstrated through the existence of a short (polynomial length) solution. The correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by trying all possible solutions.

Related publications (8)

Tree Projections: Game Characterization and Computational Aspects

Chat with Graph Search

Data-Driven C-Refinement A proof-of-concept

A Lagrangian relaxation method for a choice-based optimization framework capturing the demand-supply interaction

MATHICSE Technical Report : Geometric multiscale modeling of the cardiovascular system, between theory and practice