Zobrazeno 1 - 10
of 86
pro vyhledávání: '"Curticapean, Radu"'
A central result of Marx [ToC '10] proves that there are $k$-vertex graphs $H$ of maximum degree $3$ such that $n^{o(k /\log k)}$ time algorithms for detecting colorful $H$-subgraphs would refute the Exponential-Time Hypothesis (ETH). This result is
Externí odkaz:
http://arxiv.org/abs/2410.02606
Autor:
Curticapean, Radu, Neuen, Daniel
For a fixed graph property $\Phi$ and integer $k \geq 1$, the problem $\#\mathrm{IndSub}(\Phi,k)$ asks to count the induced $k$-vertex subgraphs satisfying $\Phi$ in an input graph $G$. If $\Phi$ is trivial on $k$-vertex graphs (i.e., if $\Phi$ conta
Externí odkaz:
http://arxiv.org/abs/2407.07051
In this paper we further explore the recently discovered connection by Bj\"{o}rklund and Kaski [STOC 2024] and Pratt [STOC 2024] between the asymptotic rank conjecture of Strassen [Progr. Math. 1994] and the three-way partitioning problem. We show th
Externí odkaz:
http://arxiv.org/abs/2404.04987
Autor:
Curticapean, Radu
Given graphs $H$ and $G$, possibly with vertex-colors, a homomorphism is a function $f:V(H)\to V(G)$ that preserves colors and edges. Many interesting counting problems (e.g., subgraph and induced subgraph counts) are finite linear combinations $p(\c
Externí odkaz:
http://arxiv.org/abs/2305.04767
Autor:
Curticapean, Radu
We give a new combinatorial explanation for well-known relations between determinants and traces of matrix powers. Such relations can be used to obtain polynomial-time and poly-logarithmic space algorithms for the determinant. Our new explanation avo
Externí odkaz:
http://arxiv.org/abs/2204.10718
Autor:
Curticapean, Radu, Xia, Mingji
In the 1960s, statistical physicists discovered a fascinating algorithm for counting perfect matchings in planar graphs. Valiant later showed that the same problem is #P-hard for general graphs. Since then, the algorithm for planar graphs was extende
Externí odkaz:
http://arxiv.org/abs/2108.12879
We systematically investigate the complexity of counting subgraph patterns modulo fixed integers. For example, it is known that the parity of the number of $k$-matchings can be determined in polynomial time by a simple reduction to the determinant. W
Externí odkaz:
http://arxiv.org/abs/2107.00629
Autor:
Curticapean, Radu
Given an integer $n\geq 1$ and an irreducible character $\chi_{\lambda}$ of $S_{n}$ for some partition $\lambda$ of $n$, the immanant $\mathrm{imm}_{\lambda}:\mathbb{C}^{n\times n}\to\mathbb{C}$ maps matrices $A\in\mathbb{C}^{n\times n}$ to $\mathrm{
Externí odkaz:
http://arxiv.org/abs/2102.04340
For even $k$, the matchings connectivity matrix $\mathbf{M}_k$ encodes which pairs of perfect matchings on $k$ vertices form a single cycle. Cygan et al. (STOC 2013) showed that the rank of $\mathbf{M}_k$ over $\mathbb{Z}_2$ is $\Theta(\sqrt 2^k)$ an
Externí odkaz:
http://arxiv.org/abs/1709.02311
We introduce graph motif parameters, a class of graph parameters that depend only on the frequencies of constant-size induced subgraphs. Classical works by Lov\'asz show that many interesting quantities have this form, including, for fixed graphs $H$
Externí odkaz:
http://arxiv.org/abs/1705.01595