Questions tagged [bounded-degree]
The bounded-degree tag has no usage guidance.
13
questions
1
vote
0
answers
95
views
Complexity of counting 3-colourings of planar bounded degree graphs
The following are known:
It is #P-complete to count the number of 3-colourings of a planar graph (with respect to randomized reductions) [1].
For all $d\geq 3$, it is #P-complete to count the number ...
- 1,603
2
votes
0
answers
48
views
The number of rooted ordered trees of max-out degree $k$
An ordered tree (also known as ordinal tree and plane tree) is a rooted tree in which the children of each node are ordered. It is known that the number of the ordered tree with $n$ edges is the $n$'...
2
votes
0
answers
145
views
Sensitivity and Low-Degree Approximation under Non-Uniform Distribution
I am searching for generalizations of analysis of Boolean functions when the input strings are distributed according to a general non-uniform distribution, possibly with arbitrary dependencies between ...
- 21
1
vote
0
answers
58
views
relations between the degrees of a boolean function and its absolute function
Given a boolean function $f:\{0,1\}^n\rightarrow\mathbb{R}$ of degree $d$, is there any upper bound in terms of $d$ on the degree of the function $|f|$, where $|f|(x)=|f(x)|$. Here the degree of $f$ ...
- 11
10
votes
2
answers
329
views
Finding subgraphs with high treewidth and constant degree
I am given a graph $G$ with treewidth $k$ and arbitrary degree, and I would like to find a subgraph $H$ of $G$ (not necessarily an induced subgraph) such that $H$ has constant degree and its treewidth ...
- 7,350
7
votes
0
answers
206
views
Bias of a random boolean low degree polynomial
What is the bias of a random Boolean function that can be represented as a low degree polynomial over the reals, i.e. has low Fourier degree?
More specifically, is it true that if we take a uniformly ...
- 1,887
6
votes
1
answer
392
views
Degree restriction for polynomials in $\mathsf{VP}$
why do we need the restriction on the degree for a polynomial to be in VP due to which $(\prod_{i=0}^{n} x_i)^{2^n}$ $\notin$ VP even though it has a poly-size circuit?
- 193
21
votes
1
answer
433
views
Random functions of low degree as a real polynomial
Is there a (reasonable) way to sample a uniformly random boolean function $f:\{0,1\}^n \to \{0,1\}$ whose degree as a real polynomial is at most $d$?
EDIT: Nisan and Szegedy have shown that a ...
- 1,887
13
votes
4
answers
2k
views
hardness of approximating the chromatic number in graphs with bounded degree
I am looking for hardness results on vertex coloring of graphs with bounded degree.
Given a graph $G(V,E)$, we know that for any $\epsilon>0$, it's hard to approximate $\chi(G)$ within a factor ...
- 271
3
votes
1
answer
184
views
bounded outdegree bipartite spanners
Given an undirected graph $G = (V,E)$ and an integer $k > 0$, our objective is to find a subgraph $G' = (V ,E')$ where $E' \subseteq E$ such that $G'$ has the three following properties :
$G'$ ...
- 634
21
votes
2
answers
1k
views
Is feedback vertex set problem solvable in polynomial time for 3-degree bounded graphs?
Feedback Vertex Set (FVS) is NP-complete for general graphs. It is known to be NP-complete for degree-$8$ bounded graphs due to a reduction from vertex cover.
The Wikipedia article says that it is ...
- 368
0
votes
2
answers
267
views
Complexity of finding if a degree bounded graph H is a subgraph of an unbounded graph G
You are given two graphs G and H , and want to know if H is a subgraph of G.
You know that H has a max vertex degree K (constant integer).
What can you say about the complexity of this?
I know that ...
- 143
10
votes
1
answer
432
views
Hardness of approximating fractional chromatic number on bounded degree graphs
Is it apx-hard to approximate fractional chromatic number on bounded degree graphs?
- 1,554