Questions tagged [graph-theory]

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

Filter by
Sorted by
Tagged with
8
votes
1answer
632 views

Max-clique in line graph of hypergraph

Suppose we have a multigraph (later, a multihypergraph). An edge-clique is a set of edges which all pairwise intersect (have at least one common vertex). Then any edge-clique $C$ in a multigraph ...
11
votes
3answers
2k views

Extension to the Stable Marriage Problem ?

This may sound more like a social sciences question more than a TCS one, but it is not. When reading "Randomized Algorithms" which describes the Stable Marriage Problem, one can read the following (...
4
votes
0answers
223 views

Follow-up on Nair/Tetali's Correlation Decay Tree for hypergraphs?

I'm wondering if anybody has followed up on Nair/Tetali's correlation decay tree construction for hypergraphs. I didn't find anything relevant in back-citation on google scholar. Interesting question ...
6
votes
0answers
209 views

Further question on hardness of node partitioning under shortest path constraint

This question first appeared at Hardness of node partitioning under shortest path constraint and I restate it here Given a direct graph $G=(V,E)$. $\forall (i,j) \in E$, there is a weight $w(i,j) \...
1
vote
1answer
3k views

Pre-order traversal on a search tree

The following is from this year's CS GRE practice test. I've worked through the test and I've been able to understand every question except for this one. Can anyone help me understand what's going on ...
25
votes
2answers
3k views

Hamiltonicity of k-regular graphs

It is known that it is NP-complete to test whether a Hamiltonian cycle exists in a 3-regular graph, even if it is planar (Garey, Johnson, and Tarjan, SIAM J. Comput. 1976) or bipartite (Akiyama, ...
26
votes
3answers
942 views

When is relaxed counting hard?

Suppose we relax the problem of counting proper colorings by counting weighted colorings as follows: every proper coloring gets weight 1 and every improper coloring gets weight $c^v$ where $c$ is some ...
4
votes
1answer
592 views

Hardness of node partitioning under shortest path constraint

Given a direct graph $G=(V,E)$. $\forall (i,j) \in E$, there is a weight $w(i,j) \in R$ (negative weight is possible). A label $l(i)$ is associated with each node $i \in V$. How to assign $k$ (or less)...
13
votes
1answer
4k views

What is the correct definition of $k$-tree?

As the title says, what is the correct definition of $k$-tree? There are several papers that talk about $k$-trees and partial $k$-trees as alternative definitions for graphs with bounded treewidth, ...
5
votes
1answer
218 views

How can one construct a densest graph with no k-clique?

Given integers $k$ and $n$ with $2 \le k < n$, how does one construct a graph on $n$ vertices that contains no $k$-clique and has the maximal number of edges? This sounds like basic ...
23
votes
1answer
859 views

Logspace algorithms on graphs with bounded tree width

Tree width measures how close a graph is to a tree. It is NP-hard to compute tree width. The best known approximation algorithm achieves $O(\sqrt{{\log}n})$ factor. Courcelle's theorem states that ...
2
votes
1answer
255 views

Number of Vertex Covers and Permanent

Is there any relationship between the number of vertex covers of a graph $G$ and the permanent of $G$'s adjacency matrix?
2
votes
2answers
1k views

polygonal triangulation and 3-colorability

Lets define polygonal triangulation a triangulation which has a hamiltonian cycle. It's easy to see that any polygonal triangulation is 3-colorable since any triangulation of a polygon is 3-colorable....
17
votes
3answers
1k views

Properties of Random Directed Graphs with Fixed Out-Degree

I am interested in properties of random directed graphs with fixed out-degree $d$. I am imagining a random graph model where each vertex chooses d neighbors (say, with replacement) u.a.r. ...
1
vote
1answer
1k views

Removing all but a few cycles in a graph

Let problem $S$ be defined as Given undirected graph $G$ and a set of cycles $C_1,C_2, \ldots, C_n$ in G, find minimum number of vertices that need to be deleted to remove all cycles in the ...
7
votes
1answer
945 views

Graph Theory Fun Problem

Show that in any graph $G$ with min-degree $k$ ($k \geq 1$ duh!) you can find as its subgraph any tree on $k+1$ vertices. I have not been able to solve the question so far. However, I would like if ...
-2
votes
1answer
2k views

How do I formally describe a rooted, directed, acyclic graph?

I need a formalism to describe the following requirements: I have a graph comprised of nodes and transitions between nodes Nodes maybe one of three types, all are sub-classes of a base abstract node ...
0
votes
3answers
3k views

Is it possible to have a 4-coloring for a non-planar graph ? [closed]

I have been working on this thread Grid $k$-coloring without monochromatic rectangles, and I am aware that the four color theorem implies that all planar graphs are four colorable. The question is ...
7
votes
3answers
5k views

Polynomial Time Algorithm for Graph Isomorphism Testing [closed]

"Michael I. Trofimov" claims that he has found a poly-time algorithm for graph isomorphism, which works for all graphs. The paper is given in arXiv. The companion website gives a proof-of-concept ...
7
votes
4answers
802 views

A relaxed Steiner Tree Problem

Given a weighted graph $G(V,E,w)$ where $w$ is the weight function on edges and a subset of vertices $S\subseteq Q$ called terminals, a Steiner Tree is a connected subgraph which connects all vertices ...
15
votes
6answers
486 views

Global properties of hereditary classes?

A hereditary class of structures (e.g. graphs) is one that is closed under induced substructures, or equivalently, is closed under vertex removal. Classes of graphs that exclude a minor have nice ...
11
votes
1answer
402 views

Computation of max H-free sets

In a graph, an independent set is a vertex subset which doesn't contain an edge as an induced subgraph. The problem of finding largest independent sets in a graph is a fundamental algorithmic question,...
6
votes
3answers
641 views

In Strongly connected tournament T.Is it NP-hard to find a minimum number of vertices(V1) which make T\V1 as non strongly connected tournament.

Given strongly connected tournament T.find a minimum number of vertices(V1) which make T\V1 as non strongly connected tournament. I have doubt whether the problem mentioned can be solved in polynomial ...
13
votes
2answers
370 views

H-free partition

This is a question inspired by the H-free cut problem. Given a graph, a partition of its vertex set $V$ into $r$ parts $V_1, V_2, \ldots, V_r$ is $H$-free if $G[V_i]$ does not induce a copy of $H$ for ...
1
vote
1answer
624 views

Does this notation have a special meaning?

I am currently reading a paper and I don't know how to interpret this notation you can see on the screenshot. http://moxn.brainex.de/pub/dfg.png Do the pointy angle brackets have a special meaning ...
17
votes
1answer
630 views

Rapidly mixing Markov chains on 3-colorings of a cycle

The Glauber dynamics is a Markov chain on the colorings of a graph in which at each step one attempts to recolor a randomly chosen vertex with a random color. It does not mix for the 3-colorings of a ...
16
votes
1answer
541 views

Sensitivity of Graph Properties

In [1], Turan shows that the sensitivity (called "critical complexity" in the paper) of a graph property is strictly greater than $\lfloor {1\over 4} m \rfloor$ where $m$ is the number of vertices in ...
8
votes
6answers
614 views

Have any generalizations of maximum weight matching been studied?

For example, one way to view maximum weight matching is that each vertex $v$ gets a utility $f_v= w(e_v)$ that equals the weight of the edge it's matched on, and zero otherwise. accordingly, a ...
19
votes
1answer
952 views

Construction of graphs where every pair of vertices have an unique common neighbor

Let $G$ be a simple graph on $n$ vertices $(n > 3)$ with no vertex of degree $n − 1$. Suppose that for any two vertices of $G$, there is a unique vertex adjacent to both of them. It is an exercise ...
36
votes
9answers
11k views

Data for testing graph algorithms

I am looking for a source of huge data sets to test some graph algorithm implemention. Please also provide some information about the type/distribution (e.g. directed/undirected, simple/not simple, ...
34
votes
3answers
2k views

Given a weighted dag, is there an O(V+E) algorithm to replace each weight with the sum of its ancestor weights?

The problem, of course, is double counting. It's easy enough to do for certain classes of DAGs = a tree, or even a serial-parallel tree. The only algorithm I have found which works on general DAGs in ...
2
votes
3answers
946 views

Best bounds for the longest path optimization problem in cubic Hamiltonian graph?

optimization problem Input: cubic Hamiltonian graph feasible solution: A simple path measure to optimize: length of the simple path Design a polynomial-time algorithm that outputs the longest path ...
3
votes
2answers
321 views

What is the complexity of computing a compatible 3-coloring of a complete graph?

Given a complete graph whose edges are colored by 3 colors, a compatible 3-coloring is a coloring of nodes such that no edge of the graph has the same color as its end-points. The best algorithm I ...
2
votes
1answer
339 views

What is the most efficient algorithm to sample graphs with trivial automorphism groups ?

Let us call a graph "asymmetric" if it has no nontrivial automorphism group. http://en.wikipedia.org/wiki/Asymmetric_graph I'm looking for an efficient way to compute a random asymmetric graph on a ...
6
votes
4answers
778 views

What are the best known upper bounds and lower bounds for computing O(log n)-Clique?

Input: a graph with n nodes, Output: A clique of size $O(\log n)$, Providing links to references would be great
24
votes
2answers
847 views

Space efficient “industrial” unbalanced expanders

I am looking for unbalanced expanders that are "good" and "space-efficient". Specifically, a bipartite left-regular graph $G=(A,B,E)$, $|A|=n$, $|B|=m$, with left degree $d$ is a $(k,\epsilon)$-...
28
votes
3answers
1k views

How to produce a random graph that does not have a Hamiltonian cycle?

Let class A denote all the graphs of size $n$ which have a Hamiltonian cycle. It is easy to produce a random graph from this class--take $n$ isolated nodes, add a random Hamiltonian cycle and then add ...
23
votes
3answers
1k views

What bounds can be put on counting reachable nodes in a dag?

Given is a dag. You want to label each node by how many nodes are reachable from it. $O(V(V+E))$ is a trivial upper bound; $\Omega(V+E)$ is a lower bound (I think). Is there a better algorithm? Is ...
24
votes
6answers
2k views

Graph families which have polynomial time algorithms for computing the chromatic number

Post updated on 31st of August: I added a summary of the current answers below the original question. Thanks for all the interesting answers! Of course, everyone can continue posting any new findings. ...
11
votes
2answers
3k views

Any fast algorithm for minimum cost feedback arc set problem?

In a directed graph, $G=(V,E)$, $F\subset E$, if $G\setminus F$ is a DAG(directed acyclic graph), $F$ is called a feedback arc set. If each edge is associated with a weight $w$, the minimum cost ...
13
votes
1answer
328 views

Finding odd holes in circulant Paley graphs

The Paley graphs Pq are those whose vertex-set is given by the finite field GF(q), for prime powers q≡1 (mod 4), and where two vertices are adjacent if and only if they differ by a2 ...
23
votes
1answer
361 views

Cliquewidth of Almost Cographs

(I posted this question to MathOverflow two weeks ago, but so far without a rigorous answer) I have a question about graph width measures of undirected simple graphs. It is well-known that cographs (...
17
votes
2answers
650 views

H-free cut problem

Suppose you are given a connected, simple, undirected graph H. The H-free cut problem is defined as follows: Given a simple, undirected graph G, is there a cut (partition of vertices into two ...
20
votes
2answers
1k views

Succinct circuit representation of graphs

The complexity class PPAD (e.g. computing various Nash equilibria) can be defined as the set of total search problems polytime reducible to END OF THE LINE: END OF THE LINE: Given circuits S and P ...
16
votes
1answer
872 views

Online transitive closure better than O(N^2) per edge addition

I'm looking for an online algorithm to maintain the transitive closure of a directed acyclic graph with a time complexity less than O(N^2) per edge addition. My current algorithm is like this: ...

1
22 23 24 25
26