Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [graph-theory]

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

1
vote
1answer
61 views

Is balanced Hamiltonian cycle NP complete on maximal plane graphs?

I know that the Hamiltonian cycle is NP complete on the class of maximal plane graphs. If we instead ask about balanced Hamiltonian cycles (i.e. same number of faces on both sides) on maximal plane ...
1
vote
1answer
66 views

Pulling a graph across a partition

I am looking for the name for a particular graph property, if it has been studied, and efficient algorithms for computing it, if they exist. I realise that this may be a well known property that I am ...
1
vote
1answer
65 views

Cryptography protocols using graph problem instances

I personally am only aware of basic examples of public key cryptography and I haven't studied cryptography yet. I'm curious if there are circumstances in cryptography where using problem instances ...
2
votes
0answers
104 views

Crime prevention using graph theory and machine learning

I am looking for a way to the model the incidence of crime among a network of individuals. Part of it will use machine learning, and part of it will have to resort to some graph theoretic ...
-1
votes
0answers
34 views

What's the definition of the weight of a cut in a weighted directed graph?

In the Wikipedia article on Cut (graph theory), the following is mentioned: In an unweighted undirected graph, the size or weight of a cut is the number of edges crossing the cut. In a weighted ...
2
votes
0answers
67 views

randomly sample a degeneracy ordering

Given an undirected graph $G$, the $k$-core of $G$ is defined as the maximal subgraph such that each vertex has at least $k$ neighbors in the subgraph. The cores of $G$ can be computed by the ...
8
votes
1answer
278 views

Is there an algorithm that finds the forbidden minors?

The Robertson–Seymour theorem says that any minor-closed family $\mathcal G$ of graphs can be characterized by finitely many forbidden minors. Is there an algorithm that for an input $\mathcal G$ ...
9
votes
0answers
108 views

Random unbalanced bipartite graphs are good small set expanders

My question is about small set expansion properties of random unbalanced bipartite graphs. Fix a positive $\delta<1/2$, and a positive integers $n,m,d$. Let us call a bipartite graph $\mathcal{G}$...
4
votes
1answer
62 views

Complexity of finding Exact Size Cut-Sets in Bipartite Graphs

I am interested in the problem of deciding if a cut-set of a given size $k$ (i.e. the number of edges crossing the partitions is $k$) exists in a given bipartite graph (both the graph and $k$ are part ...
1
vote
1answer
41 views

Problem property name where an optimal solution in a graph can be used as a solution in any subgraph

Suppose one is given a graph optimization problem where the optimal solution $S$ for the problem on graph $G$ can be used as a solution for any subgraph of $G$. In other words, given $S$ is an optimal ...
5
votes
1answer
104 views

Counting/Enumerating Minimal Edge Covers

A Minimal Edge Cover is an Edge Cover such that no other Edge Cover is a proper subset of it. Questions Which is the complexity of counting Minimal Edge Covers? Do we know any non-trivial ...
12
votes
1answer
809 views

Number of 4 cycles

Let $C_4$ be a cycle with four vertices. For an arbitrary graph $G$ with $n$ vertices and m edges say $m>n\sqrt n$, how many $C_4$s exist? Is there a lower bound for this?
1
vote
0answers
49 views

Reduction of irregular graphs, to regular graphs, while preserving hamiltonicity

I am wondering if this is a topic that has had research done... If I could reduce irregular graphs to regular graphs (including replacing redundant node clusters with dummy nodes), while ensuring ...
0
votes
0answers
72 views

Partitioning directed graph

I'm a newbie in the mathematical field of graph theory (started to dive into it only few days ago) but I'm a very fast learner and have deep mathematical background. I'm trying to find/develop an ...
8
votes
1answer
181 views

Could chromatic number be easy to calculate when colouring is hard for some graph class?

Similar question was asked before, but there was an error in it so it was left unanswered Graph class with easy chromatic number, but NP-hard coloring Is there any infinite set of graphs $C$ such as: ...
4
votes
1answer
112 views

Is graph connectivity definable in existential MSO with vertices and edges?

Can $\exists$MSO$_2$ express graph connectivity? Monadic SO (MSO) is the fragment of second-order logic in which the second-order quantifiers range over relations of arity 1 only. $\exists$MSO is the ...
9
votes
0answers
97 views

Graphs with minimal-size induced subgraphs

I consider undirected graphs $G = (V, E)$ for which I write $\text{n}(G) := |V|$ the number of vertices and $\text{m}(G) := |E|$ the number of edges. For $d \in \mathbb{N}$, I say that $G$ is $d$-...
4
votes
0answers
109 views

A variant of hitting set: finding a matching to hit all edge sets

In general, the hitting set problem is given a family $\cal S$ of sub-sets, $\{S_1, \cdots, S_h\}$, and a universal set $U = \bigcup_{i\in [1,h]} S_i$. It asks for a minimum set $H \subseteq U$ ...
1
vote
1answer
59 views

Minimum graph cut with constraints

Given an undirected acyclic raph $G = \{V,E\}$, with each edge $e$ having weight $c_e$in the range $[-\infty, +\infty] $, I want to compute a partition of the graph into $N$ disjoint sets $G_i, i=1,......
6
votes
1answer
190 views

Paths of length $p$ in a Graph, $p$ a prime

I came across the following decision problem, for which I wondered whether anybody of you came across a similar problem and can give me some insight on its nature/complexity. Given as input a ...
-2
votes
1answer
97 views

Finding Cheapest n-Path [closed]

Given a weighted directed acyclic graph, how can I find the cheapest path from an Origin Vertex to a Destination Vertex which ...
4
votes
1answer
123 views

Fast algorithm to find a maximum connected subgraph of k vertices

Given an undirected graph $G = (V, E)$ and a function $f: 2^V \to \mathbb{R}^+,$ where $2^V$ is the set of all subsets of $V$. Find a connected subgraph $T = (V_T, E_T)$ of k vertices such that $f(V_T)...
6
votes
0answers
89 views

Ramsey number for path in a colored tournament

I am looking about the following Ramseyish theorem with additional structure on tournament (see [1]). For all number of colors $k$, there exists $n=T(k)$ such that all tournaments of size $n$ ...
-4
votes
2answers
85 views

Looking for an algorithm to construct a graph from two subgraphs

I am looking for an algorithm to construct a graph from two subgraphs. The problem is as following: Given two graphs g1(V, E) and g2(V, E), find a graph G(V, E) where V(g1) ⊆ V(G), V(g2) ⊆ V(G), E(g1)...
3
votes
0answers
68 views

Mutually exclusive replacement paths, an existing problem?

A replacement path is a simple path allocated to an edge $e \in G$ that connects the endpoints of $e$ in $G \setminus \{e\}$. The problem An undirected graph $G$ is given and the task is to allocate ...
-1
votes
1answer
55 views

How to make any graph 2-degenerate?

I have to show a PPT(polynomial time reduction) from 'Colorful graph Motif' to '2-Degenerate Steiner Tree'. As input graph should be 2-degenerate, but here is normal graph G (that is, basically an ...
0
votes
0answers
47 views

Complexity of extending $P_4 $-partition of cubic graphs

This is a question I posted on MathOverflow before but never got an answer. I am cross-posting it here. Surprising phenomena occurs when we want to extend a partial solution of some easy problems. We ...
4
votes
2answers
139 views

Check if graph stays connected after edge swap

Checking whether a (simple, undirected) graph is connected can be done in linear time in the number of edges. What I am looking for is a more efficient way of checking whether it stays connected after ...
0
votes
0answers
29 views

Reduce maximum capacity simple cycle to maximum capacity minimum cost cycle

Consider the following problems $(A)$: Let $G=(V,E)$ a non-directed graph, a capacity function $u:V\to\mathbb Q_+\cup\{0\}$ and $m \in \mathbb Q_+$. Decide if there exists a simple cycle such that ...
3
votes
1answer
163 views

What exactly is Lawler's modification to Yen's algorithm and how does it work?

I recently read about Yen's algorithm, I understand the algorithm and it seems correct, however Wikipedia mentions that there exists "Lawler's modification" to the algorithm, which is described as ...
4
votes
1answer
95 views

Probability of a $k$-path in a random graph

Assume that $G\in G(n,p)$; if $p=\frac{\ln n +\ln \ln n +c(n)}{n}$, the following fact is well known: \begin{eqnarray} Pr [G\mbox{ has a Hamiltonian cycle}]= \begin{cases} 1 & (c(n)\...
4
votes
1answer
306 views

Minimum Union-Sum Cost Path

I have a minimum cost path selection problem that is different from the usual shortest path in that each type of cost is accounted only once in the total cost of the path if multiple edges on the path ...
1
vote
0answers
37 views

Random Multigraph ER-like model?

I was looking into multigraphs recently and I couldn't find a simple "goto" model for generating random multigraphs along the lines of the ER model of simple graphs. Specifically, I was hoping to find ...
-1
votes
1answer
51 views

NP-Complete graph problems where a special vertex is given as input?

I am currently working on a graph theory problem where the instance includes a graph and a special vertex in the graph. I am trying to prove the NP-completeness of the problem as well as explore ...
1
vote
0answers
52 views

k-center 2.0: A stronger k-center condition

Given an unweighted, undirected graph, we can use the classical 2-appx for $k$-center to select a set $S$ of centers such that every vertex is within a distance of 2 of some center in $S$. Note that ...
0
votes
0answers
24 views

explicit UES for $D$-regular graphs over $N$ vertices through the line graph

First of all observe that if we have $G$, a $D$-regular graph over $N$ vertices that is equipped with a consistent labeling $\ell$ then we can induce a consistent labeling for $L(G)$ the line graph of ...
1
vote
1answer
105 views

Total flow using minimum number of edges on a bipartite network

If I have a set of sources $S$ with total capacity $C$ and a set of sinks $T$ with the same capacity $C$, but not necessarily the same cardinality, is there an efficient way to find the minimum number ...
5
votes
1answer
134 views

Lower bound for triangle-free graphs

I was reading a set of notes where it says It can be shown that $\Omega(n^2)$ space is needed for one-pass algorithms to determine if an (unweighted, undirected) graph $G$ with $n$ nodes contains ...
1
vote
0answers
37 views

Counting vertex covers on a chain of k nodes that do not contain a sub-chain of length >=3

By a "chain of k nodes", I mean k nodes lined up like a linked-list: o-o-o.....-o . By "do not contain a sub-chain of length >=3", I mean that no cover should contain two edges that shares a node. ...
1
vote
0answers
35 views

Planarity testing of directed graph and 3d grid

I wonder if there exist definitions (and known algorithms) of planarity testing for the following case: 1- A directed graph let $G=(V=\{1,\ldots,n\},E)$ be a directed graph. Assume $e_{ij} =(v_i,...
4
votes
1answer
174 views

How hard is it to determine the chromatic number of a unit distance graph?

For example, is it NP-complete to decide whether a unit distance graph is 3-colorable?
5
votes
2answers
181 views

The chromatic number of a graph as a functor

I was fooling around with some concept and was wondering if this viewpoint is explored at all. Let INJ-GRAPH be the subcategory of graphs (with morphisms as homomorphisms) whose morphisms consist only ...
5
votes
0answers
146 views

Can graphons be useful outside of extremal graph theory?

I was recently introduced to the notion of a Graphon ([Quick introduction], [Original definition]) and I have been fascinated by the idea behind them and the way they combine fields such as graph ...
6
votes
1answer
134 views

Partition edges into edge disjoint walks

Consider an undirected graph $G=(V,E)$ and two sequences of $k$ vertices $S=s_1,\ldots,s_k$ and $T=t_1,\ldots,t_k$. A set of $k$ walks is called a $(S,T)$-walk partition if the walks form a ...
3
votes
0answers
108 views

Is 3-coloring bounded degree graphs subexponential: $O(\exp{(\sqrt{n}\log^2{n})})$? [closed]

We got an argument that 3-coloring bounded degree graphs is subexponential with complexity $O(\exp{(\sqrt{n}\log^2{n})})$. The treewidth of a planar graphs on $n$ vertices is $O(\sqrt{n})$ and 3-...
4
votes
1answer
152 views

Can $L=SL$ be shown with the replacement product instead of the zig-zag product?

(This is a bit of follow-up to https://cstheory.stackexchange.com/posts/comments/93266 but is a distinct enough question I though it should be on its own.) In Omer Reingold's logspace USTCON ...
6
votes
1answer
130 views

Path in a graph with durations [closed]

I have the following problem: given a directed graph $G=(V,E,d)$, where $d:V\to\mathcal{I}(\mathbb{Q}_0^+\cup\{+\infty\})$ (here $\mathbb{Q}_0^+$ denotes the set of non-negative rationals and $\...
3
votes
0answers
74 views

PTIME or NP-Hardness of stochastic objective function

I will begin by linking a previous post where I asked a general question for a stochastic setting which I describe below. It turns out that my "proof" for a restricted case had a mistake and there is ...
4
votes
0answers
81 views

Showing hardness of maximizing stochastic objective function over graph

Consider a graph $G = (V, E)$ with $n$ vertices and $m$ edges. Each vertex $v_i$ can take positive value $a_i$ with probability $p_i$ and value $0$ with probability $1-p_i$. The challenge is to ...
3
votes
1answer
108 views

Results/concepts that also proved useful outside of their “home areas”

There are some results/concepts in TCS which are used in areas other than the "home area" where they emerged. For example, NP-completeness has complexity theory as its home area, but it is also used ...