Tagged Questions

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
28 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
43 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
36 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
54 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
82 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 ...
-2
votes
0answers
22 views

Tree T in a graph G that isn't normal

I'm trying to figure out what a normal tree actually means, and what I don't understand is how can a tree be not normal. Is it simply that a normal tree T has to contains all vertices of G? EDIT: ...
-4
votes
0answers
24 views

Proof of Attribute of Balanced (1,1)-Biregular Bipartite Graphs [closed]

Prove that if G is a balanced, biregular, bipartite graph, then the edges of G can be partitioned into blocks such that each block is a perfect matching.
-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
100 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 ...
-4
votes
0answers
46 views

Euclidean Minimum Spanning Tree Property [closed]

Is the following statement about Euclidean MSTs true, and if so could someone help me with a proof? Between any two nodes, the EMST minimizes the maximum edge cost of any edge required to traverse ...
7
votes
1answer
170 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
76 views

Steiner trees - the added edges and vertices

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
44 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
88 views

Connecting partial paths to form a hamiltonian cycle [on hold]

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
81 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
117 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
0answers
27 views

Find all the Cycle Bases in a Undirected Graph [on hold]

How to find all the Cycle Bases in a Undirected Graph For example, given the graph: 0 --- 1 | | \ | | \ 4 --- 3 - 2 the algorithm should return 1-2-3 ...
-1
votes
0answers
44 views

Edge-based NP-hard problems for reduction

I have a problem formulation where the input is a undirected graph $G=(V,E)$, and the task is to add a set of new edges $F \subseteq V\times V \setminus E$ to $E$, but no node $v\in V$ receives more ...
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
116 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
111 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
357 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
110 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
130 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
134 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
334 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
80 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
67 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
75 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
99 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
150 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 ...
14
votes
3answers
304 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
71 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
73 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
77 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
151 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 ...
7
votes
0answers
478 views

Consequences of $\oplus \mathbf{P} \subseteq \mathbf{NP}$

I have part of a proof attempt of $\oplus \mathbf{P} \subseteq \mathbf{NP}$. The proof attempt consists of a Karp reduction from the $\oplus \mathbf{P}$-complete problem $\oplus$3-REGULAR VERTEX COVER ...
3
votes
3answers
394 views

Sub-exponential algorithm for Hamiltonian cycle problem on cubic planar graphs?

There are several graph $NP$-complete problems that have sub-exponential time algorithm on planar graph instances. What is the fastest algorithm for HC problem on cubic planar graphs? Is there a ...
1
vote
0answers
119 views

Graph sparsification

I would like to ask if any one is aware of any results related to graph sparsification with bounded degrees? What I mean is anyone aware of graph sparsification results such that the resultant graph ...
4
votes
2answers
204 views

Algorithms for online clique detection

Are there any algorithms which let you detect cliques when adding/deleting edges based on previously detected cliques? What would be the time/memory complexity of this approach?
6
votes
2answers
193 views

Partition planar graph into connected subgraphs of equal size

Work Jünger, Michael, Gerhard Reinelt, and William R. Pulleyblank. "On partitioning the edges of graphs into connected subgraphs." Journal of graph theory 9.4 (1985): 539-549. states that for ...