# Questions tagged [graph-theory]

Graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects.

1,231 questions
131 views

90 views

### Path Finding: single-source, multi-path, multi-target, and max-depth - approaches and application

Background Definitions (as used here): $\qquad$single-source: for path finding, an algorithm is single-source if it searches from a given node. $\qquad$multi-target: for path finding, an ...
59 views

### Finding a Minimal k-Subgraph

Given a complete, positively weighted, bidirectional graph with $n$ nodes without self-loops. Hence the corresponding adjacency matrix $A$ is positive, symmetric, and has zero main diagonal. I am ...
95 views

### Is there any better than (2/k)-approximation algorithm for Independent Set in Coloring graph?

I would like to know any results in terms of approximation algorithm about Maximum weight Independent Set problem in coloring graph. Input: Given a graph G with non-negative vertex weights and ...
72 views

### Complexity of bounded degree full contraction

This paper defines the problem $\mathrm{B{\scriptsize OUNDED} \ D{\scriptsize EGREE}\ C{\scriptsize ONTRACTION}}$ as follows: Instance: A graph $G$ and two integers $d$ and $k$. Question: Is there a ...
116 views

### Hardness of Approximation for minimum path cover in an undirected graph?

Given an undirected graph $G = (V,E)$, a path cover is a set of disjoint paths such that every vertex $v\in V$ belongs to exactly one path. The minimum path cover problem consists of finding a path ...
98 views

75 views

81 views

### Unbalanced connected partition

Let $G = (V, E)$ be a connected graph with (possibly negative) vertex weights $w(v)\in\mathbb{Z}$. We want to partition the vertices into two parts such that the induced graphs $G'$ and $G''$ are ...
314 views

### Why isn't the Charikar algorithm for finding the densest subgraph optimal?

I read about the algorithm in Greedy Approximation Algorithms for Finding Dense Components in a Graph by Moses Charikar, and I tried to find an instance/graph where the algorithm returns a different ...
42 views

### Is a k-connected graph also k-1 connected?

So I'm reading about k-connected graphs, and I'm a little confused about them. This is the main definition I've seen: A graph is k connected if and only if for any distinct x, y vertices in the graph,...
143 views

### Data structure to search name of files and get its path

I will be inserting names of files in a dynamically way, approximately till 1 billion of names. Besides, I do also want to store the path where the files are located in order to do the following ...
125 views

126 views

53 views

### Preference based group generator

I'm looking for a polynomial time algorithm for the following problem: $n$ number of students must be partitioned into $\frac{n - n\%m}{m}$ sets where $m$ is the ideal cardinality. Each pair of ...
It is a well known fact that if $H$ is a graph of maximum degree 3, then $H$ is a minor of a graph $G$ if and only if $H$ is a topological minor of $G$. Moreover, a graph $G$ has one of $K_{3,3}$ or \$...