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

learn more… | top users | synonyms (1)

0
votes
1answer
59 views

Understanding graph minor theorem

This question is two-fold, and is mainly reference-oriented: Is there somewhere where the main intuitions for proving graph minor theorem are given, without going too much into the details? I know ...
-1
votes
2answers
77 views

Upper bound for number of independent sets

What is the tightest upper bound known for the number of independent sets in a graph?
3
votes
1answer
55 views

Expected length of longest construction path in Barabási–Albert Model

The Barabási-Albert Model is used for constructing scale-free networks using the preferential attachment technique. The essence, as I understand it, is that nodes are incrementally added to a graph by ...
0
votes
4answers
146 views

Finding outer face in plane graph (embedded planar graph)

I have a planar graph, for which I have computed a combinatorial embedding and coordinates in the plane. So all my arcs are now oriented in the plane, respective to their end vertices. Computing a ...
-4
votes
0answers
25 views

Proving optimality for a new algorithm that finds minimum spanning tree [on hold]

Below is an algorithm that finds the minimum spanning tree: ...
7
votes
0answers
110 views

Enumerating Planar Graphs of Bounded Treewidth

I am looking for references for the following problem: given integers $n$ and $k$, enumerate all non-isomorphic planar graphs on $n$ vertices and treewidth $\leq k$. I'm interested both in theoretical ...
0
votes
0answers
28 views

Mapping load balancing to graph theory

I'm looking for algorithms that transform/reduce dynamic load balancing problem in a cluster to a flow problem. I have n machines each of them constantly performing a job, suppose a machine is ...
3
votes
0answers
58 views

Definition of Clique width of graph

The clique width of graph $G$ is defined as minimum number of labels required to construct $G$ by using four operations. I would like to know why the name clique width is given to this definition. ...
-4
votes
0answers
49 views

Find a particular subset not empty of a graph

I have a problem that I don't know how to solve: Every edge of a general graph G = (VERTICES,EDGES) has a real number 0<=val<=1. Every node is indicated with a letter of the alphabet; G does ...
-4
votes
0answers
43 views

Find subsets of nodes in a graph sum of all edges [on hold]

Is it possible to visit all the cycles in a graph not necessary directed, from the smaller to the bigger in a polynomial time alghoritm? Example of output: ABA = cycle of 2 nodes ABCA = cycle of 3 ...
0
votes
1answer
83 views

Graph theory: definiton of the crown of a graph

I'm currently reading "Invitation to Fixed-Parameter Algorithms" by Rolf Niedermayer. Page 69 gives the following definition of the crown of a graph, which I do not quite understand: A crown of a ...
2
votes
0answers
54 views

How to Quantify Entropy in a Data Set

I'm currently creating a program in Java to analysis the pathological cases of Quicksort. Namely, the transition of complexity from O(n^2) to O(nlogn) as a data set gets less ordered. Since Quicksort ...
0
votes
1answer
41 views

Assign each biclique to a distinct left

Given a minimum biclique edge cover, is it always possible to assign each biclique to a distinct left node (which it contains)? ie one such assignment for this graph (from wikipedia): ...
1
vote
0answers
29 views

Common subgraph isomorphism with K vertex [migrated]

I'm looking for subgraph isomorphism of at least K vertex between Graph A and B. I only can come up with the dumbest algorithm, which is: Compute all combination of vertices with length K of Graph ...
6
votes
0answers
60 views

Approximating a max-cut's intersection with other cuts

For the purposes of this question, a cut in a graph $G$ is the edge-set $\delta (S)\subseteq E(G)$ between some vertex-set $S$ and its complement. A max cut is one with at least as many edges as any ...
8
votes
0answers
91 views

Advances towards proving the Held-Karp conjecture for TSP

I've only began my research into the Held-Karp conjecture and I was wondering about recent progress in proving the conjecture. The Held-Karp relaxation is conjectured to have an integrality gap of ...
-1
votes
0answers
78 views

NP-hardness of the following problem

A subgraph $H \subseteq G$ is said to be 'valid' if all the paths in $H$ satisfy the property $x$. The property $x$ is closed under taking sub-paths. Given a directed graph $G$ and a set of all ...
3
votes
0answers
114 views

The largest connected component of a random subgraph

Let a graph on $|V|$ vertices and $|E|$ edges. We randomly sample $s= c \cdot \frac{|V|}{{d_{\text{av}}}}$ vertices, without replacement, where $d_{\text{av}}$ is the average degree of $G$ and $c$ is ...
7
votes
1answer
174 views

A curious asymmetry in good characterizations

There are quite a few theorems, mostly in graph theory and combinatorial optimization, that are often referred to as good characterizations. They typically put a property in $NP\cap co-NP$, by showing ...
-1
votes
2answers
80 views

Steiner trees - the added edges and vertices [on hold]

I have been reading up on Steiner Tree. I am a beginner. The explanation I find is this : The Steiner tree problem is superficially similar to the minimum spanning tree problem: given a set V of ...
-1
votes
0answers
45 views

Name of special class of k-partite graphs

Consider directed graphs $G=(V,E)$ such that $V$ can be partitioned into sets $V_1, V_2, \ldots, V_k$. For the edges we have that if $v \in V_i$ and $(v,w) \in E$ then $w \in V_{i+1}$ for all $1 \le ...
-2
votes
1answer
91 views

Connecting partial paths to form a hamiltonian cycle [closed]

For an undirected graph that consists of partial paths such that each vertex is a part of one of those paths and that there are edges between all the paths, is there an efficient algorithm to connect ...
0
votes
0answers
83 views

Best Hamiltonian Cycle Problem solver

What is the best Hamiltonian Cycle Problem (HCP) solvers available in the market? Googling so far shows that there is one created by Flinders University that can solve at most 5000 node instances. I ...
4
votes
0answers
118 views

Can we decide Red-blue cut problem in polynomial time?

Given a directed graph whose arcs are coloured red and blue and integers $r$ and $b$, can we decide in polynomial time whether the digraph has a cut with at most $r$ red arcs and at most $b$ blue ...
2
votes
2answers
94 views

Graph-theoretic properties of the Wiener index

The Wiener index of a graph is the sum of the lengths of the shortest paths between all pairs of its vertices. Are there useful graph-theoretic properties of this index?
5
votes
0answers
119 views

The minimum entropy of a proper coloring of a graph

The chromatic number $\chi(G)$ of an undirected graph $G$ is the minimum number of colors in a proper coloring of the vertices of $G$ (where a proper coloring uses different colors for two vertices ...
4
votes
0answers
113 views

Recognition problem of cycle permutation graphs

A cycle permutation graph is a cubic graph composed from two $n$-cycles each labeled $1, 2,..., n$, with additional edges connecting vertex $i$ in the first cycle to vertex $\pi(i)$ in the second, ...
8
votes
0answers
284 views

Is it possible to solve perfect matching in linear time

As we know matching can be solve in polynomial time. One classical and famous algorithm is designed by Karp and Hopcroft. Is it possible to solve perfect matching problem in linear time for given ...
2
votes
1answer
361 views

Is DAG isomorphism NP-C

Given two directed acyclic graphs $G_1$ and $G_2$, is it NP-Complete to find a one-to-one mapping $f:V(G_1) \rightarrow V(G_2)$ such that $(v_i,v_j) \in D(G_1)$ if and only if $(f(v_i),f(v_j)) \in ...
5
votes
0answers
111 views

lower bound for difference between max cut and min cut

Let $G=(V,E)$ be a graph on $n$ vertices with edge weights $w=(w_e)_{e\in E}$. Let $M^+$ and $M^-$ be the maximum and the minimum cut values, i.e. ...
4
votes
0answers
160 views

Is this graph polynomial known? Can it be efficiently computed?

Consider a connected simple graph $G$ with $n$ vertices and $m$ edges. View each edge $\ell$ as a transposition $t_{\ell}$ acting on the set of vertices. [To be more explicit, given an edge $\ell$ ...
-2
votes
1answer
131 views

Finding cliques in weighted graph

We have given a weighted graph $G=\{V,E\}$, where $V=\{v_1, v_2,...,v_n\}$, and for all $i,j$, the weight of edges $w(v_i, v_j)\in (0,W)$. And we have also given a weight threshold s $w$ (where ...
2
votes
1answer
139 views

Planar separator theorem and tree decomposition

The Wikipedia article about the Planar Separator Theorem states that it is possible to use a hierarchy of separators to construct a tree decomposition for a planar graph and moreover provides an ...
6
votes
2answers
336 views

Complexity of finding even cuts for a graph

Given a graph $G=(V,E)$, what is known about the classical computational complexity of finding a non-trivial cut which partitions the vertices into two sets $V_a$ and $V_b$ such that every vertex in ...
5
votes
0answers
82 views

General Results for Complicated Constraint Satisfaction Problem

Consider the following problem: on a finite two-dimensional grid (say the grid points are vertices of a graph), I need to color the vertices in such a way to satisfy the existence and nonexistence of ...
2
votes
1answer
66 views

When polynomial GI implies polynomial (edge) colored GI?

Crossposted from MO. (edge) colored graph isomorphism is GI which preserves the colors (of edges if it is edge colored). There are several reductions using transformations/gadgets of (edge) colored ...
5
votes
1answer
69 views

Is there an extension to the stable roommates problem with multiple roommates per room?

The stable roommates problem presents a set of N two-person rooms and 2N would-be roommates with preferences over each other, and asks for a stable allocation of roommates to rooms (and, really, to ...
-1
votes
1answer
76 views

Minimum vertex cover for bipartite graphs

I know that it is possible to calculate the minimum vertex cover of a bipartite graph, However, i want that the minimum vertex cover which contains vertices from only one partite set, which will be ...
8
votes
1answer
101 views

Is there a gadget that reduces generalized geography to undirected graphs?

The directed Generalized Geography game is well-known to be PSPACE-complete, however, I could not find anything for the undirected version. I saw that in Hans L. Bodlaender, Complexity of path-forming ...
1
vote
1answer
171 views

Rings and the set of all minimum s-t-cuts

Let $N$ be a flow network with nodes $V$ and edges $E$. For technical reasons, the source side of a minimum $s$-$t$ cut $(A,B)$ with $s \in A$ and $t \in B$ is defined as $A - \{s\}$. Now, let ...
3
votes
0answers
74 views

Online bridge and nonbridge counting (identification)

I was wondering if there is any efficient (possibly armortized poly-logarithmic) online algorithm which supports counting (identification) of bridges- and non-bridges online, i.e. during a sequence of ...
15
votes
3answers
307 views

What separates easy global problems from hard global problems on graphs of bounded treewidth?

Plenty of hard graph problems are solvable in polynomial time on graphs of bounded treewidth. Indeed, textbooks typically use e.g. independet set as an example, which is a local problem. Roughly, a ...
2
votes
0answers
120 views

Regular graph coloring conjecture

Almost all regular graphs with degree $k^2$ are $k+1$ colorable. The near absence (finitude) of adjacent small cycles in random regular graphs as $N$ (the size of the graph) grows may help imply the ...
-3
votes
1answer
93 views

Finding an exactly weighted st-path in a digraph [closed]

I have a weighted digraph graph $G = (V,E)$ where the weights are positive and negative integers. The graph $G$ is not necessarily acyclic. The question is: given 2 nodes $v_1$ and $v_2$, is there a ...
0
votes
1answer
72 views

How to map random cardesian points in a 2d array

I was wondering if there is any algorithm, theoretical or already implemented, or if its even possible at all, where, given N random ...
-3
votes
1answer
64 views

tagging and graph “compression”

I have a question on stack-overflow about "compressing" a graph. Suppose I have tags from a finite set $T$ and objects from a finite set $O$. Moreover there are (uni-directional) links from elements ...
4
votes
0answers
76 views

Indexing structure for all-pairs min-cuts in a huge DAG

I have a huge DAG - e.g., the dependency graph of all packages in a linux distribution. Suppose I'd like to make a user-friendly tool that makes it very easy to understand how to break the transitive ...
-1
votes
2answers
78 views

Arrangements of Objects

Suppose there are $n$ bins each having $k$ objects. Assume that capacity of each bin is also $k$. Now we want to rearrange the objects such that each bin contains $k$ objects but this time if $x,y$ ...
1
vote
1answer
73 views

Connecting vertices after struction operation in J.Chen, I.Kanj, G.Xia vertex cover algorithm

EDIT: I'm sorry if this question belongs more to cs.SE, I've had a dilemma about where to put it. Please let me know if it's inappropriate. I'm currently implementing the Vertex Cover problem solving ...
3
votes
2answers
153 views

Decompose a complete graph into smaller cliques

The following exercise problem is from the book of D.B.West which i could solve: If a complete graph can be decomposed into triangles then $n-1$ or $n-3$ is divisible by 6. So my questions are ...