Questions tagged [graph-theory]
Graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects.
1,592 questions
1
vote
1
answer
112
views
Domination between sets of nodes in a union of tournaments
Let $G$ be a directed graph obtained from the union of two tournaments $T_1$ and $T_2$ on the same vertex set, plus a loop arc on each vertex. We can assume that the tournaments $T_1$ and $T_2$ are ...
- 442
2
votes
0
answers
60
views
How updated is the ISGCI database?
According to the Information System on Graph Classes and their Inclusions (ISGCI) database, the complexity class of the MAXCUT problem for the following graph families (and) is still unknown. How ...
- 691
5
votes
0
answers
105
views
Listing spanning trees of a complete graph with constant delay
We are looking for any known algorithms/lower bounds related the the following problem:
Enumerate all spanning trees of a complete graph by edits with constant delay (linear time preprocessing allowed)...
- 151
0
votes
1
answer
370
views
I have written a preprint about a novel algorithm to find MST, I think it can be a replacement for Kruskal's algorithm; Can any anyone review it?
I am a recent CS Grad, and I wrote a preprint about a algorithm for MST, with time complexity O(E+VlogV) and Ω(E) in the worst and base cases, respectively; given sorted edges. I feel like it is a ...
6
votes
1
answer
181
views
Complexity of equitable coloring on regular graphs
Are the following problems known to the NP-hard (or solvable in polynomial time)?
Given an $r$-regular graph $G(V,E)$ and an integer $c\leq r$, does there exist a proper $c$-coloring of (the vertex ...
- 61
2
votes
0
answers
47
views
Complexity of equitable coloring on regular graphs
Are the following problems known to the NP-hard, or are they solvable in polynomial time?
Given an r-regular graph G(V,E) and an integer c≤r, does there exist a proper c-coloring of (the vertex set ...
anonymous_math_enthusiast
0
votes
1
answer
135
views
How do tree-width, clique-width and rank-width meta-theorems for (#2)SAT relate to the primal vs. incidence graph?
I’m trying to get a clear picture of the various “width-based” metatheorems for SAT/#2SAT, and in particular:
Which graph are they measuring?
The primal (constraint) graph (G) on variables, with an ...
- 131
0
votes
1
answer
156
views
What is the cliquewidth of a hypercube graph?
Is this proof for the lower bound of the clique width of a hypercube graph accurate? If so, is there an upper bound? If it's not accurate, where does it go wrong?
The hypercube graph (Q_h) is the ...
- 131
4
votes
1
answer
514
views
Is it a common assumption in Shortest Path papers to assume uniqueness of path lengths?
This very interesting paper was washed into my feed, which claims that they found a generic Single-Source-Shortest-Path algorithm in less than $O(m+n \log n)$ time: "
Breaking the Sorting Barrier ...
- 41
2
votes
1
answer
342
views
Complexity of counting the number of cycles through a particular edge
It is known that counting cycles in a graph is a hard problem (#P-hard). However, what do we know about the following problem:
Given a simple, undirected graph $G$ and an edge $e$ of $G$ as input, ...
3
votes
0
answers
95
views
Number of edges in a graph with hamiltonian path but no induced long path
In the spirit of my previously asked question: Minimum number of edges in a hamiltonian cograph
I would like to explore the following question: If a graph $G$ contains a hamiltonian path and I forbid ...
- 193
1
vote
2
answers
186
views
Show that the first agent weakly prefers their own bundle to anybody else's
Suppose we have a set $N$ of $n$ players and a set $M$ of $m$ items. We are given a matrix $P_{n \times m}$ whose element $p_{ij} \geq 0$ $(i \in N, m \in M)$ denotes the valuation of good $j$ by ...
2
votes
1
answer
154
views
Show that in every pure SPNE, the first agent weakly prefers their own bundle to any other
Suppose we have a set $N$ of $n$ players and a set $M$ of $m$ items. We are given a matrix $P_{n \times m}$ whose element $p_{ij} \geq 0$ $(i \in N, m \in M)$ denotes the valuation of good $j$ by ...
3
votes
1
answer
158
views
Greedy algorithm for Tree Augmentation
The Tree Augmentation Problem is a special case of set cover where the ground set is the edges of a tree $T = (V,E)$, and the sets are edge-subpaths of $T$. The paths are usually called links.
There ...
- 701
2
votes
0
answers
62
views
Improving reachability checks in a sparse, transitive-reduced causal DAG
I maintain a directed acyclic graph (DAG) of events in a distributed system of n processes, with these properties:
With = n: there are n independent “chains” (one per process).
Transitive reduction: ...
- 21