Publication

Some complexity results about threshold graphs

1994
Journal Articles

Abstract

The problem of determining whether a graph G contains a threshold subgraph containing at least h edges is shown to be NP-complete if h is part of the input as the problems of minimum threshold completion, weighted 2-threshold partition and weighted 2-threshold covering. We also prove that the k-cyclic scheduling problem is NP-complete for all fixed k, a result used to show that deciding whether a threshold r-hypergraph contains a Hamiltonian cycle is NP-complete

Official source

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.

1994
Journal Articles

Abstract

Official source

Related concepts (32)

Threshold graph

In graph theory, a threshold graph is a graph that can be constructed from a one-vertex graph by repeated applications of the following two operations: Addition of a single isolated vertex to the graph. Addition of a single dominating vertex to the graph, i.e. a single vertex that is connected to all other vertices. For example, the graph of the figure is a threshold graph. It can be constructed by beginning with a single-vertex graph (vertex 1), and then adding black vertices as isolated vertices and red vertices as dominating vertices, in the order in which they are numbered.

Chordal graph

In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a chord, which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced cycle in the graph should have exactly three vertices. The chordal graphs may also be characterized as the graphs that have perfect elimination orderings, as the graphs in which each minimal separator is a clique, and as the intersection graphs of subtrees of a tree.

Trivially perfect graph

In graph theory, a trivially perfect graph is a graph with the property that in each of its induced subgraphs the size of the maximum independent set equals the number of maximal cliques. Trivially perfect graphs were first studied by but were named by ; Golumbic writes that "the name was chosen since it is trivial to show that such a graph is perfect." Trivially perfect graphs are also known as comparability graphs of trees, arborescent comparability graphs, and quasi-threshold graphs.

Related publications (31)

Some complexity results about threshold graphs

Chat with Graph Search

Sponsored Fair Exchange (Extended Abstract)

Denoising Score Matching with Random Features: Insights on Diffusion Models From Precise Learning Curves

Sensor network localization has a benign landscape after low-dimensional relaxation